编译原理-西安交通大学5_自下而上语法分析__3.0

1、第五章第五章 语法分析语法分析自下而上分析自下而上分析本章内容本章内容l自下而上分析基本问题自下而上分析基本问题l直观算符优先分析法直观算符优先分析法l算符优先分析算符优先分析l LRLR分析法分析法自下而上分析法自下而上分析法从输入串开始，逐步进行从输入串开始，逐步进行“归约归约”，直至，直至归约到文法的开始符号；归约到文法的开始符号；一、自下而上分析基本问题一、自下而上分析基本问题1 1 、归约、归约利用栈，输入符号移进栈，当栈顶形成利用栈，输入符号移进栈，当栈顶形成P P的的候选式时，就归约为它的左候选式时，就归约为它的左P P符号符号例例5.1 5.1 文法文法G2:G2:S-aAcB

2、eS-aAcBe A-b A-bA-AbA-Ab B-d B-d输入串：输入串：abbcdeabbcde自下而上法，即自下而上法，即“移进移进- -归约归约”法法最右推导：最右推导：a aa ab ba aA Aa aA Ab ba aA Aa aA Ac ca aA Ac cd da aA Ac cB Ba aA Ac cB Be eS S1 12 23 34 45 56 67 78 89 91010栈栈S S= aAc= aAcB Be e = aAc= aAcd de e =a=aAbAbcdecde= a b b c d e= a b b c d eS-aAcBeS-aAcBe输入串：

3、输入串：abbcdeabbcdeA-AbA-AbB-dB-dA-bA-bSaAcBeAbdb分分 析析 树树最左归约：最左归约：= S= S= aAc= aAcB Be e= a= aA Acdecde= a= aA Abcdebcdea a b b b c d e b c d e S-aAcBeS-aAcBe输入串：输入串：abbcdeabbcdeA-AbA-AbB-dB-dA-bA-b2 2 规范归约规范归约短语短语: :令令G G是一个文法，是一个文法，S S是文法的开始符是文法的开始符号，若号，若是文法是文法G G的一个句型，的一个句型，如果有如果有S AS A且且 A A ，则称，则

4、称是句型是句型相对于相对于非终结符非终结符A A的的短语。短语。句柄：句柄：一个句型的一个句型的最左直接短语最左直接短语称为该句型称为该句型的句柄。的句柄。直接短语：直接短语：如果有如果有A A ，则称，则称是句型是句型相对于规则相对于规则A A的的直接短语直接短语规范推导：规范推导：即即最右推导最右推导；规范句型：规范句型：由规范推导所得的句型称为规范由规范推导所得的句型称为规范句型；句型；规范归约：规范归约：是关于句型是关于句型的一个的一个最右推导最右推导的的逆过程，也称逆过程，也称最左归约最左归约。例例5.25.2 文法文法G G E T | E +T T F | T * F F i |

5、（E）的一个句型的一个句型 i i1 1* *i i2 2+i+i3 3语语 法法 树树TFEEFF+T*iiiTTFEEFF+T*i1i2i3T i i1 ,1 ,i i2 ,2 ,i i3 , 3 , i i1 1* *i i2 , 2 , i i1 1* *i i2 2+i+i3 3i i1 ,1 ,i i2 ,2 ,i i3 3 i i1 1 l短语短语: :l直接短语直接短语: :l句柄句柄: : 3 3 符号栈的使用符号栈的使用规范归约用来作语法分析需要解决的规范归约用来作语法分析需要解决的问题：问题：如何在句型中找出句柄如何在句型中找出句柄? ?在相同的右部有不止一个产生式时在相

6、同的右部有不止一个产生式时, ,选哪一个选哪一个? ?实现移进实现移进- -归约分析的一个方便途径是用一个栈和一个输归约分析的一个方便途径是用一个栈和一个输 入缓冲区入缓冲区, ,用用# #表示栈底和输入的结束表示栈底和输入的结束栈栈输输 入入#w# 分析程序的动作分析程序的动作l移进移进: : 下一输入符号移进栈顶下一输入符号移进栈顶l归约归约: : 把句柄按产生式的左部进行归约把句柄按产生式的左部进行归约l接收接收: : 分析程序报告成功分析程序报告成功l出错出错: : 发现了一个语法错发现了一个语法错, ,调用出错处理程序调用出错处理程序注意注意: : 可归约的串在栈顶可归约的串在栈顶,

7、 ,不会在内部不会在内部二二 直观算符优先分析法直观算符优先分析法 1 1 定义定义: : 任二个相继出现的终结符任二个相继出现的终结符a a与与b(b(可能中间有可能中间有V VNN), ),可能有以可能有以下优先关系下优先关系: :a b a的优先性的优先性低于低于ba b a的优先性的优先性等于等于ba b a的优先性的优先性高于高于b2 例例5.3 文法文法G:E E + E | E * E | EE | ( E ) | i的终结符的优先关系见下表。的终结符的优先关系见下表。 + * i （ ） # + * i（ ） #优优 先先 表表E E E+E | E E+E | E* *E |

