编译原理：第7章 自下而上的LR(k)分析方法

1、第7章 自下而上的LR(k)分析方法 LR(k)文法：从左到右扫描输入串(LR) 自下而上规范归约 向前查看k个输入符号 7.1 LR(k)文法和LR(k)分析器 LR分析器是一个确定的下推自动机，它由一个输入串，一个下推栈和一个带分析表的总控程序组成。 分析表的结构 3 列（状态、 ACTION 、 GOTO ）状态：分析动作表(ACTION)： Sm移进符号，转m状态； r j按产生式j归约； 接收； 出错；goto函数表(GOTO)： K 转K状态； 例如：文法G(E) 1 EE+T 2 ET 3 TT*F 4 TF 5 F(E) 6 FiSLR(1)分析表(右)状态ACTIONGOTO

2、i+*()#ETF0S5S41231S6Acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S5S119r1S7r1r110r3r3r3r311r5r5r5r5LR分析器识别id+id*id栈内容 输入串0 id+id*id#0id5 +id*id# 0F +id*id# 0F3 +id*id# 0T +id*id# 0T2 +id*id# 0E +id*id# 0E1 +id*id#0E1+6 id*id# 0E1+6id5 *id#0E1+6F *id#0E1+6F3 *id#0E1+6T *id#0E1+6T9 *id#0E1+6T9

3、*7 id#0E1+6T9*7id5 #状态ACTIONGOTOid+*()#ETF0S5S41231S6Acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S5S119r1S7r1r110r3r3r3r311r5r5r5r51 EE+T 2 ET3 TT*F 4 TF5 F(E) 6 Fid栈内容 输入串0E1+6T9*7F #0E1+6T9*7F10 #0E1+6T #0E1+6T9 #0E #0E1 #分析表的构造 LR(0)分析表的构造 SLR分析表的构造 LR(1)分析表的构造 LALR分析表的构造 7.2 LR(0)分析表的构造

4、 活前缀 前缀：指符号串的任意首部，包括 活前缀：右边加上一些VT 符号，可构成规范句型LR(0)项目：每个产生式右部在某个位置加上“.” 如：Axyz的项目有四个 A.xyz Ax.yz Axy.z Axyz.拓广文法：如果开始符号S的产生式有多个右部，则另外加SS 产生式，S为开始符号。如 GS：SA | B = GS： SS SA | B 7.2.4 CLOSURE（I）函数 项目集I属于CLOSURE（I）若S.B 属于CLOSURE（I） 则B.也属于CLOSURE（I）如文法G(E) 0 EE 1 EE+T 2 ET 3 TT*F 4 TF 5 F(E) 6 FiCLOSURE(E

5、.E )包括E.EE.E+TE.TT.T*FT.FF.(E)F.i7.2.5 goto(I,X)函数 goto(I,X)=CLOSURE(AX .) | 所有A . X I如 I0：E.EE.E+TE.TT.T*FT.FF.(E)F.igoto(I0,E)=EE. ， EE.+Tgoto(I0,T)=E T. ， TT.*F goto(I0,F)=TF.goto(I0,()=F (.E) ，E.E+T，E.T，T.T*F，T.F，F.(E)，F.igoto(I0,id)=Fi.文法G(E)EEEE+T|TTT*F|FF(E)|i7.2.6 LR(0)项目规范族 拓广文法为：0： ZA1： AB

6、A 2： Ai3： BAB4： Bj LR(0)项目族若S.B 属于CLOSURE（I） 则B.也属于CLOSURE（I）goto(I,X)=CLOSURE(AX .) | 所有A. X ILR(0)项目分析表状态 ACTION GOTO ij#ABI0S3S412I1S3S4Acc56I2S3S472I3r2r2r2I4r4r4r4I5S3S456I6S3/r3S4/r3r372I7S3/r1S4/r1r156拓广文法为：0： ZA1： ABA 2： Ai3： BAB4： Bj LR(0)项目族7.2.7 有效项目 一个项目Ax .y称为对某个活前缀是有效的(valid)，当且仅当存在某个规

7、范推导： S uAv=uxyv其中，xy是句型uxyv的句柄，v是VT串LR(0) 文法移进项目与归约项目不能并存同一项目集。多个归约项目不能并存同一项目集。LR(0)项目分析表的构造A . X Ii，goto(Ii,X)=Ij， 如果X VT，则ACTIONIi,X=SjA . X Ii，goto(Ii,X)=Ij， 如果X VN，则GOTOIi,X=jSS . Ii，则ACTIONIi,#=AccA. Ii，该项目为k产生式的， 则ACTIONIi,v=rk, v VT7.3 SLR分析表的构造 在LR(0)中，每个项目集，如果有归约项目A.，则不能与归约与移进冲突；SLR中，每个项目集，

8、如果有归约项目A.，B.，有移进项目D.b要求：FOLLOW（A）、FOLLOW（B）互不相同，且不含b。例1：文法G(E) EE+T | T TT*F | F F(E) | i例1：文法G(E)0 EE1 EE+T2 ET3 TT*F4 TF5 F(E)6 FiFIRSTFOLLOWEi,(#Ei,(),+,#Ti,(*, ),+,#Fi,(*, ),+,#FIRST()的构造VT，FIRST()= VN，a，a FIRST()； ，FIRST()VN，XY， FIRST(X)- FIRST()， 若X ，则FIRST(Y)- FIRST() FOLLOW（U）的构造 U是开始符号，则# F

9、OLLOW(U) AxUy， 则FIRST(Y)- FOLLOW（U） AxUy，y , (包括AxU) 则FOLLOW(A) FOLLOW(U) 例1：文法G(E)0 EE1 EE+T2 ET3 TT*F4 TF5 F(E)6 Fid例1：文法G(E)SLR分析表0 EE 1 EE+T 2 ET 3 TT*F 4 TF 5 F(E)6 Fid状态ACTIONGOTOid+*()#ETF0S5S41231S6Acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5FIRSTFO

10、LLOWEId,(#EId,(),+,#TId,(*, ),+,#FId,(*, ),+,#SLR项目分析表的构造A.X Ii，goto(Ii,X)=Ij， 如果X VT，则ACTIONIi,X=SjA.X Ii，goto(Ii,X)=Ij， 如果X VN，则GOTOIi,X=jSS . Ii，则ACTIONIi,#=AccA. Ii，该项目为k产生式的， 则ACTIONIi,v=rk, v FOLLOW(A) RrFe FY；F FY Y Yi：t例2：GR： RrFe FY；F | Y Y| i：t例2：GR RrFeFY；F | Y Y| i：t解： RrFe FY；F FY Y Yi：

11、t状态 ACTION GOTO riet;:#FY0S11S4r4r4232S53r3S64S75acc6S4r4r4837S98r29r5r5FIRSTFOLLOWRr#Fi,;, eYi, ;,e例3 GA 不是SLR(1)文法 GAAi:=EEE+EEE*EEiFIRSTFOLLOWAi#Ei#,+,*7.4 规范LR(1)分析表的构造 LR(1) 的项目： A.，bLR(1) 的闭包： A.B，b B.，FIRST（b） 例： G7-3S0 S S1 SCC2 CcC3 Cd LR(1) 的项目： A.B，bLR(1) 的闭包： A.B，b B.，FIRST（b）GS LR(1)分析表

12、状态ACTIONGOTOcd#SC0S3S4121Acc2S6S753S3S484r3r35r16S6S797r38r2r29r20 S S1 SCC2 CcC3 Cd 例2： GZ0 ZS1 SL=R2 SR3 RL4 L*R5 Li LR(1) 的项目： A.B，bLR(1) 的闭包： A.B，b B.，FIRST（b）GZ LR(1)分析表0 ZS1 SL=R2 SR3 RL4 L*R5 Li 状态ACTIONGOTO=*i#SLR0S4S51231Acc2S6r33r24S4S5875r5r56S11S121097r4r48r3r39r110r311S11S12101312r513r4

13、7.5 LALR分析表的构造 LR（1）的项目集同心：除向前看符号外，项目集内容相同；同心合并：不含“移进归约”冲突；可能“归约-归约” 冲突； 例1：GS LALR文法 0 S S1 SCC2 CcC3 Cd状态ACTIONGOTOcd#SC0S36S47121Acc2S36S47536S36S478947r3r3r35r16S6S797r389r2r2r29r2状态ACTIONGOTO=*i#SLR0S4S51231Acc2S6r33r24S4S5875r5r56S11S121097r4r48r3r39r110r311S11S12101312r513r4例：LR(0)分析表(0)SS(1)

14、 SA(2) SB(3) AaAb(4) Ac(5) BaBb(6) Bd状态ACTIONGOTOabcd#ABCI0I1I2I3I4I5I6I7I8I9I10例：构造LR(0)分析表SEEaAEbBAcAAdBcBBd(1)SE (2)EaA(3)EbB (4)AcA(5)Ad (6)BcB(7)Bd状态ACTIONGOTOabcd#EAB1234567891011例：构造LR(0)分析表7.6 无二义性规则的使用简单的无二义规则“移进-归约”冲突，移进优先。“归约-归约”冲突，序号优先文法GS(1) SIF S ELSE S(2) SIF S(3) SS;S(4) Sa拓广GS，简化(0)

15、 SS(1) SiSeS(2) SiS(3) SS;S(4) SaFollow(S)=#,e,;GS的LR(0)项目族(0) SS(1) SiSeS(2) SiS(3) SS;S(4) SaGS的SLR(1)分析表(0) SS(1) SiSeS(2) SiS(3) SS;S(4) SaFollow(s)=#,e,;状态ACTION状态ACTIONaei;#Saei;#S0s3s2151s4acc6s7s4r22s3s257s3s283r4r4r48r1s4r14s3s26GS的LR(1)项目族(0) SS(1) SiSeS(2) SiS(3) SS;S(4) Sa状态ACTIONaei;#S0S3S211S4Acc2S7S653r4r44S3S285S9S10r2r26S7S6117r4r4r48S4r