第五章语法分析——自下而上分析

1、第五章 语法分析 自下而上分析自下而上分析：从输入串开始，逐步进行“归约”，直至归 约到文法的开始符号。 5.1 自下而上分析基本问题n归约 自下而上分析法是“移进归约”法。 模型：移进归约识别成功其他出错字符串：babAba#b#ba#A归约5.1 自下而上分析基本问题1.输入带记录待识别语句（单词结束符#）2.读头自左向右扫描输入串，初态指在最左单词上，栈内仅有#3.语法分析执行动作有：移进读入一单词并压入栈内，读头下移一位归约检查栈顶若干符号是否为语法表中产生式右部，若是，用左部替换右部识别成功栈内为文法开始符号，读头指向#否则，语法错误programIdVar#语法分析程序分析表#输入

2、串：下推栈，初态为#，字符“先进后出”如：SaAcBeAAb|bBd分析：abbcdeSaAcBeAbdb栈内输入带动作0#abbcde#预备1#abbcde#移进2#abbcde#移进3#aAbcde#归约(Ab)4#aAbcde#移进5#aAcde#归约(AAb)6#aAcde#移进7#aAcde#移进8#aAcBe#归约(Bb)9#aAcBe#移进10#S#归约(SaAcBe)11#S#接受(分析成功)5.1.2 规范规约简述1.短语、直接短语、句柄n短语：已知文法GS，是文法G的一个句型，若S A且A，则称是句型的相对于非终结符A的短语。n直接短语：若有SA且A，称是句型的相对于规则A

3、的直接短语。n句柄：一个句型的最左直接短语称为该句型的句柄。*例：G: E E+T | E-T | T T T*F | T/F | F F (E) | i 给出句型E+T*F+i的短语、直接短语和句柄。例： G： EE+T | T 句型E+T*F+i TT*F | F F(E) | i短语： E+T*F+i， E+T*F， T*F，i直接短语： T*F，i句柄： T*F归约方法：形成句柄则进行归约。abbcde AbaAbcde AbaAcde BdaAcBe SaAcBdS2.规范归约： 假定是文法G的一个句子，称序列n，n1， 0 是的一个规范归约，则此序列满足： （1）n （2）0为文法

4、开始符，即0S （3）对任何i，0in， i1是从i经把句柄替换为相应产生式的左部符号而得到的。 最左推导的逆过程最右归约 最右推导的逆过程最左归约 最右推导称为规范推导 最左归约称为规范归约SaAcBeAbdb5.2 算符优先分析n直观算符优先法 对于文法，任何两个相继出现的终结符（ab或aQb），有下列三种关系： a b a的优先性等于b a b a的优先性高于b a b a的优先性低于b注意：这三个关系不同于数学中的“=”，“”，此处a b并不一定意味着b a，a b也不一定意味着 b a。5.2.1 算符优先文法及优先表的构造1.算符文法(OG)：文法G，如果G中每条规则不能有形如AB

5、C(A,B,CVN)的规则，则称G为算符文法。2.设G是不含产生式的文法，对任何终结符a,bVT，A,B,CVN， (1)a bG中含有规则Aab或AaBb (2)a bG中含有规则AaB，而Bb或BCb (3)a bG中含有规则ABb，而Ba或BaCn若一个算符文法G 中任何终结符对(a,b)至多只满足下述三个关系之一： a b ，a b ，a b 则称G是一个算符优先文法(OPG)。如： EE+E | E*E | (E)| i 为算符文法，但不是算符优先文法。 EE+E EE*E + * EE*E EE+E + *n注意：算符优先文法中允许a b，b a同时存在，但不允许a b ，a b

6、，a b三种中任何两种同时存在。例： G： EE+T | T TT*F | F FPF | P P(E) | i+*i()#+*i()#3.算符优先关系的构造 FIRSTVT(P)=a | Pa或P Qa，aVT，QVN LASTVT(P)=a | Pa或P aQ，aVT，QVN三种关系的计算： 关系：由产生式右部决定，形如ab或aQb如：SaAcBe，Ab，AAb，Bd，BAb 有 a c c e 关系：求出每个符号的FIRSTVT，对于形如AaB就有a FIRSTVT(B)如上例：FIRSTVT(S)=a,FIRSTVT(A)=b, FIRSTVT(B)=b,d 关系：求出每个符号的LAS

