编译原理课件：Linux编程与应用课件：第5章 语法分析-自下而上分析8.ppt

1、第五章第五章 语法分析语法分析自下而上分析自下而上分析语法分析方法：语法分析方法：n自上而下分析法自上而下分析法(Top-down)(Top-down)n自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)n基本思想基本思想 它从文法的开始符号出发，反复使用各种产生它从文法的开始符号出发，反复使用各种产生式，寻找式，寻找 匹配匹配 的的推导推导。n递归下降分析法递归下降分析法 对每一语法变量对每一语法变量( (非终结符非终结符) )构造一个相应的子构造一个相应的子程序，每个子程序识别一定的语法单位，通过程序，每个子程序识别一定的语法单位，通过子程序间的相互调用实现对输入串的

2、识别。子程序间的相互调用实现对输入串的识别。n预测分析程序预测分析程序F非递归实现非递归实现F优点：直观、简单和宜于手工实现。优点：直观、简单和宜于手工实现。n基本思想基本思想 从输入串开始，逐步进行从输入串开始，逐步进行“归约归约”，直到文，直到文法的开始符号。即从树末端开始，构造语法树。法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。生式的右部替换成左部符号。n算符优先分析法算符优先分析法 按照算符的优先关系和结合性质进行语法分析。按照算符的优先关系和结合性质进行语法分析。适合分析表达式。适

3、合分析表达式。nLRLR分析法分析法 规范归约规范归约G(E)： E i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E Ei+ +* *EiiEEEE第五章第五章 语法分析语法分析自下而上分析自下而上分析n自下而上分析的基本问题自下而上分析的基本问题n算符优选分析算法算符优选分析算法nLRLR分析法分析法一、自下而上分析的基本问题一、自下而上分析的基本问题n采用采用“”思想进行自下而上分析。思想进行自下而上分析。n基本思想基本思想 用一个寄存符号的先进后出用一个寄存符号的先进后出，把输入符号，把输入符号一个一个地移进到栈里，一个一