8、 EE |( E )| iE | EE |( E )| i3 3 使用如上分析表，构造分析算法（直观算符使用如上分析表，构造分析算法（直观算符优先分析法）优先分析法）记号使用说明：记号使用说明： #：语句括号（栈底：语句括号（栈底 w后）后）：现行栈顶符：现行栈顶符 a：刚读入字符：刚读入字符OPTR：运算符栈：运算符栈OPND：操作符栈：操作符栈分析算法步骤：分析算法步骤：下一个输入符号读至下一个输入符号读至a a中；中；若若a a为为i i，则，则a aOPNDOPND，转第一步；，转第一步；若若 a a，则调用关于，则调用关于的处理程序（语义程序），处理子的处理程序（语义程序），处理子表

9、达式表达式 : : E E（1 1）EE（2 2） ；然后重新进入第；然后重新进入第3 3步；（其中，步；（其中， E E（1 1） 、E E（2 2）分分别为别为OPNDOPND栈的次栈顶和栈顶）栈的次栈顶和栈顶）aOPTROPND#E （1） E （2）E（3）=若若 a a，则，则若若=(=(,a=),a=),则逐出则逐出OPTROPTR栈顶的栈顶的(,(,放弃放弃a a中中的的 ),),转第转第 1 1步步; ;若若=a=#,a=#,分析成功结束；分析成功结束；若若 a a，a aOPTROPTR栈，转第栈，转第1 1步；步；与与a a不存在优先关系不存在优先关系，则输入串错误，调出错

10、处理，则输入串错误，调出错处理)OPTROPND#(E （1） E （2）a#成功！成功！2 例例5.4 由文法由文法G: E E + E | E * E | EE | ( E ) | i的终结符的优先关系表及上述分析算法的终结符的优先关系表及上述分析算法分析算术表达式分析算术表达式 i1 + i2 i1 + i2 * * i3 # i3 # 的过程。的过程。OPTROPTROPNDOPND分析过程分析过程 OPND OPND栈为空，栈为空， # -OPTR# -OPTR栈栈 i1-OPND i1-OPND # + # OPTR+-OPTR i2-OPND i2-OPND# #+ +i1 i1

11、i2i2i3i3* *t te e输入串输入串 : :i1 + i2 i1 + i2 * * i3 # i3 #+ +OPTR-OPTR i3-OPND i3-OPND* * # # ， * *弹出弹出OPTROPTR栈；栈； i2 i2 * * i3 = t -OPND i3 = t -OPND + # + # ， +弹出弹出OPTROPTR栈栈； t + i1 = e -OPNDt + i1 = e -OPND # =# # =# ， 分析成功；分析成功； e e 为整个表达式的结为整个表达式的结果果a a1 1 算符优先文法算符优先文法定义一定义一 如果一个文法的任何产生式右部都不含两如

12、果一个文法的任何产生式右部都不含两个相继（并列）的非终结符，即不含有如下形式个相继（并列）的非终结符，即不含有如下形式的产生式右部：的产生式右部：QRQR则我们称该文法为则我们称该文法为算符文法。算符文法。三三 算符优先分析算符优先分析定义二定义二 假定假定G G是一个不含是一个不含- -产生式的算符文法。对于任产生式的算符文法。对于任何一对终结符何一对终结符a a、b b，我们说：，我们说：la a b b， 当且仅当文法当且仅当文法G G中含有形如中含有形如P-P-abab 或或P-P-aQbaQb的产生式；的产生式； （如：（如：（E E），则（），则（ ）la ba b， 当且仅当当且

13、仅当G G中含有形如中含有形如P-P-aRaR的产生的产生式，而式，而R bR b 或或 R QbR Qb；la ba b， 当且仅当当且仅当G G中含有形如中含有形如P-P-RbRb的产生的产生式，而式，而R R a a 或或 R R aQaQ。 定义三定义三 如果一个算符文法如果一个算符文法G G中的任何终结符对（中的任何终结符对（a a，b b）至多只满足下述三种关系之一：至多只满足下述三种关系之一：a ba b，a ba b，a ba b则称则称G G是一个是一个算符优先文法。算符优先文法。2 2 从算符优先文法构造优先关系表从算符优先文法构造优先关系表构造优先关系表，就是要找出所有构

14、造优先关系表，就是要找出所有V VT T对之间的三种关对之间的三种关系，而对于系，而对于 可以直接检查所有的可以直接检查所有的G G中中P P来得到。而来得到。而 ， 关系不易检查，故要定义二个集合。关系不易检查，故要定义二个集合。FIRSTVT(P)=a|PFIRSTVT(P)=a|P a a或或P QaP Qa，aVaVT T 而而QVQVN N LASTVT(P)=a|PLASTVT(P)=a|P a a或或P P aQaQ，aVaVT T 而而QVQVN N 如该二集合成功，检查如该二集合成功，检查P P，就可确定满足，就可确定满足 ， 的（的（a a，b b）对。）对。这是因为，假定

15、有个产生式候选式：这是因为，假定有个产生式候选式： aPaP，那么对任何，那么对任何 bFIRSTVT(PbFIRSTVT(P), ),有有a ba b； PbPb，那么对任何，那么对任何 aLASTVT(PaLASTVT(P) )，有，有a ba b；构造该二个集合的算法，对每一构造该二个集合的算法，对每一 V VNN的的FIRSTVT(PFIRSTVT(P) ) 、LASTVT(PLASTVT(P）使用每个使用每个V VNN的的FIRSTVT(P)FIRSTVT(P) 、LASTVT(PLASTVT(P），检），检查每一个产生式，找出所有（查每一个产生式，找出所有（a a，b b）的关）的

16、关系，就完成了构造优先关系表。系，就完成了构造优先关系表。因此，问题归结为：因此，问题归结为：3 3 构造集合构造集合FIRSTVT(P)FIRSTVT(P)的算法的算法 P-a P-a或或P-QaP-Qa,则则aFIRSTVT(PaFIRSTVT(P) )；若若aFIRSTVT(QaFIRSTVT(Q),),且有产生式且有产生式P-QP-Q，则，则aFIRSTVT(PaFIRSTVT(P) )4 4 构造集合构造集合LASTSTVT(P)LASTSTVT(P)的算法的算法 P-a P-a 或或 P-aQP-aQ, ,则则aLASTVT(PaLASTVT(P) )；若若aLASTVT(QaLA

17、STVT(Q),),且有产生式且有产生式P-QP-Q，则，则aLASTVT(PaLASTVT(P) )5 5 构造优先表方法构造优先表方法 对形如对形如 P-abP-ab和形如和形如P-aQbP-aQb，有，有a ba b；对形如对形如 P-aRP-aR，而，而bFIRSTVT(RbFIRSTVT(R) )，有，有a ba b；对形如对形如 P-RbP-Rb，而，而aLASTVT(RaLASTVT(R) )，有，有a ba b；对文法开始符号对文法开始符号S，有，有# FIRSTVT(S)，LASTVT(S) #， 且对且对 #S#，有，有# #。lFIRSTVT(P)FIRSTVT(P)的自

18、动构造的自动构造过程过程INSERTINSERT： PROCEDURE INSERT(P,a)PROCEDURE INSERT(P,a) IF NOT FP,a THEN IF NOT FP,a THENBEGIN BEGIN FP,a := TRUE FP,a := TRUE； 把把(P,a)(P,a)下推进下推进STACKSTACK栈栈 END;END;主程序：主程序：BEGINBEGIN FOR FOR 每个非终结符每个非终结符P P和终结符和终结符a DO FP,a := FALSE;a DO FP,a := FALSE; FOR FOR 每个形如每个形如P-a P-a 或或P-QaP

19、-Qa的产生式的产生式 DO DO INSERT(P,a);INSERT(P,a); WHILE STACK WHILE STACK 非空非空 DODO BEGIN BEGIN把把STACKSTACK的顶项，记为的顶项，记为(Q,a)(Q,a)，弹出去，弹出去FOR FOR 每条形如每条形如P-QP-Q的产生式的产生式 DODO INSERT(P,a) INSERT(P,a) END OF WHILE; END OF WHILE;ENDENDlLASTVT(P)LASTVT(P)的自动构造的自动构造过程过程INSERTINSERT： PROCEDURE INSERT(P,a)PROCEDURE

20、 INSERT(P,a)IF NOT LP,a THENIF NOT LP,a THEN BEGIN BEGIN LP,a := TRUELP,a := TRUE；把把(P,a)(P,a)下推进下推进STACKSTACK栈栈 END;END;主程序：主程序：BEGINBEGIN FOR FOR 每个非终结符每个非终结符P P和终结符和终结符a DO LP,a := FALSE;a DO LP,a := FALSE; FOR FOR 每个形如每个形如P- P- a a 或或P- P- aQ aQ的产生式的产生式 DO DO INSERT(P,a);INSERT(P,a); WHILE STACK

21、 WHILE STACK 非空非空 DODO BEGIN BEGIN把把STACKSTACK的顶项，记为的顶项，记为(Q,a)(Q,a)，弹出去，弹出去FOR FOR 每条形如每条形如P- P- Q Q的产生式的产生式 DODO INSERT(P,a) INSERT(P,a) END OF WHILE; END OF WHILE;ENDENDl优先表的自动构造优先表的自动构造FOR FOR 每条产生式每条产生式P-X1X2P-X1X2Xn DOXn DO FOR i := 1 TO n-1 DO FOR i := 1 TO n-1 DOBEGINBEGIN IF Xi IF Xi和和Xi+1X

22、i+1均为终结符均为终结符 THEN THEN 置置Xi Xi+1Xi Xi+1 IF in IF in2 2且且XiXi和和Xi+2Xi+2都为终结符都为终结符但但Xi+1Xi+1为非终结符为非终结符 THEN THEN 置置Xi Xi+2;Xi Xi+2; IF Xi IF Xi为终结符而为终结符而Xi+1Xi+1为非终结符为非终结符THENTHENFOR FIRSTVT(Xi+1)FOR FIRSTVT(Xi+1)中的每个中的每个a DOa DO置置 Xi a;Xi a; IF Xi IF Xi为非终结符而为非终结符而Xi+1Xi+1为终结符为终结符 THENTHENFOR LASTVT

23、(Xi)FOR LASTVT(Xi)中的每个中的每个a DOa DO置置 a Xi+1a Xi+1ENDEND6 6 算符优先分析算法的设计算符优先分析算法的设计l定义定义 1 1）文法文法G G，开始符号，开始符号S S，若，若S S ，如果，如果S S 且且 A A ，则称则称是句型是句型的一个的一个短语短语。2 2）所谓素短语是指这样一个短语所谓素短语是指这样一个短语, ,它至少含有一个终它至少含有一个终结符结符, ,并且并且, ,除自身之外除自身之外, ,不再含任何更小的不再含任何更小的素短语素短语。3 3）句型最左边的那个素短语叫句型最左边的那个素短语叫最左素短语最左素短语。l最左素

24、短语满足以下条件的最左子串最左素短语满足以下条件的最左子串 NNj ja aj j N Ni ia ai iNNi+1i+1， a aj-1j-1 a aj ja aj j a aj+1 j+1 , , , a , ai-1 i-1 a ai i a ai i a ai+1i+1l定理定理算符优先文法的句型一般形式：算符优先文法的句型一般形式：# #NN1 1a a1 1NN2 2a a2 2NNn na an nNNn+1n+1# # 其中，其中，a ai i V VT T，NNi i V VNN|l算法分析：算法分析：l也即：也即： a aj-1j-1 a ai+1i+1 NNj j a

25、aj j a ai i NNi+1i+12 例例5.5 i1 i1 * *( i2 + i3) # ( i2 + i3) # # # i1 i1 * * ( ( i2 i2 + + i3i3 ) ) # #i1i1，i2i2，i3i3是素短语；是素短语；i1 i1是最左素短语。是最左素短语。 IF Sj a OR SjIF Sj a OR Sj a THEN a THEN BEGIN BEGIN k:=k+1;Sk:=a k:=k+1;Sk:=a END END ELSE ERROR ELSE ERROR UNTIL a=# UNTIL a=# k:=1; Skk:=1; Sk:=#;:=#;

26、REPEATREPEAT 把下一个输入符号读进把下一个输入符号读进a中；中； IF SkVIF SkVT T THEN j:=k ELSE j:=k-1; THEN j:=k ELSE j:=k-1; WHILE Sj WHILE Sj a DO a DO BEGIN BEGIN REPEAT REPEAT Q:=Sj Q:=Sj; IF Sj-1V IF Sj-1VT T THEN j:=j-1 ELSE j:=j-2 THEN j:=j-1 ELSE j:=j-2 UNTIL Sj UNTIL Sj Q Q 把把Sj+1SkSj+1Sk 归约为某个归约为某个N N； k:=j+1;k:=j

27、+1; Sk Sk:=N;:=N; END OF WHILE; END OF WHILE; 7 7 优先函数优先函数 l定义：定义： 我们把每个终结符我们把每个终结符与两个自然数与两个自然数f( f() ) 和和g(g() )相对相对应，使得：应，使得： 若若1 1 2 2，则，则f( f(1 1)g()g()g(2 2) )函数函数 f f 称为称为入栈优先函数入栈优先函数，g g 称为称为比较优先函数比较优先函数。l使用优先函数的优缺点：使用优先函数的优缺点：优：便于比较运算；节省存储空间。优：便于比较运算；节省存储空间。缺：对不存在优先关系的两个终结符，由于与自然数相缺：对不存在优先关系

28、的两个终结符，由于与自然数相 对应，变成可比较对应，变成可比较。l优先函数的性质：优先函数的性质：1）正确性：）正确性：优先函数掩盖了矩阵中出错元素对，若优先函数掩盖了矩阵中出错元素对，若f(id) g(b) f(a) g(b) f(b) = g(a) f(b) = g(a) f(b) = g(b) f(b) = g(b)那么，那么，f(a)g(b)=f(b)=g(a)=f(a)f(a)g(b)=f(b)=g(a)=f(a)，矛盾。，矛盾。baba g(x)f(x)3）唯一性：）唯一性：存在一个优先函数，就有无数多对，加一常数，不等存在一个优先函数，就有无数多对，加一常数，不等式也成立。式也成

29、立。l构造优先函数的方法构造优先函数的方法（如果优先函数存在的话）（如果优先函数存在的话）v对每个对每个a a（包括）（包括）VVT T，对应两个符号，对应两个符号f fa a，g ga a。v把所建立的符号尽可能划分为许多组：把所建立的符号尽可能划分为许多组：若若a ba b，则，则f fa a和和g gb b就在一组；就在一组；若若a ba b，c bc b，则，则f fa a和和f fc c同组；同组；v建立一个有向图，其结点是上一步中找出的组。建立一个有向图，其结点是上一步中找出的组。对于任何对于任何a a和和b b，若，若 a ba b，画，画 f fa aggb b 弧，意味着弧，

30、意味着f(a)g(b)f(a)g(b)； 若若 a ba b，画，画 g gb bffa a 弧，意味着弧，意味着f(a)g(b)f(a) E+E | E*E | EE | ( E ) | i的终结符的优先关系表，构造优先函数。的终结符的优先关系表，构造优先函数。f+f*ff)f(g)g(gg*g+由优先关系表，得：由优先关系表，得： + ) ( * + *其余类同其余类同46629358824 4 LR LR分析法分析法l语法分析概述（见图语法分析概述（见图1 1）lLRLR分析程序分析程序( (器器) )：自左向右自左向右扫描，识别句柄，扫描，识别句柄，自下而上自下而上归约的归约的 语法分

31、析程序语法分析程序。lLRLR分析程序生成器：自动生成分析程序生成器：自动生成LRLR分析程序的程分析程序的程序。序。lLRLR分析程序（见图分析程序（见图2 2）图图 1（返回）返回）算符优先-最左素短语规范归约-句柄自下而上(自动生成)递归下降-消除左递归预测分析法- 预测分析表 自上而下(手动，自动生成)语法分析图图 2（返回）（返回）分析表分析表产生器产生器文法文法分析表分析表总控总控程序程序输入输入输出输出分析表分析表l分析表的构造方法（见图分析表的构造方法（见图3 3）LR(0)表构造法SLR表构造法规范LR表构造法LALR（向前LR）表构造法分析表的构造方法图图 31 1、 LR

32、LR分析程序分析程序A A、LRLR分析程序的分析程序的实质实质：分析栈：分析栈DFADFA（见图（见图4 4）图图 4 4状态状态符号符号S0S1Sm#X1XmLR分析程序分析程序分析表分析表actiongoto输出输出输入串输入串栈栈#anaia1B B、LRLR分析的核心分析的核心分析表分析表l分析表由分析表由ACTIONACTION表表和和GOTOGOTO表表两部分组成。两部分组成。ACTION(sACTION(s，a)a)：表示当状态：表示当状态s s面临输入面临输入a a时的动作时的动作GOTO(sGOTO(s，x)x)：表示面对文法符号：表示面对文法符号x x的下一状态的下一状态

33、lACTIONsACTIONs，aa表中的动作种类：表中的动作种类： 移进移进 归约归约 接受接受 报错报错C C、给出下述文法、给出下述文法G G的的LRLR分析表分析表 文法文法G G (1)EE+T (2) ET (3) TT *F (4) TF (5) F(E) (6) Fi 分析表分析表（图（图 5） 分析表中记号的含义分析表中记号的含义sjsj： 把下一状态把下一状态 j j 和现行输入符号和现行输入符号 a a 移进栈；移进栈；rjrj： 按第按第 j j 个产生式进行归约；个产生式进行归约；accacc： 接受；接受；空白格：出错标志，报错空白格：出错标志，报错状态状态ACTI

34、ON(动作动作)GOTO(转换转换)i+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5图图 5例例 5.8 利用上述分析表，假定输入串为利用上述分析表，假定输入串为 i * i + i ，描述描述LR分析器的工作过程。分析器的工作过程。（1） 0#i * i + i #（2） 05#i * i + i #（3） 03#F * i + i #（4） 02#T * i + i #（5） 027#T* i + i #（6） 0275#T*

35、i + i #（7） 02710#T*F + i #（8） 02#T + i #（9） 01#E + i #ACTION 0, i =s5移进移进 5 和和 iACTION 5, * =r6按第按第6个产生式个产生式进行归约，即：进行归约，即：(6) (6) F Fi iGOTO0,F=3移进状态移进状态3ACTION 10, + =r3按第按第3个产生式个产生式进行归约，即进行归约，即(3) (3) T TT T * *F FGOTO0,T=2移进状态移进状态2例例5.8 利用上述分析表，假定输入串为利用上述分析表，假定输入串为 i * i + i ，描述，描述LR分析器的工作过程。分析器的

36、工作过程。(续续)（10） 016#E+ i #（11） 0165#E+i #（12） 0163#E+F #（13） 0169#E+T #（14） 01#E #ACTION1,#=accACTION1,#=acc接受输入串！接受输入串！D D、LRLR文法文法 LRLR（k k）文法：一个文法，如果能用一个每步顶多）文法：一个文法，如果能用一个每步顶多向前检查向前检查k k个输入符号的个输入符号的LRLR分析器进行分析，则这个分析器进行分析，则这个文法就称为文法就称为LR(kLR(k) )文法文法。定义：对于一个文法，如果能够构造一张分析表，定义：对于一个文法，如果能够构造一张分析表，使得它的

37、每个入口均是唯一确定的，则我们把这个文使得它的每个入口均是唯一确定的，则我们把这个文法称为法称为LRLR文法文法。 A A、LR(0)LR(0)分析表的构造步骤分析表的构造步骤 确定确定G G的的LR(0)LR(0)项目项目 以以LR(0)LR(0)项目为状态项目为状态, ,构造一个能识别文法构造一个能识别文法G G的所有活的所有活前缀的前缀的NFANFA 利用子集法利用子集法, ,将将NFANFA确定化确定化, ,成为以项目集合为状态的成为以项目集合为状态的DFADFA根据根据 上述上述DFADFA可直接构造出可直接构造出LRLR分析表分析表2 2、LR(0)LR(0)分析表的构造分析表的构

38、造定义：定义：文法文法G G每一个产生式的右部添加一个圆点，称为每一个产生式的右部添加一个圆点，称为 G G的一个的一个LR(0)LR(0)项目。项目。 如：如：AXYAXY对应三个项目：对应三个项目： AAXY AXXY AXY AXYY AXY 而而: : AA 的项目的项目 AA B B、LR(0)LR(0)项目（简称项目）项目（简称项目）项目的意义：项目的意义：指明在分析过程的某时刻，我们看到产指明在分析过程的某时刻，我们看到产 生式多大一部分生式多大一部分项目在计算机中的表示：项目在计算机中的表示：（m m，n n） intint m m，n n m m：代表产生式编号：代表产生式编

39、号 n n：指出圆点的位置：指出圆点的位置 如：如：abcabc前缀：前缀：，a a，abab，abcabc活前缀活前缀：规范句型的一个前缀，该前缀是不含句柄之后：规范句型的一个前缀，该前缀是不含句柄之后 的任何符号。的任何符号。 C C、字的前缀：指该字的任意首部、字的前缀：指该字的任意首部D D、对文法、对文法G G，构造能识别，构造能识别G G的所有活前缀的的所有活前缀的NFANFANFANFA的状态：是一个的状态：是一个LR(0)LR(0)项目项目构造方法：构造方法： a. a.文法开始符号的形如文法开始符号的形如SS S S的项目为的项目为NFANFA的唯一初态；的唯一初态； b b

40、. .若状态若状态i i和和j j出自同一个产生式，而且出自同一个产生式，而且j j的圆点只落后于的圆点只落后于I I 的圆点一个位置，就从的圆点一个位置，就从i i画一条标志为画一条标志为XiXi的弧到的弧到j j。 （即，（即，i i：X XX1X1Xi-1Xi-1 XiXiXnXn j j：XX1 XX1 Xi-1XiXi-1XiXnXn） c c. .若状态若状态i i的圆点之后的符号为非终结符，如的圆点之后的符号为非终结符，如I I为为 X XAA，其中，其中A A属于属于V VNN，就从状态，就从状态i i画画弧到所有弧到所有 AA状态。状态。例例2.2.构造以下文法的构造以下文法

41、的NFANFA 文法文法G的所有的所有LR(0)项目项目 文法文法 G G S S E E E E aA|bBaA|bB A A cA|dcA|d B B cB|dcB|d 1.S E 2. S E 3. E aA 4. E a A 5. E aA 6. A cA 7. A c A 8. A cA 9. A d 10. A d 11. E bB 12. E b B 13. E bB 14. B cB 15. B c B 16. B cB 17. B d 18. B d 利用上述规则利用上述规则a a，b b，c c构造构造NFANFA，如图所示：，如图所示： 1 13 3A A1 13 37

42、79 91 11 11 12 21 14 41 15 51 17 76 64 45 51 10 08 82 21 16 61 18 8a ac cb bd dc cd dB BA AB BE E、使用子集方法，将、使用子集方法，将NFANFA确定化，使之成为一个以项目集确定化，使之成为一个以项目集合为状态的合为状态的DFADFA。 相关定义：相关定义： LR(0) LR(0)项目集规范族：构成识别一个文法活前缀的项目集规范族：构成识别一个文法活前缀的DFADFA 的项目集（状态）的全体。的项目集（状态）的全体。 归约项目：归约项目：AA 接受项目：接受项目：SS （SS文法的开始符号）文法的开

43、始符号） 移进项目：移进项目：AA aa （aa终结符）终结符） 待约项目：待约项目：AA BB (B(B非终结符非终结符) ) 利用利用CLOSURECLOSURE方法构造方法构造LR(0)LR(0)项目集规范族项目集规范族 拓广文法拓广文法 CLOSURE(I)算法算法(其中其中I为为G的任一项目集的任一项目集)I I的任何项目都属于的任何项目都属于CLOSURE(I);CLOSURE(I);若若A-A- BB属于属于CLOSURE(I)CLOSURE(I)，那么，对任何关于，那么，对任何关于B B的的 产生式产生式B-B-，项目，项目B B- 也属于也属于CLOSURE(I);CLOSU

44、RE(I);重复执行上述两步骤直至重复执行上述两步骤直至CLOSURE(I)CLOSURE(I)不再增大为止。不再增大为止。构造项目集规范族方法（见下页构造项目集规范族方法（见下页) ) 步骤一步骤一: :令令NFANFA的初态为的初态为I I, ,求其求其CLOSURE(CLOSURE(I I), ),得到初态项目得到初态项目集。即集。即: : 求求CLOSURECLOSURE（SSS)S) 步骤二步骤二: :对所得项目集对所得项目集I I和文法和文法G G的每个文法符号的每个文法符号X(X(包括包括V VT T和和V VN N) ) 计算计算GOGO（I I，X X） =CLOSURE=C

45、LOSURE（J J），得到新的项目集。），得到新的项目集。 其中其中J=J=任何形如任何形如A A X X 的项目的项目| | A A X X 属于属于I I 步骤三步骤三: :重复步骤二，直至没有新的项目集出现。重复步骤二，直至没有新的项目集出现。 经过以上步骤构造出的项目集的全体即为经过以上步骤构造出的项目集的全体即为LR(0)LR(0)项项目集规范族。目集规范族。 利用利用LR(0)LR(0)项目集规范族和项目集规范族和GOGO函数画出函数画出DFADFA 相关定义：相关定义： LR(0)文法：不存在以下两种冲突的文法文法：不存在以下两种冲突的文法 移进归约冲突移进归约冲突 归约归约冲

46、突归约归约冲突 LR(0)表：由表：由LR(0)文法得到的分析表文法得到的分析表 LR(0)分析器：使用分析器：使用LR(0)表的分析器表的分析器F F、LRLR（0 0）分析表的构造）分析表的构造分析表的构造方法分析表的构造方法 如下：如下： a、若项目若项目A a 属于属于Ik且且GO(Ik,a) Ij，a为终结符，且置为终结符，且置 ACTIONk，a为为“把（把（j，a）移进栈）移进栈”，简记为，简记为“sj”； b、若项目若项目A 属于属于Ik，那么，对任何输入符号，那么，对任何输入符号a（或者结束符（或者结束符） 置置ACTIONk，a为为“用产生式用产生式A 进行归约进行归约”，

47、简记为，简记为“rj”；其其 中，假定中，假定A 为文法为文法G的第的第j个产生式；个产生式； c、若项目若项目SS属于属于Ik，则置，则置ACTIONk，为为“接受接受”，简记为，简记为 “acc”； d、若若GO（Ik，A）Ij，A为非终结符，则置为非终结符，则置GOTOk，Aj； e、分析表中凡不能使用规则分析表中凡不能使用规则1至至4填入信息的空白格均置上填入信息的空白格均置上“出错标出错标 志志”。例例3.3.根据例根据例2 2的结果，将其的结果，将其NFANFA确定化确定化 , ,并构造该文法的并构造该文法的 LR(0)LR(0)分析表。假定这个文法的各个产生式的编号如分析表。假定

48、这个文法的各个产生式的编号如 下：下： 0 0、SS E 1E 1、E E aAaA 2 2、E E bBbB 3 3、A A cAcA 4 4、A A d 5d 5、B B cBcB 6 6、B B d d DFA构造：（部分）构造：（部分）lCLOSURE ( S- E ) = S- E, E- aA, E- bB 此即为此即为DFA的状态的状态0l令令I = S- E, E- aA, E- bB GO( I, a ) = CLOSURE( E-aA ) /即即I中所有圆点之后紧跟中所有圆点之后紧跟a的的 = E-a A, A-cA, A-d GO( I, b ) = CLOSURE( E

49、-bB ) = E-b B, B-cB, B-d GO( I, E ) = CLOSURE( S-E ) = S-E l同上步骤，依次对各项目集进行计算（略）同上步骤，依次对各项目集进行计算（略） LR(0)分析表构造分析表构造0:S0:S EE E Aa E Aa E bB E bB3:E 3:E bBbB B cB B cB B d B d2:E 2:E aAaA A cA A cA A d A d1:S1:S E E （DFA部分图，全图见下页）部分图，全图见下页）0:S0:S EE E Aa E Aa E bB E bB5:EcB5:EcB B cB B cB B d B d3:E 3

50、:E bBbB B cB B cB B d B d2:E 2:E aAaA A cA A cA A d A d4:AcA4:AcA A cA A cA A d A d1:S1:S E E 10:Ad10:Ad 8:AcA 8:AcA 6:EaA6:EaA7:EbB7:EbB11:Bd11:Bd 9:BcB9:BcBc ca ac cc cc cb bd dd dd dA Ad dA AB BB B状态状态ACTION(动作动作)GOTO(转换转换)abcd#EAB0s2s311acc2s4s1063s5s1174s4s1085s5s116r1r1r1r1r19 7r2r2r2r2r28r3r3

51、r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r6 该文法的该文法的LR(0)分析表如下所示：分析表如下所示： A A、若、若LR(0)LR(0)规范族中含有冲突项目规范族中含有冲突项目, ,采用向前展望方法解决采用向前展望方法解决 例例4. 4. 若若I=XI=X bb ，AA ，BB 若当前输入符号为若当前输入符号为b b，则含有移进，则含有移进归约冲突；归约冲突； 而而A A和和B B，又含有归约，又含有归约归约冲突。归约冲突。 解决办法：解决办法： 考察考察FOLLOWFOLLOW（A A）和）和FOLLOWFOLLOW（B B） （设（设FOLLOWF

52、OLLOW（A A）FOLLOWFOLLOW（B B）为空，且均不含）为空，且均不含b b）3 3、SLRSLR表的构造方法表的构造方法 则当则当 I I 面临任何输入符号面临任何输入符号a时，可做出如下时，可做出如下“移进移进归约归约 决策：决策： 若若a=b，移进；移进； 若若a属于属于FOLLOW（A），则用），则用A 归约；归约； 若若a属于属于FOLLOW（B），则用），则用B 归约；归约； 此外，报错。此外，报错。 B B、回顾、回顾FOLLOWFOLLOW（A A）的计算。（其中）的计算。（其中A A是非终结符）是非终结符） 注：注：FIRST集是针对终结符、非终结符和产生式构造

53、的；集是针对终结符、非终结符和产生式构造的； FOLLOW集仅对非终结符构造。集仅对非终结符构造。C C、SLRSLR表的构造方法表的构造方法 若项目若项目AA a a 属于属于I Ik k且且GO(IGO(Ik k,a),a) I Ij j，a a为终结符，且置为终结符，且置 ACTIONkACTIONk，aa为为“把状态把状态j j和符号和符号a a移进栈移进栈”，简记为，简记为“sj sj”； 若项目若项目AA 属于属于I Ik k，那么，对任何输入符号，那么，对任何输入符号a a， aFOLLOW(AaFOLLOW(A) )，置，置ACTIONkACTIONk，aa为为“用产生式用产生

54、式AA 进进 行归约行归约”，简记为，简记为“rj rj”；其中，假定；其中，假定AA 为文法为文法GG的第的第j j个个 产生式；产生式； 若项目若项目SSSS属于属于I Ik k，则置，则置ACTIONkACTIONk， 为为“接受接受”，简，简 为为“acc”acc”； 若若GO(IGO(Ik k，A)=IA)=Ij j，A A为非终结符，则置为非终结符，则置GOTOkGOTOk，A= jA= j； 分析表中凡不能使用规则分析表中凡不能使用规则1 1至至4 4填入信息的空白格均置上填入信息的空白格均置上“出出 错标志错标志”。只在归约时 展望,即已到产生式末尾,则去判断FOLLOW(A)

55、 文法文法 G G： (0) S(0) SE E ( (1) 1) E EE+TE+T ( (2) E2) ET T ( (3) 3) T TT T* *F F ( (4) 4) T TF F ( (5) 5) F F(E)(E) ( (6) 6) F Fi i 例例4 4：对如下文法构造其：对如下文法构造其SLRSLR分析表。分析表。该文法的该文法的LR(0)LR(0)项目集规范族项目集规范族由这些项目集的转换函数由这些项目集的转换函数GOGO表示成的表示成的DFADFA文法文法G G的非终结符的的非终结符的FOLLOWFOLLOW集如下：集如下：FOLLOW(S)= # FOLLOW(S)

56、= # FOLLOW(EFOLLOW(E）= += +，），），# # FOLLOW(T)= +, FOLLOW(T)= +, * * , ) , # , ) , # FOLLOW(F)= +, FOLLOW(F)= +, * * , ) , # , ) , # SLRSLR分析表分析表状态状态ACTION(动作动作)GOTO(转换转换)i+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5文法文法 G 的的SLR分析表如下所示：分析表

57、如下所示： 问题：问题：有些无二义文法会产生有些无二义文法会产生“移进移进/ /归约归约”冲突冲突 或或“归约归约/ /归约归约”冲突冲突产生原因：产生原因：SLRSLR分析法未包含足够多的分析法未包含足够多的“展望展望”信息信息解决办法：解决办法：让每个状态含有更多的让每个状态含有更多的“展望展望”信息信息 4 4、规范、规范LRLR分析表的构造分析表的构造方法：重新定义项目，使得每个项目都附带有方法：重新定义项目，使得每个项目都附带有k k个终结符；个终结符；即每个项目的形式为：即每个项目的形式为：A- A- , a, a1 1a a2 2a ak k p向前搜索符串仅对归约项目向前搜索符

58、串仅对归约项目A-A- , a, a有意义；有意义；p归约项目归约项目A-A- , a, a意味着：当它所属的状态呈现在栈顶意味着：当它所属的状态呈现在栈顶且后续的且后续的k k个输入符号为个输入符号为a a1 1a a2 2a ak k 时，才可以把栈顶上的时，才可以把栈顶上的归归约为约为A Ap只研究只研究k1k1的情形的情形定义：如上形式的项目称为一个定义：如上形式的项目称为一个LR(k)LR(k)项目项目。说明：说明：A A、构造规范、构造规范LRLR分析表的步骤：分析表的步骤：l确定确定LR(1)LR(1)项目；项目；l根据根据LR(1)LR(1)项目构造项目构造NFA;NFA;l利

59、用函数利用函数CLOSURECLOSURE和和GOGO求求DFA;DFA;l根据根据DFADFA，构造，构造LRLR分析表。分析表。B B、确定、确定LR(1)LR(1)项目项目确定确定LR(1)LR(1)项目的方法：项目的方法： 对对SS和和S S，只向前搜索，只向前搜索 # # ； 其它产生式，对每一个其它产生式，对每一个V VT T均向前搜索。均向前搜索。 例例5 5 拓广文法拓广文法 (0)S-S (0)S-S(2) B-aB(2) B-aB (1) S-BB (1) S-BB(3) B-b(3) B-b由由： S-S-S,#S,#S-SS-S,#,#S-S-BB,#BB,#S-BS-

60、BB,#B,#S-BBS-BB,#,#由由: B-B-aB,aaB,a B- B-aB,b aB,b B- B-aB,#aB,# B-a B-aB,a B,a B-aB-aB,b B,b B-a B-aB,# B,# B-aB B-aB,a ,a B-aB B-aB,b ,b B-aBB-aB,# ,# B-B-b,ab,a B- B-b,b b,b B- B-b,# b,# B-bB-b,a ,a B-b B-b,b ,b B-b B-b,# ,# 定义定义我们说一个我们说一个LR(1)LR(1)项目项目 A- A-, a , a 对于活前缀对于活前缀是是有效的有效的，如果存在规范推导，如果