7、TVT，对于形如ABb就有LASTVT(B) b如上例：LASTVT(S)=e，LASTVT(A)=b， LASTVT(B)=b,dG： S#S# Sif Eb then E else E EE+T | T TT*F | F F i EbbFIRSTVT(S)=#FIRSTVT(S)=ifFIRSTVT(E)=+,*,iFIRSTVT(T)=*,iFIRSTVT(F)=iFIRSTVT(Eb)=bLASTVT(S)=#LASTVT(S)=else, +,*,iLASTVT(E)=+,*,iLASTVT(T)=*,iLASTVT(F)=iLASTVT(Eb)=bifthenelse*ib#ift

8、henelse*ib#nFIRSTVT(P)算法： (1)若有Pa或PQa，则aFIRSTVT(P)； (2)若有PQ且aFIRSTVT(Q)，则aFIRSTVT(P)。nLASTVT(P)算法： (1)若有Pa或PaQ，则aLASTVT(P)； (2)若有PQ且aLASTVT(Q)，则aLASTVT(P)。5.2.1 算符优先文法及优先表的构造例： G： E#E# EE+T | T TT*F | F FPF | P P(E) | i+*i()#+*i()#5.2.2 算符优先分析算法n素短语：是一个短语，它至少含有一个终结符，且除自身之外不包含其它的素短语。n最左素短语：处于句型最左边的素短

9、语。（从语法树看）n例：G: E E+T | T T T*F | F F PF | P P (E) | i 给出句型P*P+i的短语、素短语和最左素短语。2.句型的一般形式： #N1a1N2a2NnanNn+1# 其中Ni为非终结符或，ai为终结符。3.一个算法优先文法G的任何句型的最左素短语是满足如下条件的最左子串NjajNiaiNi+1：aj-1 ajaj aj+1,ai-1 aiai ai+14. 算符优先算法k=1; Sk=#; / S为下推栈 do把下一个输入符号读入Sym中； if(SkVT) j=k; else j=k-1; while(Sj Sym) / 素短语归约可能为若干次