4、个地移进到栈里，当栈顶形成某个产当栈顶形成某个产生式的候选式生式的候选式时，即把栈顶的这一部分替换时，即把栈顶的这一部分替换成成( (归约归约为为) )该产生式的该产生式的左部符号左部符号。n例：例：设文法设文法G(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d试对试对abbcdeabbcde进行进行“移进归约移进归约”分析。分析。a bbcdeba bcdeAa bcdebAa cdeAa cdecAa dedcAa eabbcdeeBcAa S BcAa e步步骤骤: :1 12 23 34 45 56 67 78 89 91 10 0动动作作: : 进进

5、a a进进b b 归归( (2 2) ) 进进b b 归归( (3 3) ) 进进c c进进d d 归归( (4 4) ) 进进e e 归归( (1 1) )e ed dB BB Bb bc cc cc cc cb bA AA AA AA AA AA AA Aa aa aa aa aa aa aa aa aa aS SbdbaceSABA自下而上分析过程：边输入单词符号，边自下而上分析过程：边输入单词符号，边归约。归约。核心问题：识别可归约串核心问题：识别可归约串NNPVPSDETThe teacherVpraisedNNPDETthe studentn定义：令定义：令G G是一个文法，是一个

6、文法，S S是文法的开始符号，假是文法的开始符号，假定定是文法是文法G G的一个句型，如果有的一个句型，如果有 且且 AS*A则则 称是句型称是句型相对于非终结符相对于非终结符A A的的短语短语。特别是，如果有特别是，如果有A A, ,则称则称 是句型是句型相对于规相对于规则则A A 的的直接短语直接短语。一个句型的。一个句型的最左直接短语最左直接短语称为该句型的称为该句型的句柄句柄。n定义：令定义：令G G是一个文法，是一个文法，S S是文法的开始符号，假是文法的开始符号，假定定是文法是文法G G的一个句型，如果有的一个句型，如果有 且且 AS*A则则 称是句型称是句型相对于非终结符相对于非

7、终结符A A的的短语短语。考虑文法考虑文法G(E)： E T | E+T T F | T*F F (E) | i和和句型句型i1*i2+i3：E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3 * +E F*i2+i3 F i1 i1*i2+i3 短短 语：语： i1E i1 *F+i3 F i2 i1*i2+i3 短短 语：语： i2E i1*i2+F F i3 i1*i2+i3 短短 语：语： i3E E+ i3 E i1*i2 i1*i2+i3 短短 语：语： i1*i2 E E E i1*i2+i3 i1*i2+i3 短短 语：语：i

8、1*i2+i3 G(E)： E T | E+T T F | T*F F (E) | iE E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3考虑文法考虑文法G(E)： E T | E+T T F | T*F F (E) | i和句型和句型i1*i2+i3：E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3n短语：短语： i1，i2，i3， i1*i2， i1*i2+i3n直接短语：直接短语： i1，i2，i3n句柄：句柄： i1n在一个句型对应的语法在一个句型对应的语法树中：树中：p以某非终结符

9、为根的以某非终结符为根的两代以两代以上的子树的所有末端结点从上的子树的所有末端结点从左到右排列左到右排列就是相对于该非就是相对于该非终结符的一个终结符的一个短语短语p如果如果子树只有两代子树只有两代，则该短，则该短语就是语就是直接短语直接短语。EFFTTTi1+*EFi3i2n可用句柄来对句子进行归约可用句柄来对句子进行归约句型句型 归约规则归约规则abbcde (2) A bbdbaceSABAn可用句柄来对句子进行归约可用句柄来对句子进行归约句型句型 归约规则归约规则abbcde (2) A baAbcde (3) A AbdbaceSABAn可用句柄来对句子进行归约可用句柄来对句子进行归

10、约句型句型 归约规则归约规则abbcde (2) A baAbcde (3) A AbaAcde (4) B ddaceSABn可用句柄来对句子进行归约可用句柄来对句子进行归约句型句型 归约规则归约规则abbcde (2) A baAbcde (3) A AbaAcde (4) B daAcBe (1) S aAcBe SaceSABn定义：假定定义：假定 是文法是文法G的一个句子，我们的一个句子，我们称序列称序列 n， n-1， ， 0 是一个是一个规范归约规范归约，如果此序列满足：，如果此序列满足： 1 n= 为为句子句子 2 0为文法的为文法的开始符号开始符号，即，即 0=S 3 对任何

11、对任何i，0 i n， i-1是从是从 i经把经把句柄句柄替换成为替换成为相应产生式左部符号相应产生式左部符号而得到的。而得到的。把上例倒过来写，则得到：把上例倒过来写，则得到：S S aAcBeaAcBe aAcde aAcde aAbcde aAbcde a abbcde bbcde 显然这是一个最右推导。显然这是一个最右推导。规范归约规范归约是是最右推导最右推导的逆过程的逆过程最左归约最左归约 规范推导规范推导由规范推导推出的句型称为由规范推导推出的句型称为规范句型规范句型。bdbaceSABAdbaceSABAdaceSABaceSABS符号栈的使用符号栈的使用n栈栈是语法分析的一种基

12、本数据结构。是语法分析的一种基本数据结构。# #作为栈底符作为栈底符号号n自下而上的语法分析器的工作过程是：自下而上的语法分析器的工作过程是：自左至右把自左至右把输入串的符号一一移进符号栈里，一旦发现栈顶出输入串的符号一一移进符号栈里，一旦发现栈顶出现现可归约串可归约串就归约，这种替换可能出现多次，直至就归约，这种替换可能出现多次，直至栈顶不再出现栈顶不再出现可归约串可归约串为止。然后继续移进符号，为止。然后继续移进符号，重复整个过程，直至栈里只含有重复整个过程，直至栈里只含有#和文法开始符号和文法开始符号、且输入串全被吸收，仅剩下且输入串全被吸收，仅剩下#。这种格局表示分析成。这种格局表示分

13、析成功，否则，就说明输入串有语法错误功，否则，就说明输入串有语法错误符号栈的使用符号栈的使用n例：文法例：文法G(E)： E T | E+T T F | T*F F (E) | i输入串为输入串为i1*i2+i3 ，分析步骤为：，分析步骤为：步骤步骤 符号栈符号栈输入串输入串动作动作0 #i1*i2+i3#预备预备1 #i1*i2+i3#进进2 #F*i2+i3#归，用归，用Fi3 #T*i2+i3#归，用归，用TF4 #T*i2+i3#进进nG(E)： E T | E+T T F | T*F F (E) | i步骤步骤 符号栈符号栈输入串输入串动作动作4 #T*i2+i3#进进5 #T*i2

14、+i3#进进6 #T*F+i3#归，用归，用Fi7 #T+i3#归，用归，用TT*F8 #E+i3# 归，用归，用ET9 #E+i3# 进进nG(E)： E T | E+T T F | T*F F (E) | i步骤步骤 符号栈符号栈输入串输入串动作动作9 #E+ i3#进进10#E+i3#进进11#E+F#归，用归，用Fi12#E+T#归，用归，用TF13#E#归，用归，用EE+T14#E#接受接受nG(E)： E T | E+T T F | T*F F (E) | in语法分析的方法：语法分析的方法：自下而上分析法自下而上分析法(Bottom-up)(Bottom-up) 基本思想：从输入

15、串开始，逐步进行基本思想：从输入串开始，逐步进行“归约归约”，直到文法的开始符号。即从树末端开始，构造语直到文法的开始符号。即从树末端开始，构造语法树。所谓法树。所谓 归约归约 ，是指根据文法的产生式规，是指根据文法的产生式规则，把产生式的右部替换成左部符号。则，把产生式的右部替换成左部符号。 回顾回顾归约归约n采用采用“移进归约移进归约”思想进行自下而上分析。思想进行自下而上分析。n基本思想：用一个寄存符号的先进后出基本思想：用一个寄存符号的先进后出栈栈，把输，把输入符号一个一个地移进到栈里，当栈顶形成某个入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成产

16、生式的候选式时，即把栈顶的这一部分替换成( (归约归约为为) )该产生式的左部符号。该产生式的左部符号。规范归约规范归约n定义：令定义：令G G是一个文法，是一个文法，S S是文法的开始符是文法的开始符号，假定号，假定是文法是文法G G的一个句型，如果有的一个句型，如果有 且且 AS*A则则 称是句型称是句型相对于非终结符相对于非终结符A A的的短语短语。特别是，如果有特别是，如果有A A, ,则称则称 是句型是句型相对相对于规则于规则A A 的的直接短语直接短语。一个句型的最左。一个句型的最左直接短语称为该句型的直接短语称为该句型的句柄句柄。n定义：假定定义：假定 是文法是文法G的一个句子，

17、我们的一个句子，我们称序列称序列 n， n-1， ， 0 是的一个是的一个规范归约规范归约，如果此序列满足：，如果此序列满足： 1 n= 2 0为文法的开始符号，即为文法的开始符号，即 0=S 3 对任何对任何i，0 i n， i-1是从是从 i经把经把句句柄柄替换成为相应产生式左部符号而得到替换成为相应产生式左部符号而得到的。的。第五章第五章 语法分析语法分析自下而上分析自下而上分析n自下而上分析的基本问题自下而上分析的基本问题n算符优选分析算法算符优选分析算法nLRLR分析法分析法 二、算符优先分析二、算符优先分析n四则运算的优先规则：四则运算的优先规则： 先乘除后加减，同级从左到右先乘除

18、后加减，同级从左到右n考虑二义文法文法考虑二义文法文法G(E)：G(E)： E i| E+E|E-E|E*E|E/E|(E)n它的句子有几种它的句子有几种不同的规范规约不同的规范规约。n归约即计算表达式的值。归约顺序不同，归约即计算表达式的值。归约顺序不同，则计算的顺序也不同，结果也不一样。则计算的顺序也不同，结果也不一样。n如果规定算符的优先次序如果规定算符的优先次序，并按这种规定，并按这种规定进行归约，则归约过程是进行归约，则归约过程是唯一唯一的。的。例如：句子例如：句子i+i-ii+i-i* *(i+i)(i+i)Ei( () )i* *EiEE+ +EEE-ii+ +EEEG(E)：

19、E i| E+E|E-E|E*E|E/E|(E)Ei( () )i* *EiEE+ +EEE-ii+ +EEE返回G(E)： E i| E+E|E-E|E*E|E/E|(E)句子句子i+i-i*(i+i)的归约过程是：的归约过程是：(1) i+i-i*(i+i)(2) E+i-i*(i+i)(3) E+E-i*(i+i)(4) E-i*(i+i)(5) E-E*(i+i)(6) E-E*(E+i)(7) E-E*(E+E)(8) E-E*(E)(9) E-E*E(10) E-E(11) EG(E)： E i| E+E|E-E|E*E|E/E|(E)句子句子i+i-i*(i+i)的归约过程是：的

20、归约过程是：(1) i+i-i*(i+i)(2) F+i-i*(i+i)(3) T+i-i*(i+i)(4) E+i-i*(i+i)(5) E+F-i*(i+i)(6) E+T-i*(i+i)(7) E-i*(i+i)(8) E-F*(i+i)(9) E-T*(i+i)(10) E-T*(F+i)(11) E-T*(T+i)(12) E-T*(E+i)(13) E-T*(E+F)(14) E-T*(E+T)(15) E-T*(E)(16) E-T*F(17) E-T(18) E无二义文法：无二义文法：G(E)： E T |E+T|E-T T F |T*F|T/F F (E)|i G(E)： E

21、 i| E+E|E-E|E*E|E/E|(E)n起决定作用的是起决定作用的是相邻的两个算符（终结符）相邻的两个算符（终结符）之间的之间的优先关系优先关系。n所谓所谓算符优先分析法算符优先分析法就是定义就是定义算符（终结符）算符（终结符）之间的某种之间的某种优先关系优先关系，借助于这种关系寻找，借助于这种关系寻找“可归约串可归约串”和进行归约和进行归约。算符优先分析的基本思想算符优先分析的基本思想n定义任何两个可能相继出现的终结符定义任何两个可能相继出现的终结符a a与与b b的的三种优先关系三种优先关系 a b a a b a的优先级的优先级低于低于b b a b a a b a的优先级的优先

22、级等于等于b b a b a a b a的优先级的优先级高于高于b bn注意：与数学上的注意：与数学上的=不同不同 + + （先归约右边的（先归约右边的+） a ba b并不意味着并不意味着b ab a，如，如 ( + 和和 + ( 优先关系优先关系算符优先文法算符优先文法及及优先表优先表构造构造n一个文法，如果它的任一产生式的右部都一个文法，如果它的任一产生式的右部都不含两个相继不含两个相继(并列并列)的非终结符，即不含的非终结符，即不含如下形式的产生式右部：如下形式的产生式右部：QR 则我们称该文法为则我们称该文法为算符文法算符文法。n约定：约定：a、b代表任意终结符；代表任意终结符；P、

23、Q、R代表任意非终结符；代表任意非终结符；代表由终结符和非终结符组成的任意序代表由终结符和非终结符组成的任意序列，包括空字。列，包括空字。n假定假定G是一个不含是一个不含 -产生式的算符文法。产生式的算符文法。对于任何一对终结符对于任何一对终结符a、b，我们说：，我们说：1. a b，当且仅当文法，当且仅当文法G中含有形如中含有形如Pab或或PaQb的产生式；的产生式；2. a b，当且仅当，当且仅当G中含有形如中含有形如PaR的产生式，的产生式， 而而R b或或R Qb；3. a b ，当且仅当，当且仅当G中含有形如中含有形如PRb的产生式，而的产生式，而 R a或或R aQ。n如果一个算符

24、文法如果一个算符文法G中的任何终结符对中的任何终结符对(a，b)至多只满足下述三关系之一：至多只满足下述三关系之一： a b，a b， a b 则称则称G是一个算符优先文法。是一个算符优先文法。G(E)： E i| E+E|E-E|E*E|E/E|(E)不是一个算符优先文法不是一个算符优先文法G(E)： E T |E+T|E-T T F |T*F|T/F F (E)|i 是一个算符优先文法是一个算符优先文法 n例例:考虑下面的文法考虑下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | in由规则由规则(4)P(E) ，有，有

25、 ( )；n由规则由规则(1)EET和和(2)TT*F， 有有 *；n由由(2) TT*F 和和(3) FP F ，可得，可得* ；n由由(1)EE + T和和E E+T，可得，可得+ +；n由由(3)FP F和和F P F，可得，可得。n由由(4)P(E)和和 EE+TT+TT*F+TF*F+TPF*F+TiF*F+T 有有 ( + ( * ( ( i。n 优先关系表优先关系表+*i()#+*i()#n从算符优先文法从算符优先文法G构造优先关系表的算法构造优先关系表的算法。n通过检查通过检查G的每个产生式的每个候选式，可的每个产生式的每个候选式，可找出所有满足找出所有满足a b的终结符对。的

26、终结符对。2. a b，当且仅当，当且仅当G中含有形如中含有形如PaR的产生式，的产生式， 而而R b或或R Qb；3. a b ，当且仅当，当且仅当G中含有形如中含有形如PRb的产生式，而的产生式，而 R a或或R aQ。n确定满足关系确定满足关系 和和 的所有终结符对：的所有终结符对：1. a b，当且仅当文法，当且仅当文法G中含有形如中含有形如Pab或或PaQb的产生式；的产生式；n从算符优先文法从算符优先文法G构造优先关系表的算法构造优先关系表的算法n通过检查通过检查G的每个产生式的每个候选式，可的每个产生式的每个候选式，可找出所有满足找出所有满足a b的终结符对。的终结符对。n为确定

27、满足关系为确定满足关系 和和 的所有终结符对：的所有终结符对：首先需要对首先需要对G的每个非终结符的每个非终结符P构造两个集合构造两个集合FIRSTVT(P)和和LASTVT(P)：a b 当且仅当当且仅当G中含有形如中含有形如PaR的产生式，的产生式， 而而R b或或R Qb；n从算符优先文法从算符优先文法G构造优先关系表的算法。构造优先关系表的算法。n通过检查通过检查G的每个产生式的每个候选式，可的每个产生式的每个候选式，可找出所有满足找出所有满足a b的终结符对。的终结符对。n为确定满足关系为确定满足关系 和和 的所有终结符对：的所有终结符对：首先需要对首先需要对G的每个非终结符的每个非

28、终结符P构造两个集合构造两个集合FIRSTVT(P)和和LASTVT(P)：,|)(NTVQVaaQPaPaPLASTVT而或3. a b 当且仅当当且仅当G中含有形如中含有形如PRb的产生式，而的产生式，而 R a或或R aQ。n从算符优先文法从算符优先文法G构造优先关系表的算法。构造优先关系表的算法。n通过检查通过检查G的每个产生式的每个候选式，可的每个产生式的每个候选式，可找出所有满足找出所有满足a b的终结符对。的终结符对。n确定满足关系确定满足关系 和和 的所有终结符对：的所有终结符对：首先需要对首先需要对G的每个非终结符的每个非终结符P构造两个集合构造两个集合FIRSTVT(P)和

29、和LASTVT(P)：,|)(NTVQVaaQPaPaPLASTVT而或.,|=)(*TVaaaFIRST比较.,.|)(*TVaAaSaAFOLLOW比较q有了这两个集合有了这两个集合之后，就可以通过检查每之后，就可以通过检查每个产生式的候选式确定满足关系个产生式的候选式确定满足关系 和和 的的所有终结符对。所有终结符对。假定有个产生式的一个候选形为假定有个产生式的一个候选形为aP 那么，对任何那么，对任何b FIRSTVT(P)，有，有 a b。假定有个产生式的一个候选形为假定有个产生式的一个候选形为Pb 那么，对任何那么，对任何a LASTVT(P)，有，有 a b。n首先讨论构造集合首

30、先讨论构造集合FIRSTVT(P)的算法。的算法。n按其定义，可用下面两条规则来构造集合按其定义，可用下面两条规则来构造集合FIRSTVT(P)：1. 若有产生式若有产生式Pa或或PQa，则，则a FIRSTVT(P)；（直接从产生式看）；（直接从产生式看）2. 若若a FIRSTVT(Q)，且有产生式，且有产生式PQ，则则a FIRSTVT(P)。构造集合构造集合FIRSTVT(P) 的算法的算法将将对推导的遍历对推导的遍历转换成转换成对产生式的反复遍历对产生式的反复遍历n数据结构：数据结构：布尔数组布尔数组FP，a，使得，使得FP，a为真的条件是，为真的条件是，当且仅当当且仅当a FIRS

31、TVT(P)。开始时，按上述的。开始时，按上述的规则规则(1)对每个数组元素对每个数组元素FP，a赋初值。赋初值。栈栈STACK，把所有初值为真的数组元素，把所有初值为真的数组元素FP，a的符号对的符号对(P，a)全都放在全都放在STACK之中。之中。构造集合构造集合FIRSTVT(P) 的算法的算法1. 若有产生式若有产生式Pa或或PQa，则，则a FIRSTVT(P)；（直接从产生式看）（直接从产生式看）2. 若若a FIRSTVT(Q)，且有产生式，且有产生式PQ，则，则a FIRSTVT(P)。n运算：运算：如果栈如果栈STACK不空，就将顶项逐出，记此不空，就将顶项逐出，记此项为项为

32、(Q，a)。对于每个形如。对于每个形如PQ 的产生式，若的产生式，若FP，a为假，则变其值为真为假，则变其值为真且将且将(P，a)推进推进STACK栈。栈。上述过程必须上述过程必须一直重复一直重复，直至栈，直至栈STACK拆拆空为止。空为止。1. 若有产生式若有产生式Pa或或PQa，则，则a FIRSTVT(P)；（直接从产生式看）（直接从产生式看）2. 若若a FIRSTVT(Q)，且有产生式，且有产生式PQ，则，则a FIRSTVT(P)。构造集合构造集合FIRSTVT(P) 的算法的算法n程序程序(包括一个过程和主程序包括一个过程和主程序)：PROCEDURE INSERT(P，a)；I

33、F NOT FP，a THENBEGIN FP，a:=TRUE； 把把(P，a)下推进下推进STACK栈栈 END；构造集合构造集合FIRSTVT(P) 的算法的算法1. 若有产生式若有产生式P a或或PQa，则，则a FIRSTVT(P)；（直；（直接从产生式看）接从产生式看）2. 若若a FIRSTVT(Q)，且有产生式，且有产生式PQ，则，则a FIRSTVT(P)。主程序：主程序：BEGIN FOR 每个非终结符每个非终结符P和终结符和终结符a DO FP，a:=FALSE； FOR 每个形如每个形如Pa或或PQa的产生式的产生式 DO INSERT(P，a)； WHILE STACK

34、 非空非空 DOBEGIN 把把STACK的顶项，记为的顶项，记为(Q，a)，上托出去；，上托出去； FOR 每条形如每条形如PQ的产生式的产生式 DOINSERT(P，a)；END OF WHILE；END1. 若有产生式若有产生式Pa或或PQa，则，则 a FIRSTVT(P)；2. 若若a FIRSTVT(Q)，且有产生式，且有产生式PQ， 则则 a FIRSTVT(P)。n这个算法的工作结果得到一个二维数组这个算法的工作结果得到一个二维数组F，从它可得任何非终结符从它可得任何非终结符P的的FIRSTVT。FIRSTVT(P)a | FP，a=TRUEn同理，可构造计算同理，可构造计算L

35、ASTVT的算法。的算法。n构造集合构造集合LASTVT(P)的算法。的算法。n按其定义，可用下面两条规则来构造集合按其定义，可用下面两条规则来构造集合LASTVT(P)：1. 若有产生式若有产生式P a或或P aQ，则，则a LASTVT(P)；2. 若若a LASTVT(Q)，且有产生式，且有产生式P Q ，则则a LASTVT(P)。,|)(NTVQVaaQPaPaPLASTVT而或构造集合构造集合LASTVT(P) 的算法的算法n例例: 考虑下面的文法考虑下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i计算文法

36、计算文法G的的FIRSTVT和和LASTVT;1. 若有产生式若有产生式P a或或PQa，则，则a FIRSTVT(P)；（直；（直接从产生式看）接从产生式看）2. 若若a FIRSTVT(Q)，且有产生式，且有产生式PQ，则，则a FIRSTVT(P)。1. 若有产生式若有产生式P a或或P aQ，则，则a LASTVT(P)；2. 若若a LASTVT(Q)，且有产生式，且有产生式P Q ，则，则a LASTVT(P)。+ * ()iE TFP(,)(,*,)(,)(,*,)(iPFIRSTVTiEFIRSTVTiFFIRSTVTiTFIRSTVT+ * ()iE T F P ),)(),

37、*,)(),)(),*,)(iPLASTVTiELASTVTiFLASTVTiTLASTVTn使用每个非终结符使用每个非终结符P的的FIRSTVT(P)和和LASTVT(P)，就，就能够构造文法能够构造文法G的优先关系表。的优先关系表。构造优先关系表的算法构造优先关系表的算法是：是：n通过检查通过检查G的每个产生式的每个候选式，可找出所有满的每个产生式的每个候选式，可找出所有满足足a b的终结符对；的终结符对；n通过检查每个产生式的候选式确定满足关系通过检查每个产生式的候选式确定满足关系 和和 的的所有终结符对：所有终结符对：假定有个产生式的一个候选形为假定有个产生式的一个候选形为 aP 那么

38、，对任何那么，对任何b FIRSTVT(P)，有，有 a b。假定有个产生式的一个候选形为假定有个产生式的一个候选形为 Pb 那么，对任何那么，对任何a LASTVT(P)，有，有 a b。构造优先关系表的算法构造优先关系表的算法如果考虑如果考虑#，则，则考虑句型考虑句型#S#FOR 每条产生式每条产生式PX1X2Xn DO FOR i:=1 TO n-1 DOBEGIN IF Xi和和Xi+1均为终结符均为终结符 THEN 置置Xi Xi+1 IF i n-2且且Xi和和Xi+2都为终结符都为终结符 但但Xi+1为非终结符为非终结符 THEN 置置Xi Xi+2； IF Xi为终结符而为终结

39、符而Xi+1为非终结符为非终结符 THENFOR FIRSTVT(Xi+1)中的每个中的每个a DO 置置 Xi a； IF Xi为非终结符而为非终结符而Xi+1为终结符为终结符 THEN FOR LASTVT(Xi)中的每个中的每个a DO 置置 a Xi+1 ENDn例例: 考虑下面的文法考虑下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i1. 计算文法计算文法G的的FIRSTVT和和LASTVT;2. 构造优先关系表构造优先关系表;3. G是算符优先文法吗是算符优先文法吗?(,)(,*,)(,)(,*,)(iPF

40、IRSTVTiEFIRSTVTiFFIRSTVTiTFIRSTVT),)(),*,)(),)(),*,)(iPLASTVTiELASTVTiFLASTVTiTLASTVT (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i+ +* * ( () )i i+ +* * ( () )i iG结论结论: G是算符优先文法是算符优先文法q G的算符优先关系表的算符优先关系表第五章第五章 语法分析语法分析自下而上分析自下而上分析n自下而上分析的基本问题自下而上分析的基本问题n算符优选分析算法算符优选分析算法p计算计算FIRSTVT(P)FIRSTVT(

41、P)和和LASTVT(P)LASTVT(P)集合集合p构造算符优先关系表构造算符优先关系表nLRLR分析法分析法n可归约串，句型，短语，直接短语，句柄，可归约串，句型，短语，直接短语，句柄，规范归约。规范归约。n一个文法一个文法G G的句型的的句型的素短语素短语是指这样一个短是指这样一个短语，语，它至少含有一个终结符它至少含有一个终结符，并且，除它，并且，除它自身之外自身之外不再含任何更小的素短语不再含任何更小的素短语。n最左素短语最左素短语是指处于句型最左边的那个素是指处于句型最左边的那个素短语。短语。n考虑下面的文法考虑下面的文法G(E)： (1) EE+T | T (2) TT*F |

42、F (3) FP F | P (4) P(E) | iEEF+*TiFTFTP+ETP对于句型：对于句型：T+F*P+i短语：短语：直接短语：直接短语：句柄：句柄：素短语：素短语：最左素短语：最左素短语：, T+F*P+iT, F, P, F*P, iT+F*PT, F, P, iTF*P, iF*Pn算符优先文法句型算符优先文法句型(括在两个之间括在两个之间)的一般的一般形式写成：形式写成： #N1a1N2a2NnanNn+1#其中，每个其中，每个ai都是终结符，都是终结符，Ni是可有可无的非是可有可无的非终结符。终结符。n定理：定理：一个算符优先文法一个算符优先文法G的任何句型的的任何句型

43、的最最左素短语左素短语是满足如下条件的最左子串是满足如下条件的最左子串 NjajNiaiNi+1， aj-1 aj aj aj+1，ai-1 ai ai ai+1n使用一个符号栈使用一个符号栈S，用它寄存终结符和非终结，用它寄存终结符和非终结符，符，k代表符号栈代表符号栈S的使用深度。的使用深度。 k:=1;Sk:=#;REPEAT 把下一个输入符号读进把下一个输入符号读进a中；中； IF Sk VT THEN j:=k ELSE j:=k-1;WHILE Sj a DOBEGIN REPEAT Q:=Sj; IF Sj-1 VT THEN j:=j-1 ELSE j:=j-2 UNTIL S

44、j Q; 把把Sj+1Sk归约为某个归约为某个N； k:=j+1; Sk:=N END OF WHILE; IF Sj a OR Sj a THEN BEGIN k:=k+1;Sk:=a END ELSE ERROR /*调用出错诊察程序调用出错诊察程序*/ UNTIL a=#自左至右，终结符对终结符，非自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符对非终结符，而且对应的终结符相同。终结符相同。 N X1 X2 Xk-j Sj+1 Sj+2 Skn在算法的工作过程中，若出现在算法的工作过程中，若出现j减减1后的值后的值小于等于小于等于0时，则意味着输入串有错。在时，则意味着输入

45、串有错。在正确的情况下，算法工作完毕时，符号栈正确的情况下，算法工作完毕时，符号栈S应呈现：应呈现：# N #。n由于非终结符对归约没有影响，因此，非由于非终结符对归约没有影响，因此，非终结符根本可以不进符号栈终结符根本可以不进符号栈S。n对于文法的句子来说，它的算符优先对于文法的句子来说，它的算符优先分析的结果分析的结果(移进归约所得到的分析移进归约所得到的分析树树)就是语法树。就是语法树。 A.正确正确 B.错误错误 答案：答案：B自左至右，终结符对终结符，非自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符对非终结符，而且对应的终结符相同。终结符相同。 N X1 X2 Xk-

46、j Sj+1 Sj+2 Skn算符优先分析一般并不等价于规范归约。算符优先分析一般并不等价于规范归约。EE+*iTP+iPiPiPEEF+*TiFTFTP+ETiFPiPiPn考虑下面的文法考虑下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i的句子的句子i+i*i+in算符优先分析法特点：算符优先分析法特点：优点优点: : 简单，快速简单，快速缺点缺点: : 可能错误接受非法句子，能力有限可能错误接受非法句子，能力有限. .n算符优先分析法是一种广为应用、行之算符优先分析法是一种广为应用、行之有效的方法。有效的方法。用

47、于分析各类表达式用于分析各类表达式ALGOL 60n把每个终结符把每个终结符 与两个自然数与两个自然数f(f( ) )与与g(g( ) )相对相对应，使得应，使得若若 1 1 2 2，则，则f(f( 1 1) ) g( g( g( 2 2) )f f称为称为入栈优先函数入栈优先函数，g g称为称为比较优先函数比较优先函数。n优点优点: : 便于比较，节省空间；便于比较，节省空间；n缺点缺点: : 原来不存在优先关系的两个终结符，由于自然数相对应，原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的判断。变成可以比较的。要进行一些特殊的判断。n文法文法G(E) G(

48、E) (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i的优先函数如下表的优先函数如下表+* ()i#F2440660G 1355050对于任何无冲突优先关系表都存在优先函数吗对于任何无冲突优先关系表都存在优先函数吗？ A.是是 B.不是不是n有许多优先关系表不存在优先函数有许多优先关系表不存在优先函数，如：，如： 不存在对应的优先函数不存在对应的优先函数f和和g 假定存在假定存在f和和g，则有，则有 f(a)=g(a)，f(a)g(b)， f(b)=g(a)，f(b)=g(b) 导致如下矛盾导致如下矛盾: f(a) g(b) = f(b)

49、= g(a) = f(a)优先函数如果存在，唯一吗？优先函数如果存在，唯一吗？ A.是是 B.不是不是G如果优先函数存在，则不唯一如果优先函数存在，则不唯一(无穷多无穷多)n如果优先函数存在如果优先函数存在，则可以通过以下三个步，则可以通过以下三个步骤从优先表骤从优先表构造优先函数构造优先函数: :1 1 画图：画图：对于每个终结符对于每个终结符a a，令其对应两个符号，令其对应两个符号f fa a和和g ga a，画一以所有符号和为结点的方向图。如果，画一以所有符号和为结点的方向图。如果a ba b，则从，则从f fa a画一条弧至画一条弧至g gb b，如果，如果a ba b，则画一条弧从

50、则画一条弧从g gb b至至f fa a 。2 2 数数：数数：对每个结点都赋予一个数，此数等于从对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点该结点出发所能到达的结点( (包括出发点自身包括出发点自身) )。赋给赋给f fa a的数作为的数作为f(a)f(a)，赋给，赋给g ga a的数作为的数作为g(a)g(a)。3 3 验证：验证：检查所构造出来的函数检查所构造出来的函数f f和和g g是否与原来是否与原来的关系矛盾。若没有矛盾，则的关系矛盾。若没有矛盾，则f f和和g g就是要求的优就是要求的优先函数，若有矛盾，则不存在优先函数。先函数，若有矛盾，则不存在优先函数。n例例: