语法分析自下而上分析ppt课件

1、第五章第五章 语法分析语法分析自下而上分析自下而上分析n自上而下分析法自上而下分析法(Top-down)(Top-down)n自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)n语法分析的方法：语法分析的方法：n自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)n 根本思想：从输入串开场，逐渐进展根本思想：从输入串开场，逐渐进展“归约归约，直到文法的开场符号。即从树末端开场，直到文法的开场符号。即从树末端开场，构造语法树。所谓归约，是指根据文法的产构造语法树。所谓归约，是指根据文法的产生式规那么，把产生式的右部交换成左部符生式规那么，把产生式的右部交

2、换成左部符号。号。n 算符优先分析法：按照算符的优先关系和算符优先分析法：按照算符的优先关系和结合性质进展语法分析。适宜分析表达式。结合性质进展语法分析。适宜分析表达式。n LR LR分析法：规范归约分析法：规范归约5.1.1 5.1.1 归约归约n采用采用“移进归约思想进展自下而上分析。移进归约思想进展自下而上分析。n根本思想：用一个存放符号的先进后出栈，根本思想：用一个存放符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶把输入符号一个一个地移进到栈里，当栈顶构成某个产生式的候选式时，即把栈顶的这构成某个产生式的候选式时，即把栈顶的这一部分交换成一部分交换成( (归约为归约为) )该

3、产生式的左部符号。该产生式的左部符号。步步骤骤: :1 12 23 34 45 56 67 78 89 91 10 0动动作作: : 进进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分析树和语法树不一定一致。分析树和语法树不一定一致。自下而上分析过程：边输入单词符号，边自下而上分析过程：边输入单词符号，

4、边归约。归约。中心问题：识别可归约串中心问题：识别可归约串5.1.2 5.1.2 规范归约规范归约n定义：令定义：令G G是一个文法，是一个文法，S S是文法的开场符是文法的开场符号，假定号，假定是文法是文法G G的一个句型，假设的一个句型，假设有有n 且且n AS*A那么那么称是句型称是句型相对于非终结符相对于非终结符A A的的短语。短语。特别是，假设有特别是，假设有A A, ,那么称那么称是句型是句型相对于规那么相对于规那么A A 的直接短语。的直接短语。一个句型的最左直接短语称为该句型的句一个句型的最左直接短语称为该句型的句柄。柄。n在一个句型对应的在一个句型对应的语法树中，以某非语法树

5、中，以某非终结符为根的两代终结符为根的两代以上的子树的一切以上的子树的一切末端结点从左到右末端结点从左到右陈列就是相对于该陈列就是相对于该非终结符的一个短非终结符的一个短语，假设子树只需语，假设子树只需两代，那么该短语两代，那么该短语就是直接短语。就是直接短语。EFFTTTi1+*EFi3i2n定义：假定定义：假定是文法是文法G G的一个句子，我们的一个句子，我们称序列称序列n n n， n-1n-1， ，0 0n 是的一个规范归约，假设此序列满足：是的一个规范归约，假设此序列满足：n 1 1 n= n= n 2 2 0 0为文法的开场符号，即为文法的开场符号，即0=S0=Sn 3 3 对任何

6、对任何i i，0 0 i i n n， i-1i-1是是从从i i经把句柄交换成为相应产生式左部经把句柄交换成为相应产生式左部符号而得到的。符号而得到的。把上例倒过来写，那么得到：把上例倒过来写，那么得到：S S aAcBe aAcBe aAcde aAcde aAbcde aAbcde abbcde abbcde 显然这是一个最右推导。显然这是一个最右推导。规范归约是关于是一个最右推导的逆过程规范归约是关于是一个最右推导的逆过程最左归约最左归约 规范推导规范推导由规范推导推出的句型称为规范句型。由规范推导推出的句型称为规范句型。5.2 5.2 算符优先分析算符优先分析n四那么运算的优先规那么

7、：四那么运算的优先规那么： n先乘除后加减，同级从左到右先乘除后加减，同级从左到右n思索二义文法文法思索二义文法文法G(E)G(E)：nG(E)G(E)： E E i| E+E|E-E|E i| E+E|E-E|E* *E|E/E|(E)E|E/E|(E)n它的句子有几种不同的规范规约。它的句子有几种不同的规范规约。n归约即计算表达式的值。归约顺序不同，归约即计算表达式的值。归约顺序不同，那么计算的顺序也不同，结果也不一样。那么计算的顺序也不同，结果也不一样。n假设规定算符的优先次序，并按这种规定假设规定算符的优先次序，并按这种规定进展归约，那么归约过程是独一的。进展归约，那么归约过程是独一的

8、。n起决议作用的是相邻的两个算符之间的优起决议作用的是相邻的两个算符之间的优先关系。先关系。n所谓算符优先分析法就是定义算符之间的所谓算符优先分析法就是定义算符之间的某种优先关系，借助于这种关系寻觅某种优先关系，借助于这种关系寻觅“可可归约串和进展归约。归约串和进展归约。n首先必需定义任何两个能够相继出现的终首先必需定义任何两个能够相继出现的终结符结符a a与与b b的优先关系的优先关系n 三种关系三种关系na a b a b a的优先级低于的优先级低于b bna a b a b a的优先级等于的优先级等于b bna a b a b a的优先级高于的优先级高于b bn留意：与数学上的留意：与数

9、学上的=不同，不同，a a b b并不意并不意味着味着b b a a5.2.1 算符优先文法及优先表构造算符优先文法及优先表构造n一个文法，假设它的任一产生式的右部都一个文法，假设它的任一产生式的右部都不含两个相继不含两个相继(并列并列)的非终结符，即不含的非终结符，即不含如下方式的产生式右部：如下方式的产生式右部：nQRn 那么我们称该文法为算符文法。那么我们称该文法为算符文法。n商定：商定：na、b代表恣意终结符；代表恣意终结符；nP、Q、R代表恣意非终结符；代表恣意非终结符；n代表由终结符和非终结符组成的恣意代表由终结符和非终结符组成的恣意序列，包括空字。序列，包括空字。n假定假定G是一

10、个不含是一个不含-产生式的算符文法。产生式的算符文法。对于任何一对终结符对于任何一对终结符a、b，我们说：，我们说：n1. ab 当且仅当文法当且仅当文法G中含有形如中含有形如Pab或或PaQb的产生式；的产生式；n假设一个算符文法假设一个算符文法G中的任何终结符对中的任何终结符对(a，b)至多只满足下述三关系之一：至多只满足下述三关系之一：nab，ab， abn 那么称那么称G是一个算符优先文法。是一个算符优先文法。2. ab 当且仅当当且仅当G中含有形如中含有形如PaR的产生式，的产生式， 而而R b或或R Qb；3. ab 当且仅当当且仅当G中含有形如中含有形如PRb的产生式，而的产生式

11、，而 R a或或R aQ。n 优先关系表优先关系表+*i()#+*i()#n从算符优先文法从算符优先文法G构造优先关系表的算法。构造优先关系表的算法。n经过检查经过检查G的每个产生式的每个候选式，可的每个产生式的每个候选式，可找出一切满足找出一切满足ab的终结符对。的终结符对。n确定满足关系确定满足关系和和的一切终结符对：的一切终结符对：n首先需求对首先需求对G的每个非终结符的每个非终结符P构造两个集构造两个集合合FIRSTVT(P)和和LASTVT(P)：FIRSTVT Pa PaPQaaVQVTN( ) |,或而,|)(NTVQVaaQPaPaPLASTVT而或q有了这两个集合之后，就可以

12、经过检查每有了这两个集合之后，就可以经过检查每个产生式的候选式确定满足关系个产生式的候选式确定满足关系和和的的一切终结符对。一切终结符对。q假定有个产生式的一个候选形为假定有个产生式的一个候选形为qaPq 那么，对任何那么，对任何bFIRSTVT(P)，有，有 ab。q假定有个产生式的一个候选形为假定有个产生式的一个候选形为qPbq 那么，对任何那么，对任何aLASTVT(P)，有，有 ab。n首先讨论构造集合首先讨论构造集合FIRSTVT(P)的算法。按的算法。按其定义，可用下面两条规那么来构造集合其定义，可用下面两条规那么来构造集合FIRSTVT(P)：n1. 假设有产生式假设有产生式Pa

13、或或PQa，那么，那么aFIRSTVT(P)；n2. 假设假设aFIRSTVT(Q)，且有产生式，且有产生式PQ，那么，那么aFIRSTVT(P)。n数据构造：数据构造：n布尔数组布尔数组FP，a，使得，使得FP，a为真的条为真的条件是，当且仅当件是，当且仅当aFIRSTVT(P)。开场时，。开场时，按上述的规那么按上述的规那么(1)对每个数组元素对每个数组元素FP，a赋初值。赋初值。n栈栈STACK，把一切初值为真的数组元素，把一切初值为真的数组元素FP，a的符号对的符号对(P，a)全都放在全都放在STACK之之中。中。n运算：运算：n假设栈假设栈STACK不空，就将顶项逐出，记不空，就将顶

14、项逐出，记此项为此项为(Q，a)。对于每个形如。对于每个形如nPQn 的产生式，假设的产生式，假设FP，a为假，那么变为假，那么变其值为真且将其值为真且将(P，a)推进推进STACK栈。栈。n上述过程必需不断反复，直至栈上述过程必需不断反复，直至栈STACK拆空为止。拆空为止。n假设把这个算法稍为方式化一点，我们假设把这个算法稍为方式化一点，我们可得如下所示的一个程序可得如下所示的一个程序(包括一个过程包括一个过程和主程序和主程序)：nPROCEDURE INSERT(P，a)；nIF NOT FP，a THENnBEGIN n FP，a:=TRUE；n 把把(P，a)下推进下推进STACK栈

15、栈 nEND；主程序：主程序：BEGIN FOR 每个非终结符每个非终结符P和终结符和终结符a DO FP，a:=FALSE； FOR 每个形如每个形如Pa或或PQa的产生式的产生式 DO INSERT(P，a)； WHILE STACK 非空非空 DOBEGIN 把把STACK的顶项，记为的顶项，记为(Q，a)，上托出，上托出去；去； FOR 每条形如每条形如PQ的产生式的产生式 DOINSERT(P，a)；END OF WHILE；ENDn这个算法的任务结果得到一个二维数组这个算法的任务结果得到一个二维数组F，从它可得任何非终结符从它可得任何非终结符P的的FIRSTVT。nFIRSTVT(

16、P)a | FP，a=TRUEn同理，可构造计算同理，可构造计算LASTVT的算法。的算法。n运用每个非终结符运用每个非终结符P的的FIRSTVT(P)和和LASTVT(P)，就可以构造文法，就可以构造文法G的优先的优先表。构造优先表的算法是：表。构造优先表的算法是：FOR 每条产生式每条产生式PX1X2Xn DO FOR i:=1 TO n-1 DOBEGIN IF Xi和和Xi+1均为终结符均为终结符 THEN 置置XiXi+1 IF in-2且且Xi和和Xi+2都为终结符都为终结符 但但Xi+1为非终结符为非终结符 THEN 置置XiXi+2； IF Xi为终结符而为终结符而Xi+1为非

17、终结符为非终结符 THENFOR FIRSTVT(Xi+1)中的每个中的每个a DO 置置 Xia； IF Xi为非终结符而为非终结符而Xi+1为终结符为终结符 THEN FOR LASTVT(Xi)中的每个中的每个a DO 置置 aXi+1 ENDn例例: 思索下面的文法思索下面的文法G(E)：n (1) EE+T | Tn (2) TT*F | Fn (3) FP F | Pn (4) P(E) | in1. 计算文法计算文法G的的FIRSTVT和和LASTVT;n2. 构造优先关系表构造优先关系表;n3. G是算符优先文法吗是算符优先文法吗?+ * ()iE TFP(,)(,*,)(,)

18、(,*,)(iPFIRSTVTiEFIRSTVTiFFIRSTVTiTFIRSTVT+ * ()iE T F P ),)(),*,)(),)(),*,)(iPLASTVTiELASTVTiFLASTVTiTLASTVT+ +* * ( () )i i+ +* * ( () )i iG结论结论: G是算符优先文法是算符优先文法q G的算符优先关系表的算符优先关系表5.2.2 算符优先分析算法算符优先分析算法n可归约串，句型，短语，直接短语，句柄，可归约串，句型，短语，直接短语，句柄，规范归约。规范归约。n一个文法一个文法G G的句型的素短语是指这样一个短的句型的素短语是指这样一个短语，它至少含有

19、一个终结符，并且，除它语，它至少含有一个终结符，并且，除它本身之外不再含任何更小的素短语。本身之外不再含任何更小的素短语。n最左素短语是指处于句型最左边的那个素最左素短语是指处于句型最左边的那个素短语。短语。n思索下面的文法思索下面的文法G(E)：n (1) EE+T | Tn (2) TT*F | Fn (3) FP F | Pn (4) P(E) | iEEF+*TiFTFTP+ETP句型：句型：T+FT+F* *P+iP+i短语：短语：T+F*P+i, T, F， P, F*P, i, T+F*P直接短语：直接短语：T, F, P, i句柄：句柄：T素短语：素短语： F*P, i最左素短

20、语：最左素短语： F*Pn算符优先文法句型算符优先文法句型(括在两个之间括在两个之间)的普通的普通方式写成：方式写成：n #N1a1N2a2NnanNn+1#n其中，每个其中，每个ai都是终结符，都是终结符，Ni是可有可无的是可有可无的非终结符。非终结符。n定理：一个算符优先文法定理：一个算符优先文法G的任何句型的最的任何句型的最左素短语是满足如下条件的最左子串左素短语是满足如下条件的最左子串 NjajNiaiNi+1，n aj-1ajn aj aj+1，ai-1ain aiai+1n算符优先分析算法算符优先分析算法n运用一个符号栈运用一个符号栈S，用它存放终结符和非终，用它存放终结符和非终结

21、符，结符，k代表符号栈代表符号栈S的运用深度。的运用深度。n1 k:=1;Sk:=#;n2 REPEATn3 把下一个输入符号读进把下一个输入符号读进a中；中；n4 IF SkVT THEN j:=k ELSE j:=k-1;n5 WHILE Sja DOn6 BEGINn7 REPEATn8 Q:=Sj;n9 IF Sj-1VT THEN j:=j-1 ELSE j:=j-2n10 UNTIL SjQ;n11把把Sj+1Sk归约为某个归约为某个N；n12k:=j+1;n13Sk:=Nn14 END OF WHILE;n15 IF Sja OR Sja THENn16 BEGIN k:=k+1

22、;Sk:=a ENDn17 ELSE ERROR /*调用出错诊察程序调用出错诊察程序*/n18 UNTIL a=#n在算法的任务过程中，假设出现在算法的任务过程中，假设出现j减减1后的后的值小于等于值小于等于0时，那么意味着输入串有错。时，那么意味着输入串有错。在正确的情况下，算法任务终了时，符号在正确的情况下，算法任务终了时，符号栈栈S应呈现：应呈现：# N #。n算法的第算法的第11行中的行中的N是指那样一个产生式是指那样一个产生式的左部符号，此产生式的右部和的左部符号，此产生式的右部和Sj+1Sk 构成如下一一对应关系：自构成如下一一对应关系：自左至右，终结符对终结符，非终结符对非左至

23、右，终结符对终结符，非终结符对非终结符，而且对应的终结符一样。由于非终结符，而且对应的终结符一样。由于非终结符对归约没有影响，因此，非终结符终结符对归约没有影响，因此，非终结符根本可以不进符号栈根本可以不进符号栈S。n算符优先分析普通并不等价于规范归约。算符优先分析普通并不等价于规范归约。EE+*iTP+iPiPiPEEF+*TiFTFTP+ETiFPiPiPn算符优先分析法特点：算符优先分析法特点：n优点优点: : 简单，快速简单，快速n缺陷缺陷: : 能够错误接受非法句子，才干有能够错误接受非法句子，才干有限限. .n算符优先分析法是一种广为运用、行之算符优先分析法是一种广为运用、行之有效

24、的方法。有效的方法。n用于分析各类表达式用于分析各类表达式nALGOL 60ALGOL 605.2.3 5.2.3 优先函数优先函数n把每个终结符把每个终结符qq与两个自然数与两个自然数f(f(qq) )与与g(g(qq) )相对应，使得相对应，使得n假设假设qq1 1 qq2 2，那么，那么f(f(qq1) g(1) g(1) g(qq2)2)nf f称为入栈优先函数，称为入栈优先函数，g g称为比较优先函数。称为比较优先函数。n优点优点: :便于比较，节省空间；便于比较，节省空间；n缺陷缺陷: :原来不存在优先关系的两个终结符，由原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比

25、较的。要进展于自然数相对应，变成可以比较的。要进展一些特殊的判别。一些特殊的判别。n文法文法G(E) G(E) n (1) EE+T | T (1) EE+T | Tn (2) TT (2) TT* *F | FF | Fn (3) FP (3) FP F | P F | Pn (4) P(E) | i (4) P(E) | in的优先函数如下表的优先函数如下表+* ()i#F2440660G 1355050n有许多优先关系表不存在优先函数，如：有许多优先关系表不存在优先函数，如：abab 不存在对应的优先函数不存在对应的优先函数f和和g 假定存在假定存在f和和g，那么有，那么有 f(a)=g

26、(a)，f(a)g(b)， f(b)=g(a)，f(b)=g(b) 导致如下矛盾导致如下矛盾: f(a) g(b) = f(b) = g(a) = f(a)假设优先函数存在，那么不独一假设优先函数存在，那么不独一(无穷多无穷多)n假设优先函数存在，那么可以经过以下三个假设优先函数存在，那么可以经过以下三个步骤从优先表构造优先函数步骤从优先表构造优先函数: :n1 1 对于每个终结符对于每个终结符a a，令其对应两个符号，令其对应两个符号fafa和和gaga，画一以一切符号和为结点的方向图。，画一以一切符号和为结点的方向图。假设假设a ab b，那么从，那么从fafa画一条弧至画一条弧至gbgb

27、，假设，假设a ab b，那么画一条弧从，那么画一条弧从gbgb至至fa fa 。n2 2 对每个结点都赋予一个数，此数等于从该对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点结点出发所能到达的结点( (包括出发点本身包括出发点本身) )。赋给赋给fafa的数作为的数作为f(a)f(a)，赋给，赋给gaga的数作为的数作为g(a)g(a)。n3 3 检查所构造出来的函数检查所构造出来的函数f f和和g g能否与原来的能否与原来的关系矛盾。假设没有矛盾，那么关系矛盾。假设没有矛盾，那么f f和和g g就是要就是要求的优先函数，假设有矛盾，那么不存在优求的优先函数，假设有矛盾，那么不存在

28、优先函数。先函数。n如今必需证明：假设如今必需证明：假设ab，那么，那么f(a)g(b)；假设；假设ab，那么，那么f(a) g(b)。n第一个关系可从函数的构造直接获得。由第一个关系可从函数的构造直接获得。由于，假设于，假设ab，那么既有从，那么既有从fa到到gb的弧，的弧，又有从又有从gb到到fa的弧。所以，的弧。所以，fa和和gb所能到所能到达的结是全同的。达的结是全同的。n至于至于ab和和ab的情形，只须证明其一。的情形，只须证明其一。n假设假设ab，那么有从，那么有从fa到到gb的弧。也就的弧。也就是，是，gb能到达的任何结能到达的任何结fa也能到达。因也能到达。因此，此，f(a)

29、g(b)。n我们所需证明的是，在这种情况下，我们所需证明的是，在这种情况下，f(a)g(b)不应成立。不应成立。n我们将指出，假设我们将指出，假设f(a)g(b)，那么根本，那么根本不存在优先函数。假假设不存在优先函数。假假设f(a)g(b)，那，那么必有如下的回路：么必有如下的回路： 因此有因此有ab, a1b, a1b1, , ambm, abm对任何优先函数对任何优先函数f和和g来说，必定有来说，必定有f(a) g(b) f(a1) g(b1) f(am) g(bm) f(a)从而导致从而导致f(a) f(a)，产生矛盾。因此，不存在，产生矛盾。因此，不存在优先函数优先函数f和和g。fa

30、1fafamgb1gbgbmn例例: :取前面文法取前面文法G(E) G(E) n (1) EE+T | T (1) EE+T | Tn (2) TT (2) TT* *F | FF | Fn (3) FP (3) FP F | P F | Pn (4) P(E) | i (4) P(E) | in的终结符的终结符+ +，* *，i i+* i+* if+f*ffig+g*ggi+* if2447g13665.3 LR分析法分析法nLR分析法：分析法：1965年年 由由Knuth提出提出分析表产分析表产生器生器文法文法分析表分析表输入输入输出输出 产生分析表产生分析表 LR分析器任务分析器任务

31、LR分析总分析总 控程控程 序序分析表分析表主要引见主要引见1. 总控程序总控程序(LR分析器分析器)的处置思想的处置思想2. LR分析表的构造方法及原理分析表的构造方法及原理5.3.1 LR分析器分析器n规范归约的关键问题是寻规范归约的关键问题是寻觅句柄觅句柄.n“历史：已移入符号栈历史：已移入符号栈的内容的内容n“展望：根据产生式推展望：根据产生式推测未来能够遇到的输入符测未来能够遇到的输入符号号n“现实：当前的输入符现实：当前的输入符号号 Xn 输入串 X2 a# X1 #nLR分析方法：把分析方法：把历史历史及及展望展望综合笼统综合笼统成形状；由栈顶的形状和现行的输入符号成形状；由栈顶

32、的形状和现行的输入符号独一确定每一步任务独一确定每一步任务 LR分析分析程程 序序形状形状符号符号SmXmS1X1S0#分析栈分析栈 action goto LR分析表分析表a1a2ai an#输入串输入串 输出输出nLR分析器的中心是一张分析表：分析器的中心是一张分析表：nACTIONs，a：当形状：当形状s面临输入符号面临输入符号a时，应采取什么动作时，应采取什么动作.nGOTOs，X：形状：形状s面对文法符号面对文法符号X时，时，下一形状是什么下一形状是什么n每一项每一项ACTIONs，a所规定的四种动作所规定的四种动作:n1. 移进移进 把把(s，a)的下一形状的下一形状s和输入符号和

33、输入符号a推进栈，下一输入符号变成现行输入符号推进栈，下一输入符号变成现行输入符号.n2. 归约归约 指用某产生式指用某产生式A进展归约进展归约. 假假假假设设的长度为的长度为r， 归约动作是，归约动作是， 去除栈顶去除栈顶r个个项，使形状项，使形状sm-r变成栈顶形状，然后把变成栈顶形状，然后把(sm-r, A)的下一形状的下一形状s=GOTOsm-r, A和文法符和文法符号号A推进栈推进栈.n3. 接受接受 宣布分析胜利，停顿分析器任务宣布分析胜利，停顿分析器任务.n4. 报错报错n分析开场时分析开场时:n形状形状 已归约串已归约串 输入串输入串n (s0， #， a1a2 an #)n以

34、后每步的结果可以表示为以后每步的结果可以表示为:n(s0 s1 sm ，# X1 Xm ，aiai+1 an #)(s0 s1 sm ，# X1 Xm ，aiai+1 an #)分析器根据分析器根据ACTION(sm , ai)确定下一步动作确定下一步动作1. 假设假设ACTION(sm , ai)为移进，且为移进，且s，那么三，那么三元式格局变为元式格局变为: (s0 s1 sms ，# X1 Xm ai，ai+1 an #)2. 假设假设ACTION(sm , ai)为按为按A归约，三元归约，三元式变为式变为: (s0 s1 sm-rs ，# X1 Xm-rA ，aiai+1 an #)此

35、处此处, s=GOTO(sm-r, A), r为为的长度的长度, = Xm-r+1 Xm3. 假设假设ACTION(sm , ai)为为接受接受，那么三元式，那么三元式不再变化，变化过程终止，宣布分析胜利不再变化，变化过程终止，宣布分析胜利.4. 假设假设ACTION(sm , ai)为为报错报错，那么三元式，那么三元式变化过程终止，报告错误变化过程终止，报告错误.LR分析器例如：分析器例如：文法文法G(E)： (1) EET(2) ET(3) TT*F(4) TF(5) F(E)(6) FiACTIONGOTO状态状态i+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4

36、r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5其其LR分析表为分析表为:n假定输入串为假定输入串为i*i+i， LR分析器的任务过程分析器的任务过程:n步骤步骤形状形状符号符号输入串输入串n(1)0#i*i+i#n(2)05#i*i+i#n(3)03#F*i+i#n(4)02#T*i+i#n(5)027#T*i+i#n(6)0275#T*i+i#n(7)02710#T*F+i#n(8)02#T+i#n(9)01#E+i#n(10)016#E+i#步骤步骤形状形状符号符号输入串输入串(11)0165#E

37、+i#(12)0163#E+F#(13)0169#E+T#(14)01#E#(15) 接受接受EE*TT+FFFiiin定义：对于一个文法，假设可以构造一张定义：对于一个文法，假设可以构造一张分析表，使得它的每个入口均是独一确定分析表，使得它的每个入口均是独一确定的，那么这个文法就称为的，那么这个文法就称为LR文法。文法。n定义：一个文法，假设能用一个每步顶多定义：一个文法，假设能用一个每步顶多向前检查向前检查k个输入符号的个输入符号的LR分析器进展分分析器进展分析，那么这个文法就称为析，那么这个文法就称为LR(k)文法文法.n非非LR构造构造nLR文法不是二义的，二义文法一定不会是文法不是二

38、义的，二义文法一定不会是LR的。的。n S iCtS | iCtSeSn 栈栈 输入输入n iCtS e#5.3.2 LR(0)工程集族和工程集族和LR(0)分分析表的构造析表的构造n字的前缀：是指字的恣意首部，如字字的前缀：是指字的恣意首部，如字abc的的前缀有前缀有，a，ab，abcn活前缀：是指规范句型的一个前缀，这种前活前缀：是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即，对于规范缀不含句柄之后的任何符号。即，对于规范句型句型，为句柄，假设为句柄，假设=u1u2ur，那么符号串，那么符号串u1u2ui(1ir)是是的活前缀。的活前缀。(必必为终结符串为终结符串)n对于一个文

39、法对于一个文法G, 可以构造一个可以构造一个DFA,它能识它能识别别G的一切活前缀的一切活前缀.n文法文法G的每个产生式的右部添加一个圆的每个产生式的右部添加一个圆点称为点称为G的的LR(0)工程工程n如如:AXYZ有四个工程：有四个工程：nA.XYZ AX.YZ AXY.Z AXYZ. nA . 称为称为归约工程归约工程n归约工程归约工程 S . 称为称为接受工程接受工程nA .a (aVT) 称为称为移进工程移进工程n A .B (BVN) 称为称为待约工程待约工程.n文法文法G(S)n SEn EaA|bBn AcA|dn BcB|d n 该文法的工程有：该文法的工程有：n1. SE2.

40、 SE3. EaA 4. EaA5. EaA6. AcAn7. AcA8. AcA9. Ad 10. Ad11. EbB12. EbBn13. EbB14. BcB15. BcB 16. BcB17. Bd18. Bdn构造识别文法一切活前缀的构造识别文法一切活前缀的NFA方法方法n 1. 假设形状假设形状i为为XX1 Xi-1.Xi Xn ，n 形状形状j为为XX1 Xi-1Xi .Xi+1 Xn ，n 那么从形状那么从形状i画一条标志为画一条标志为Xi的有向边到形的有向边到形状状j；n 2. 假设形状假设形状i为为X .A ，A为非终结符，为非终结符，n 那么从形状那么从形状i画一条画一条

41、边到一切形状边到一切形状A.。n把识别文法一切活前缀的把识别文法一切活前缀的NFA确定化。确定化。n构成识别一个文法活前缀的构成识别一个文法活前缀的DFA的工程集的工程集(形状形状)的全体称为文法的的全体称为文法的LR(0)工程集规范工程集规范族。族。678910453121112131415161817 a AEbBBcAcd识别活前缀的识别活前缀的NFA识别活前缀的识别活前缀的DFA0: SE EaA EbB 4: AcA AcA Ad 2: EaA AcA Ad1: SE3: EbB BcB Bd5: BcB BcB Bd 11: Bd9: BcB7: EbB10: Ad6: EaA 8

42、: AcAccbEadAccdddBAB有效工程有效工程n我们说工程我们说工程A 1.2对活前缀对活前缀1是是有效的，其条件是存在规范推导有效的，其条件是存在规范推导21R*RASq在任何时候，分析栈中的活前缀在任何时候，分析栈中的活前缀X1X2 Xm的有效工程集正是栈顶形状的有效工程集正是栈顶形状Sm所代表的所代表的那个集合。也正是从识别活前缀的那个集合。也正是从识别活前缀的DFA的初的初态出发，读出态出发，读出X1X2 Xm后到达的那个工后到达的那个工程集程集(形状形状)。n结论结论: 假设工程假设工程A .B对活前缀对活前缀=是有效的且是有效的且B 是一个产生式，是一个产生式，那么工程那

43、么工程B .对对=也是有效的。也是有效的。BASRR* 所以，所以，B .对对=也是有效的。也是有效的。RRRRBBAS*R设设，那么，那么n文法文法G(S)n SEn EaA|bBn AcA|dn BcB|d n思索：思索：n 工程：工程：B c.B B . cB B . dn 活前缀：活前缀：bcnS E bB bcBnS E bB bcB bccBnS E bB bcB bcdLR(0)工程集规范族的构造工程集规范族的构造n假定文法假定文法G是一个以是一个以S为开场符号的文法，为开场符号的文法，我们构造一个我们构造一个G，它包含了整个，它包含了整个G，但，但它引进了一个不出如今它引进了一

44、个不出如今G中的非终结符中的非终结符S，并加进一个新产生式，并加进一个新产生式SS，而这，而这个个S是是G的开场符号。那么，我们称的开场符号。那么，我们称G是是G的拓广文法。这样，便会有一个的拓广文法。这样，便会有一个仅含工程仅含工程SS.的形状，这就是独一的的形状，这就是独一的“接受态。接受态。n假定假定I是文法是文法G的任一工程集，定义和构的任一工程集，定义和构造造I的闭包的闭包CLOSURE(I)如下：如下：n1. I的任何工程都属于的任何工程都属于CLOSURE(I)；n2. 假设假设AB属于属于CLOSURE(I)，那么，对任何关于那么，对任何关于B的产生式的产生式B，工，工程程B也

45、属于也属于CLOSURE(I)；n3. 反复执行上述两步骤直至反复执行上述两步骤直至CLOSURE(I) 不再增大为止。不再增大为止。n为了识别活前缀，我们定义一个形状转换为了识别活前缀，我们定义一个形状转换函数函数GO是一个形状转换函数。是一个形状转换函数。I是一个工是一个工程集，程集，X是一个文法符号。函数值是一个文法符号。函数值GO(I，X)定义为：定义为：nGO(I，X)CLOSURE(J)n 其中其中n J任何形如任何形如AX的工程的工程| A X属于属于I。n直观上说，假设直观上说，假设I是对某个活前缀是对某个活前缀 有效有效的工程集，那么，的工程集，那么，GO(I，X)便是对便是

46、对 X 有效的工程集。有效的工程集。n文法文法G(S)n SEn EaA|bBn AcA|dn BcB|d nI0=SE, EaA, EbBn GO(I0, E)= closure(J)=closure(SE)n= SE = I1n GO(I0, a)= closure(J)=closure(EaA)n = EaA, AcA, Ad )=I2n GO(I0, b)= closure(J)=closure (E b.B) n=E b.B, B.cB, B.d= I3n构造文法构造文法G的拓广文法的拓广文法G的的LR(0)工程集工程集规范族算法：规范族算法：nPROCEDURE ITEMSETS(

47、G)；nBEGINnC:=CLOSURE(SS)；nREPEATn FOR C中每个工程集中每个工程集I和和G的每个的每个符号符号X DOn IF GO(I，X)非空且不属于非空且不属于C THENn 把把GO(I，X)放入放入C族中族中;nUNTIL C 不再增大不再增大nENDn转换函数转换函数GO把工程集衔接成一个把工程集衔接成一个DFA转换转换图图.0: SE EaA EbB 4: AcA AcA Adc5: BcB BcB Bd c3: EbB BcB Bdb1: SEE2: EaA AcA Ada11: Bdd8: AcAAccd10: Addd9: BcBB6: EaA A7:

48、EbBBLR(0)分析表的构造分析表的构造n假假设一个文法假假设一个文法G的拓广文法的拓广文法G的活前的活前缀识别自动机中的每个形状缀识别自动机中的每个形状(工程集工程集)不存不存在下述情况：在下述情况：n 1) 既含移进工程又含归约工程，既含移进工程又含归约工程，n 2) 含有多个归约工程含有多个归约工程n 那么称那么称G是一个是一个LR(0)文法。文法。构造构造LR(0)分析表的算法分析表的算法n令每个工程集令每个工程集Ik的下标的下标k作为分析器的形状，作为分析器的形状，包含工程包含工程SS的集合的集合Ik的下标的下标k为分析为分析器的初态。器的初态。n分析表的分析表的ACTION和和G

49、OTO子表构造方法：子表构造方法：n1. 假设工程假设工程Aa属于属于Ik且且GO(Ik, a)Ij，a为终结符，那么置为终结符，那么置ACTIONk,a 为为“sj。n2. 假设工程假设工程A属于属于Ik，那么，对任何终，那么，对任何终结符结符a(或终了符或终了符#)，置，置ACTIONk,a为为 “rj(假定产生式假定产生式A是文法是文法G的第的第j个产生式个产生式)。n3. 假设工程假设工程SS属于属于Ik，那么置，那么置ACTIONk,#为为 “acc。n4. 假设假设GO(Ik,A)Ij，A为非终结符，那么置为非终结符，那么置GOTOk,A=j。n5. 分析表中凡不能用规那么分析表中

50、凡不能用规那么1至至4填入信息的填入信息的空白格均置上空白格均置上“报错标志。报错标志。nLR(0)分析表为分析表为A C T IO NG O T O状状 态态abcd#EAB0s2s311acc2s4s1063s5s1174s4s1085s5s116r1r1r1r1r197r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r6n例例: 按上表对按上表对acccd进展分析进展分析n步骤步骤形状形状符号符号输入串输入串n10#acccd#n202#acccd#n3024#acccd#n40244#acccd#n502444#acccd#n

51、60244410 #acccd#n7024448#acccA#n802448#accA#n90248#acA#n10026#aA#n1101#E#5.3.3 SLR分析表的构造分析表的构造nLR(0)文法太简单，没有适用价值文法太简单，没有适用价值.n假定一个假定一个LR(0)规范族中含有如下的一个工程集规范族中含有如下的一个工程集(形状形状)IXb，A，B。FOLLOW(A)和和FOLLOW(B)的交集为的交集为，且不包，且不包含含b，那么，当形状，那么，当形状I面临任何输入符号面临任何输入符号a时，可以时，可以:n1. 假设假设a=b，那么移进；，那么移进；n2. 假设假设aFOLLOW(

52、A)，用产生式，用产生式A进展归进展归约；约；n3. 假设假设aFOLLOW(B)，用产生式，用产生式B进展归进展归约；约；n4. 此外，报错。此外，报错。n假定假定LR(0)规范族的一个工程集规范族的一个工程集I=A1a11，A2a22，Amamm，B1，B2，Bn 假设集合假设集合a1，am，FOLLOW(B1)，FOLLOW(Bn)两两不相两两不相交交(包括不得有两个包括不得有两个FOLLOW集合有集合有#)，那么：，那么：n1. 假设假设a是某个是某个ai，i=1,2,m，那么移进；，那么移进；n2. 假设假设aFOLLOW(Bi)，i=1,2,n，那么用，那么用产生式产生式Bi进展归

53、约；进展归约；n3. 此外，报错。此外，报错。n冲突性动作的这种处理方法叫做冲突性动作的这种处理方法叫做SLR(1)处理处理方法。方法。构造构造SLR(1)分析表方法分析表方法:首先把首先把G拓广为拓广为G，对，对G构造构造LR(0)工程工程集规范族集规范族C和活前缀识别自动机的形状转和活前缀识别自动机的形状转换函数换函数GO.然后运用然后运用C和和GO，按下面的算法构造，按下面的算法构造SLR分析表：分析表：令每个工程集令每个工程集Ik的下标的下标k作为分析器的形状，作为分析器的形状，包含工程包含工程SS的集合的集合Ik的下标的下标k为分析为分析器的初态。器的初态。分析表的分析表的ACTIO

54、N和和GOTO子表构造方法：子表构造方法：1. 假设工程假设工程Aa属于属于Ik且且GO(Ik,a)=Ij，a为终结符，那么置为终结符，那么置ACTIONk,a为为 “sj；2. 假设工程假设工程A属于属于Ik，那么，对任何终，那么，对任何终结符结符a，aFOLLOW(A)，置，置ACTIONk,a为为 “rj；其中，假定；其中，假定A为文法为文法G的第的第j个产生式；个产生式；3. 假设工程假设工程SS属于属于Ik，那么置，那么置ACTIONk,#为为“acc;4. 假设假设GO(Ik,A)Ij，A为非终结符，那么为非终结符，那么置置GOTOk,A=j；5. 分析表中凡不能用规那么分析表中凡

55、不能用规那么1至至4填入信息的填入信息的空白格均置上空白格均置上“出错标志。出错标志。n按上述方法构造出的按上述方法构造出的ACTION与与GOTO表表假设不含多重入口，那么称该文法为假设不含多重入口，那么称该文法为SLR(1)文法。文法。n运用运用SLR表的分析器叫做一个表的分析器叫做一个SLR分析器。分析器。n每个每个SLR(1)文法都是无二义的。但也存在文法都是无二义的。但也存在许多无二义文法不是许多无二义文法不是SLR(1)的的.n例例5.11 调查下面的拓广文法：调查下面的拓广文法：n(0) SEn(1) EE+Tn(2) ETn(3) TT*Fn(4) TFn(5) F(E)n(6

56、) Fin这个文法的这个文法的LR(0)工程集规范族为：工程集规范族为：I0: SE EE+T ET TT*F TT*F TF F (E) FiI1: SE EE+TI2: ET TT*FI3: TF I4: F(E) EE+T ET TT*F TF F (E) FiI5 :FiI6: EE+T TT*F TF F(E) FiI7: TT*F F(E) FiI8: F(E) EE+TI9: EE+T TT*FI10: TT*FI11: F(E)nI1、I2和和I9都含有都含有“移进归约冲突。移进归约冲突。nFOLLOW(E)#, ), +，I0I1I2I3I4I5I6I7I8I9I10I11E

57、+T*TTiF(i( FE(Fi+F*()ACTIONGOTO状状态态i+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5其分析表如下其分析表如下:n非非SLR文法例如：思索如下文法：文法例如：思索如下文法：n(0) SSn(1) SL=Rn(2) SRn(3) L*Rn(4) Lin(5) RL计算计算FOLLOW集合所得到的超前符号集合能集合所得到的超前符号集合能够大于实践能出现的超前符号集。够大于实践能出现的超前符号集。这个文法

58、的这个文法的LR(0)工程集规范族为：工程集规范族为：I0：SS SL=R SR S*R Li RLI1：SSI2：SL=R RLI3：SRI4：L*R RL L*R LiI5：LiI6：SL=R RL L*R LiI7：L*RI9：SL=RI8：RL R S = i L R * L * * R i i L 活活 前前 缀缀 识识 别别 器器1203467589nSLR在方法中在方法中,假设工程集假设工程集Ii含工程含工程A.而且下一输入符号而且下一输入符号aFOLLOW(A),那么那么形状形状i面临面临a时时,可选用可选用“用用A归约动作。归约动作。但在有些情况下但在有些情况下,当形状当形状

59、i显现于栈顶时显现于栈顶时,栈栈里的活前缀未必允许把里的活前缀未必允许把归约为归约为A，由于，由于能够根本就不存在一个形如能够根本就不存在一个形如“Aa的规的规范句型。因此，在这种情况下，用范句型。因此，在这种情况下，用“ A 归约不一定适宜。归约不一定适宜。n如上例，当形状如上例，当形状2显现于栈顶而且面临输显现于栈顶而且面临输入符号为入符号为=时，实践上不能用对栈顶时，实践上不能用对栈顶L进进展归约，由于这个文法不含展归约，由于这个文法不含“R=为前缀为前缀的规范句型。的规范句型。5.3.4 规范规范LR分析表的构造分析表的构造n我们需求重新定义工程，使得每个工程都我们需求重新定义工程，使

60、得每个工程都附带有附带有k个终结符。每个工程的普通方式个终结符。每个工程的普通方式是是A, a1a2ak ，这样的一个工，这样的一个工程称为一个程称为一个LR(k)工程。工程中的工程。工程中的 a1a2ak 称为它的向前搜索符串称为它的向前搜索符串(或展望或展望串串)。n向前搜索符串仅对归约工程向前搜索符串仅对归约工程A，a1a2ak有意义。对于任何移进或待约有意义。对于任何移进或待约工程工程A, a1a2ak, ，搜索，搜索符串符串 a1a2ak 没有作用。没有作用。n归约工程归约工程A, a1a2ak意味着：当它所意味着：当它所属的形状呈如今栈顶且后续的属的形状呈如今栈顶且后续的k个输入符