10、 do / 找素短语的头 Q=Sj; if(Sj-1VT) j=j-1; else j=j-2; while(Sj Q); 把Sj+1Sk归约为某个N; k=j+1; Sk=N; / while if( sj Sym | sj=Sym )k=k+1; Sk=Sym; / 移进 else error(); while(Sym=#)n算符优先算法根据运算符优先关系决定最左素短语。n只需知道把最左素短语归约为某一非终结符，不需知道其为何物。n算符优先算法中的归约是非规范归约。n例：已知文法G，用算符优先算法分析 if b then i else i #G: S#S# Sif Eb then E el

11、se E EE+T | T TT*F | F Fi Ebbifthenelse *ib#Ifthenelse*ib#5.2.3 优先函数nf(a)栈内优先函数ng(a)比较优先函数（栈外（源程序）运算符的优先函数）na,bVT 若a b，则f(a) g(b)优先关系数学运算关系n几点说明： 优先函数优先关系表。 有些优先关系表不存在优先函数。 若存在一对优先函数f，g，则存在无穷多对优先函数。 f(a)=f(a)+c g(a)=g(a)+c优先函数算法n用关系图法构造优先函数对aVT(包括#)用下标fa，ga为结点名画出2n个结点；a,bVT ，若a b或a b，则从fa画一箭弧到gb；若a

12、b或 a b，则从gb画一箭弧到fa；给每个结点赋一个数值，此数等于从该结点出发到所能到达结点（包括出发结点自身在内）的个数，赋给fa的数值作为f(a)的值，赋给gb的数值作为g(b)的值；检查所构造出的函数f和g，看它同原来的优先关系表是否矛盾，若没有矛盾，则f和g就是所要的优先函数；若有矛盾，则不存在优先函数。n例：已知文法G： S#S# S*A A* | 0A1求文法所有非终结符的FIRSTVT和LASTVT构造优先关系表如果可能，构造优先函数nFIRSTVT(S)=# LASTVT(S)=# FIRSTVT(S)=* LASTVT(S)=*,1 FIRSTVT(A)=*,0 LASTV

13、T(A)=*,101*#01*#f0f1f*fg0g1g*g01*#f2552g6262优先关系表优先函数关系图S#S#S*AA* | 0A15.2.4 算法优先分析中的出错处理n出错情况： (1)栈顶终结符与下一个输入符间不存在任何优先关系； (2)找到某一“句柄”（素短语），但不存在任一产生式的右部与它匹配。n对第(1)种错误处理方法为：改变、插入或删除符号。n对第(2)种错误处理方法为：打印错误信息（找到类似的产生式右部）。5.3 LR分析法nLR(0)nSLR(1)nLR(1)nLALR(1)5.3.1 LR分析器1.组成 总控程序不依赖于文法 分析表依赖于文法 分析栈 状态栈 文法符

14、号栈2.模型ai#总控程序分析表输入串：状态栈Action表Goto表#S1x1 Smxm符号栈5.3.1 LR分析器3.分析表 Action表a1a2ai an#S0S1SjSmActionSj,ai= Sk(移进) rk(归约) accept 出错Goto表a1a2 an#A1A2 AtS0S1SmGotoSj,Ai=k分析表Action表Goto表a1a2an#A1A2AtS0S1Sm ActionS,a规定了栈顶状态为S时遇到输入符号a应执行的动作：(1)移进：把S,a的下一状态S=GotoS,a和输入符号a推进栈，下一输入符号变成现行输入符号。(2)规约：用产生式A进行归约。若|=r

15、，归约动作为A，则去除栈顶的r个项，使状态Sm-r变成栈顶状态，然后把Sm-r,A的下一状态S=GotoSm-r,A和文法符号A推进栈。(3)接受accetpt：宣布分析成功，停止分析器的工作。(4)报错：发现源程序含有错误，调用出错处理程序。5.3.2 LR(0)项目集族与LR(0)分析表的构造一、前缀、活前缀、可归前缀1.前缀：符号串的任意部首。 abc：，a，ab，abc2.活前缀：文法G的句型，存在规范推导SA，则的前缀称为的活前缀。3.可归前缀： SA则称为可归前缀。 含有句柄的活前缀称为可归前缀。*RR二、LR(0)项目集1.LR(0)项目：文法G的每条规则右部的任意位置加上一圆点

16、构成的式子。 AXYZ AXYZ AXYZ AXYZ AXYZ AX1X2Xi-1Xi Xi+1Xn对应四个项目已在栈内符号尚未进栈符号A 只有一个项目A2.识别文法活前缀的NFA(1)拓广文法 SS 对文法的开始符S加入规则SS例：已知文法G： SE E aA|bB A cA|d B cB|d(2)给出文法的所有LR(0)项目。 凡圆点在串的最右边的项目称为终止项目(归约项目)(3)设项目i为XX1X2Xi-1 XiXn ，项目j为XX1X2Xi Xi+1Xn ，则从项目i画一条弧至项目j。(4)对于项目i为A B (BVN)，则从i画一弧射向B的项目。 Xi例：已知文法G： SE E aA

17、|bB A cA|d B cB|d 1. SE 2. SE 3. EaA 4. EaA 5. EaA6. AcA 7. AcA 8. AcA9. Ad 10. Ad11.EbB 12.EbB 13.EbB14. BcB 15.BcB 16. BcB17. Bd 18. Bd例：已知文法G： SE E aA|bB A cA|d B cB|d 1. SE 2. SE 3. EaA 4. EaA 5. EaA 6. AcA 7. AcA 8. AcA 9. Ad 10. Ad11.EbB 12.EbB 13.EbB 14. BcB 15.BcB16. BcB 17. Bd 18. Bd1311241

18、26717958101813141516acAAEbBBcdd三、LR(0)项目集规范族的构造算法nLR(0)项目集规范族：构成识别一个文法活前缀的DFA的项目集（状态）的全体。n算法：(1)拓广文法GS：增加SS G(2)设I0是拓广文法G的一个状态项目集，定义和构造I的闭包closure(I)。 a) I中项目closure(I) b) 若A B (BVN)，则规定B对应的项目B closure(I)。 c) 重复b)直至closure(I)不再增加为止。(3)状态转换函数Go(Ik,x)=closure(Ij) Ij=A x | A x Ik n如： S Aa|Bb A Cb|d C D

19、e|e Bd Df I=S Aa， S Bb closure(I)=S Aa， S Bb ，B d， A Cb， A d， C De， C e， D f 例：(1) SE (2) EaA (3) EbB (4) AcA (5) Ad (6) B cB (7) Bd构造该文法可识别活前缀的DFA。SEEaAEbBI0EaAAcAAdI2AcAAcAAdI6AcAI7EaAI4AdI5SEI1EbBBcBBdI3BcBBcBBdI10BcBI11EbBI9BdI8abEcAdcBdccABddnSS “接受”态nA B (BVN) 待约项目nA x (xVT) 移进项目nA 归约项目n在同一项目集

20、中后继符号相同则后继状态相同。n在不同项目集中和前面对应相同项目的后继状态相同。四、LR(0)分析表的构造设LR(0)项目集规范族为C=I0,I1,In SS称为初态 (1)若项目AxIk ，GoIk,x=Ij 若xVT，置ActionIk,x=Sj 若xVN，置GotoIk,x=j(2)若项目SSIk ，则置ActionIk,#=acc(3)若项目AIk ，则a VT (包括#)，置ActionIk,a=rj (j指第j条产生式)例：(1) SE (2) EaA (3) EbB (4) AcA (5) Ad (6) B cB (7) Bd构造LR(0)分析表。SEEaAEbBI0EaAAcA

21、AdI2AcAAcAAdI6AcAI7EaAI4AdI5SEI1EbBBcBBdI3BcBBcBBdI10BcBI11EbBI9BdI8abEcAdcBdccABddActionGotoabcd#EAB0S2S311acc2S6S543S10S894r2r2r2r2r25r5r5r5r5r56S6S577r4r4r4r4r48r7r7r7r7r79r3r3r3r3r310S10S81111r6r6r6r6r6对bccd#进行分析： 状态栈 符号栈 输入串1 0 # bccd#2 03 #b ccd#3 0310 #bc cd#4 0310 10 #bcc d#5 0310 10 8 #bccd

22、 #6 0310 10 11 #bccB #7 0310 11 #bcB #8 039 #bB #9 01 #E # accnLR(0)文法 一文法若其LR(0)的分析表无冲突，则称文法为LR(0)文法。nLR(0)项目集相容性 无移进项目、归约项目并存 无归约项目并存5.3.3 SLR分析表的构造n问题的提出real ，i i(0) SS (1) SrD(2) DD,i (3) Di (0) SS (1) SrD(2) DD,i (3) Di I1SSSrDSSI0SrDDD,iDiI2SrDDD,iI3DiI4DD,iI5DD,iI6SrDi，i状态ACTIONGOTOr，iSD0S211

23、ACC2S433r1S5 ,r1r1r14r3r3r3r35S66r2r2r2r2LR(0)分析表产生移进归约冲突(0) SS (1) SrD(2) DD,i (3) Di 状态ACTIONGOTOr，iSD0S211ACC2S433r1S5 ,r1r1r14r3r3r3r35S66r2r2r2r2LR(0)分析表产生移进规约冲突n解决办法：考察当用句柄rD归约成S时，S的后跟符号集FOLLOW(S)。若FOLLOW(S)不包含当前所有移进项目的移进符号集合，则这种移进归约冲突可解决 。nFOLLOW(S)=#，移进符号只有，则在状态3中当遇到，时做“移进”，遇到时做归约。(0) SS (1)

24、 SrD(2) DD,i (3) Di 状态ACTIONGOTOr，iSD0S211ACC2S433r1S5 ,r1r1r14r3r3r3r35S6LR(0)分析表分析表变成状态ACTIONGOTOr，iSD0S211ACC2S433S5r14r3r3r3r35S66r2r2r2r2n假定一个LR(0)规范族中包含项目集(状态)I：I=Xb， A， B，即在该项目集中包含移进归约冲突和归约归约冲突，解决冲突的办法为： 考察FOLLOW(A)和FOLLOW(B),若这两个集合不相交且均不包含b，那么当状态I面临输入符a时，可采用如下决策执行动作： (1)若a=b，则移进； (2)若aFOLLOW

25、(A)，则用A归约； (3)若aFOLLOW(B)，则用B归约。推广至一般：n假定LR(0)规范族的某一个项目集I含有m个移进项目：A1a11， A2a22， Amamm，同时含有n个归约项目 B1， B2， Bn，若a1,a2, ,am，FOLLOW(B1), FOLLOW(Bn)两两不相交，则隐含在I中的动作冲突可通过检查当前输入符a属上述n+1个集合中的哪一个得到解决，方法为： (1)若a是某个ai (i=1,m) ，则移进； (2)若aFOLLOW(Bi) i=1,n ，则用Bi归约； (3)此外，报错。二、SLR(1)分析表的构造方法1.把G拓广为G，对G构造LR(0)项目集C和活前

26、缀识别自动机的状态转换函数。2.设C=I0,I1,In，令SS的Ik的下标k为初态。 (a)若项目Aa属于Ik，且GoIk,a=Ij，a为终结符，则置Actionk,a为Sj； (b)若项目A属于Ik，则对任何终结符a(包括) ，aFOLLOW(A)，置Actionk,a为rj ，j为产生式A在文法中的编号； (c)若项目SS属于Ik，则置Actionk,#为acc； (d)若GoIk,A=Ij，则置Gotok,A=j； (e)凡不能用上述规则填入信息的空白格，均置“出错信息”。n按上述方法构造的含有Action和Goto两部分的分析表，若每个入口不含多重定义（冲突），则该文法称为SLR(1)

27、文法。(0) SS (1) SrD(2) DD,i (3) Di I1SSSrDSSI0SrDDD,iDiI2SrDDD,iI3DiI4DD,iI5DD,iI6SrDi，i状态ACTIONGOTOr， iSD0S211ACC2S433S5 4r3r35S66r2r2SLR(1)分析表FOLLOW(D)=， ,# FOLLOW(S)= # 5.3.4 规范LR分析表的构造 LR(1)分析表n问题的提出文法G：(0) SS (1) SaAd (2) SbAc (3) Saec (4) Sbed (5) Ae I0I1SSSaAdSbAcSaecSbedSSSaAdSaec AeI2SaAdI4Sb

28、ASbAcSbed AeI3Saec AeI5eSbAcI6ASbed AeI7eSaAddI8SaeccI9SbAccI10SbeddI11anI5:Saec ,Ae FOLLOW(A)=c,dc 该文法不是SLR(1)文法nI7:Sbed ,Ae FOLLOW(A)=c,ddLR(0)SLR(1)LR(1)项目集不相容相关集合相交二、LR(1)项目集的构造1.项目I的闭包closure(I) (1)I的任何项目都属于closure(I)； (2)若AB,a closure(I)， B为一产生式，则对bFIRST(a)， B,b closure(I)； (3)重复(2)，直至不产生新项目为止

29、。 二、LR(1)项目集的构造2.转换函数的构造 Go(I,x)=closure(J) J=任何形如Ax,a的项目 | Ax,aI 最初项目集C= SS,# 。n文法G的LR(1)项目集族C的构造算法：Begin C:=closure(SS,# ); Repeat for C中每个项目集I和G的每个符号x， do if Go(I,x)非空且不属于C，Then 把Go(I,x)加入C中 Until C不再增大End例：文法G：(0) SS (1) SBB (2) BaB (3) BbaI1SS，#SBB，#BaB，a/bBb，a/bSS,#SBB,#BaB,# Bb,#I2SaBaB,a/bBa

30、B,a/b Bb,a/bI3SBB,#bI5BI0I4Bb,a/bbaBaB,#BaB,# Bb,#I6Bb,#BI7BaB,#BI9BaB,a/bBI8bba三、LR(1)分析表的构造算法n设项目集族C=I0,I1,In(1)若项目Aa,b属于Ik且GoIk,a=Ij，a为终结符，则置Actionk,a=Sj；(2)若项目A,a属于Ik，置Actionk,a=rj ，j为产生式A在文法中的编号；(3)若项目SS,#属于Ik，则置Actionk,#=acc；(4)若GoIk,A=Ij，则置Gotok,A=j；(5)不能用(1)(4)条填入信息的空白栏均填“出错标志”。状态ACTIONGOTOabSB0S3S4121ACC2S6S7