广工编译原理Chapter7老师自己做的

1、第第7 7章章 LR LR分析法分析法7.1 LR分析法概述7.2 LR(0)分析7.3 SLR(1)分析7.4 LR(1)分析7.5 LALR(1)分析7.6 二义性文法7.1 LR7.1 LR分析分析 LR分析方法是当前最被广泛应用的无回溯的“移进移进- -归约归约”方法。 LR(k)分析技术：这里的“L”是指从左至右扫描输入符号串，“R”是指它的归约过程是最右推导的逆过程，即规范规范归约归约，“k”是指为了作出分析决定而向前看的输入符号的个数。 LR分析器的构造和工作过程 （此处略）7.1 LR分析分析7.2 LR(0)7.2 LR(0)分析分析LR(0)分析法：能力最弱，理论上最重要

2、活前缀 识别活前缀的DFA如何构造 （LR(0)项目集规范族的构造） LR(0)分析表的构造 LR(0)分析法的实现文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B da b b c de步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # abbcde# 移进移进 2） #a bbcde# 移进移进A 3） #ab bcde# 归约归约(Ab) 4） #aA bcde# 移进移进A 5） #aAb cde# 归约归约(AAb) 6） #aA cde# 移进移进 7） #aAc de# 移进移进B 8） #aAcd e# 归约归约(Bd) 9） #aAcB e

3、# 移进移进11） #S # 接受接受S10） #aAcBe # 归约归约(SaAcBe)对输入串对输入串abbcde的移进的移进-规约分析过程规约分析过程活前缀活前缀G =(Vn,Vt ,P,S)，若有 SA,是的前缀，则称是文法G的活前缀。包含了句柄的活前缀称为可归前缀。RR*注意：注意：为使文法开始符号不出现在任何产生式的右部，需对文法进行扩展，例如：G =（S,a,SSa,Sa,S），扩充文法有： G=（S,a,SS, SSa,Sa,S）构造识别活前缀的构造识别活前缀的DFA基本思想：构造LR(0)项目集规范族（构成识别活前缀的DFA的全体状态）(1) LR(0)(1) LR(0)项目

4、项目 在文法中每个产生式的右部的某一个适当位置添加一个圆点构成项目 例： A aBc A.aBc Aa.Bc AaB.c AaBc.项目的含义：圆点的左部表示归约过程中已经处理的部分；圆点的右部表示待处理的部分。LR(0)项目分类:根据圆点所在的位置和圆点后是终结符还是非终结符或为空把项目分为以下几种：移进项目，形如 Aa,a是终结符, ,V* 待约项目，形如 A B, B是非终结符归约项目，形如 A 接受项目，形如 SS, SS 是拓广文法得到新产生式规定：A的LR(0)项目只有A 是归约项目(2) LR(0) (2) LR(0) 项目集的闭包项目集的闭包 若当前项目集包含A X项目，该项目

5、刻画的状态是期望移进First(X)中的某些符号， 假如有产生式Xu，那么有项目X.u，这个项目也是刻画期望移进First(X)中的某些符号的情况。 由于这两个项目刻画的是相同的状态，因此，将这两个项目合并一个项目集。构造识别活前缀的构造识别活前缀的DFA(续续)设I是文法G的一个LR(0)项目集合，closure(I)是从I出发用下面三个规则构造的项目集: I中每一个项目都属于closure(I);若项目ABclosure(I)，且BP 则将B 加进closure(I)中; 复执行(2)直到closure(I)不再增大为止。 例 对拓广文法GS： (0) SS (1) SaA (2) SbB

6、 (3) AcA (4) Ad (5) BcB (6) Bd I=S.Sclosure(I)=S.S, S.aA, S.bB(3) (3) 状态转移函数状态转移函数 若I是G的一个LR(0)项目集, XVTVN GO(I,X)=closure(J) 其中，J=AX|当AXI ，项目AX称为AX的后继。构造识别活前缀的构造识别活前缀的DFA(续续)直观含义: 它规定了识别活前缀的DFA从状态I(项目集)出发，经过X弧所应该到达的状态J(项目集) 。例 对拓广文法GS： (0) SS (1) SaA (2) SbB (3) AcA (4) Ad (5) BcB (6) Bd I=S.S,S.aA,

7、 S.bBGO(I,a)=Sa.A, A.cA, A.d(4) (4) 计算计算LR(0)LR(0)项目集规范族项目集规范族 C=I C=I0 0，I I1 1, .,I, .,In n Procedure itemsets(G); Begin C := CLOSURE (S.S) Repeat For C 中每一项目集I和每一文法符号x Do if GO(I,x) 非空且不属于C Then 把 GO(I,x) 放入C中 Until C 不再增大 End; DFA m= VTVN S , Q 项目集规范族 ， q0= closure S S , Q , =GO（I,X） ）它识别文法G的所有活

8、前缀的自动机。构造识别活前缀的构造识别活前缀的DFA(续续)例：文法GS： (1) SaA (2) SbB (3) AcA (4) Ad (5) BcB (6) Bd 基本思路：1、拓广文法SS2、构造LR(0)项目集规范族3、由状态转换函数建立状态之间的连接关系， 以构造识别活前缀的DFAI I0 0: :S.SS.SS.aAS.aAS.bBS.bBI I1 1: SS.: SS.SI I2 2: :Sa.ASa.AA.cAA.cAA.dA.dabI I3 3: : Sb.BSb.BB.cBB.cBB.d B.d I I4 4:SaA.:SaA.AI5 :Ac.AAc.AA.cAA.cAA.

9、dA.dcI I6 6:A:Ad.d.dI I7 7:SbB.:SbB.BI I8 8: :Bc.BBc.BB.cBB.cBB.dB.dcI I9 9:Bd.:Bd.dI10 :AcA.AcA.AcdI I1111:BcB.:BcB.Bcd问题：识别符号串acd是否为文法的合法句子。 (0) SS (1) SaA (2) SbB (3) AcA (4) Ad (5) BcB (6) Bd LR(0)分析表的构造分析表的构造假定C=I0, I1,，In，令每个项目集Ik的下标k 为分析器的一个状态，因此，G的LR(0)分析表含有状态0，1，n。令那个含有项目SS的Ik的下标k为初态。ACTION

10、和GOTO可按如下方法构造：1 若项目A.a属于Ik且GO (Ik, a)= Ij, a为终结符，则置ACTIONk, a为“Sj”，表示状态k遇上a后转向状态j;2 若项目A属于Ik, 那么，对任何终结符a, 置ACTIONk, a为“rj”，表示当前“用产生式A进行归约”;其中，假定A为文法G的第j个产生式；3 若项目SS属于Ik, 则置ACTIONk, #为“acc” ，表示“可接受”; 4 若GO (Ik, A)= Ij, A为非终结符，则置GOTO(k, A)为“j”;5 分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。 action goto 状态 a b c d #

11、 S A B 0 1 2 3 4 5 6 7 8 9 10 11 s2 s3 acc s5 s6 s8 s9 r1 r1 r1 r1 r1 s5 s6 r4 r4 r4 r4 r4 r2 r2 r2 r2 r2 s8 s9 r6 r6 r6 r6 r6 r3 r3 r3 r3 r3 r5 r5 r5 r5 r5 1 4 7 10 11 按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张LR(0)表。具有LR(0)表的文法G称为LR(0)LR(0)文法。文法。 或对于一个文法的LR(0)的项目集规范族中不存在移进/归约、归约/归约冲突，称这个

12、文法G为LR(0)LR(0)文法。文法。LR分析分析器模型器模型总控程序outputInput#SiXiS1X1S0 #栈状态文法符号ACTION GOTOLR分析表产生式表LR分析程序分析程序 初始化：初始化：状态栈为0，文法符号栈中只有终止符号#，输入队列中有输入符号串 w#； 设置 ip 指向 w# 的第一个符号 重复 begin 令i是状态栈顶元素，a是ip所指向的符号 if ACTIONi,a=Sj /移进移进 then begin PUSH j,a (进状态栈和文法符号栈) ip 前进(指向下一输入符号) endelse if ACTIONi,a=rj (第j条产生式为A) /归约

13、归约LR分析程序分析程序then begin (第j条产生式为A) pop | 项 令当前状态栈顶值为i push GOTOi,A和A(进栈)endelse if ACTIONi,a=acc /接受接受 then return (成功） else if ACTIONi,a=空白 /错误错误 then errorend.重复LR分析程序分析程序例例 GS: S GS: S aAcBeaAcBe A A b b A A AbAb B B d d识别识别abbcdeabbcde是否为文法的句子是否为文法的句子步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0

14、 S2 2） #a bbcde# 移进移进 02 S4 4） #aA bcde# 移进移进 023 S6 6） #aA cde# 移进移进 023 S5 7） #aAc de# 移进移进 0235 S8 9） #aAcB e# 移进移进 02357 S911） #S # 接受接受 01 acc对输入串对输入串abbcde#的的LR分析过程分析过程 3） #ab bcde# 归约归约(Ab) 024 r2 3 5） #aAb cde# 归约归约(AAb) 0236 r3 3 8） #aAcd e# 归约归约(Bd) 02358 r4 710） #aAcBe # 归约归约(SaAcBe) 0235

15、79 r1 1ACTION GOTO a c e b d # S A B 0 S2 1 1 acc 2 S4 3 3 S5 S6 4 r2 r2 r2 r2 r2 r2 5 S8 7 6 r3 r3 r3 r3 r3 r3 7 S9 8 r4 r4 r4 r4 r4 r4 9 r1 r1 r1 r1 r1 r1 状态栈状态栈ACTIONGOTO文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B dSi:移进，将状态移进，将状态i和和输入符输入符进栈进栈ri:归约，用第归约，用第i个产生式归约，同个产生式归约，同时状态栈与符号栈退出相应个符时状态栈与符号栈退出相应个符号

16、，并把号，并把GOTO表相应状态和第表相应状态和第i个产生式的个产生式的左部非终结非终结符入栈。符入栈。例例, ,已知拓广文法已知拓广文法GSGS: (0) S (0) SS (1) SrDS (1) SrD (2) DD,i (3) Di (2) DD,i (3) DiI I0 0: :S.S.S SS.rDS.rDI I1 1: : SS.SS.S Sr rI I2 2: : Sr.DSr.DD.D,iD.D,iD.i D.i I I4 4:D:Di.i.i iI I3 3: :SrD.SrD.DD.,iDD.,iD DI I5 5:DD,.i:DD,.i,iI I6 6:DD,i.:DD

17、,i.问题：问题：其中其中I I3 3中含有移进中含有移进/ /归约冲突归约冲突, ,文法不是文法不是LR(0)LR(0)的，如何解决？的，如何解决？action goto 状态 r , i # S D 0 1 2 3 4 5 6 s2 acc s4 r1 r1,s5 r1 r1 r3 r3 r3 r3 s6 r2 r2 r2 r2 1 3 7.3 SLR(1)分析分析解决冲突的思路：这里仅仅凭LR(0) 项目本身的信息已经无法解决项目之间的冲突，需要向前查看一个符号，再来决定到底是采取移进动作还是归约动作。主要解决方法如下： 如果一个LR(0)项目集规范族中含有如下的项目集II= X b,

18、A 存在移进-规约冲突,但是若FOLLOW(A) b = ，冲突便可以解决7.3 SLR(1)分析（续）分析（续）I=X b, A 当在状态I面临符号a时：1、对 a=b 则actionI,b= closure( X b. )移进2、对 aFOLLOW (A) 则 action I,a= 用 A归约 这种解决方法是比较简单的，因此称作SLR(1)分析，此构造的分析表，称作SLR(1)分析表。假定C=I0,I1,，In，令每个项目集Ik的下标k为分析器的一个状态，因此，G的SLR分析表含有状态0,1，,n。令那个含有项目SS的Ik的下标k为初态。函数ACTION和GOTO可按如下方法构造：1 若

19、项目Aa属于Ik且GO (Ik, a)= Ij, a为终结符，则置ACTIONk, a为“Sj”;2 2 若项目若项目AA属于属于I Ik k, ,那么，对任何输入符号那么，对任何输入符号a,a, aFOLLOW(A), aFOLLOW(A),置置ACTIONk, aACTIONk, a为为“r“rj j”,”,表示表示“用用产生式产生式AA进行归约进行归约”，其中，假定，其中，假定AA为文法为文法GG的第的第j j个产生式；个产生式；SLR(1)分析表的构造分析表的构造3 若项目SS属于Ik, 则置ACTIONk, #为 “acc”,表示“可接受”;4 若GO(Ik, A)=Ij, A为非终

20、结符，则置GOTO(k, A)=j; 5 分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。SLR分析表的构造（续）分析表的构造（续） 按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张改进SLR(1)分析表。具有SLR(1)分析表的文法G称为一个SLR(1)文法。 SLR(1)分析法中的数字1的意思是，在分析过程中顶多只要向前看一个符号。SLR分析表的构造（续）分析表的构造（续）例：文法GS: (0) SS (1) SrD (2) DD,i (3) DiI I2 2: : Sr.DSr.DD.D,iD.D,iD.i D.i I

21、 I0 0: :S.S.S SS.rDS.rDI I1 1: : SS.SS.S Sr rI I4 4:D:Di.i.i iI I3 3: :SrD.SrD.DD.,iDD.,iD DI I5 5:DD,.i:DD,.i,iI I6 6:DD,i.:DD,i.action goto 状态 r , i # S D 0 1 2 3 4 5 6 s2 acc s4 r1 r1,s5 r1 r1 r3 r3 r3 r3 s6 r2 r2 r2 r2 1 3 I3 = SrD. , DD.,I Follow(S)= # I3:FOLLOW(S),=因此可用SLR(1)方法 s5 r1 r3 r3 r2

22、r2例, 已知拓广文法GS(0) S S (1) S L=R (2) S R (3) L *R (4) L id (5) R LI I1 1I I0 0I I3 3I I2 2I I6 6I I9 9I I8 8I I7 7I I5 5I I4 4startstartS SR RL Lidid* *= =ididididL LL LR R* * *R RI I0 0= S= S.S, .S, S S.L=R, S.L=R, S.R, .R, L L. .* *R, LR, L.id, .id, R R.L .L 处在状态 2时，试图构建句子有两条路：1. S L = R 2. S R L SL

23、RSLR（1 1）的局限的局限问题分析：问题分析：follow 集包含了在任何句型中跟在R后的符号但没有严格地指出在一个特定的推导里哪些符号跟在R后。所以需要扩充状态以包含更多的信息。7.4 LR(1)分析法分析法基本思想:如果存在规范推导 S Aw w 当且仅当当前输入的符号为aFirst(w#)时，才能用产生式A进行归约。 因此，在LR(1)方法中重新定义项目,使每个项目附带一个向前搜索符。*RR A.，a A.：核，为LR(0)项目； a：向前搜索符，要么是一个终结符，要么是输入结束标记#。 向前搜索符(lookahead)只对归约项目起作用 A ., a 意味着处在符号栈栈顶形成句柄，

24、当且仅当下一个输入符是a时才能进行归约。 如果有多个向前搜索符，比如a,b,c时，可写作: A u., a/b/c LR(1)项目( 配置）的一般形式：构造构造LR(1)项目集项目集规范族规范族Closure(I)Closure(I)按如下方式构造(I为LR(1)项目集)：1、I的任何项目属closure(I)；2、若A X，aclosure(I)， Xu是一产生式，那么对于FIRST(a)中的每个终结符b， 如果X.u,b不在 closure(I)中，则把它加进去；3、重复（2），直至closure(I)不再增大。GOGO函数函数按如下方式构造：若I是一个项目集，X是一个文法符号GO(I,

25、X)= closure(J) 其中 J= 任何形如AX.,a的项目A.X,aILR(1)项目规范族C的构造算法类同LR(0)的，只是初始时： C= closure(S.S,#)C= closure(S.S,#)例：已知文法GS如下 (1)SBB (2)BaB (3)Bb 基本思路：1、拓广文法：SS2、构造LR(1)项目集规范族3、由状态转换函数建立状态之间的连接关系，以构造识别活前缀的DFAI0:S S,# S BB,# B aB,a/b B b,a/b I1:S S,#I2:S BB,# B aB,#B b,# I5:S BB,#I6:B aB,# B aB,#B b,# I3:B aB,

26、a/b B aB,a/b B b,a/b I4:B b,a/bI7:B b,#I9:B aB,#I8:B aB,a/bsBBabbbBBaaaLR(1)项目集和转换函数bGSGS：(0)S(0)S S (1) S (1)S S BB (2)B BB (2)BaB (3)B aB (3)B b b规范的规范的LR(1)分析表的构造分析表的构造定义： 与LR(0)分析表构造不同的，当状态Ik中包含归约项目A,a时，则 ACTIONk, a为“rj”,其中，假定A为文法G的第j个产生式；按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张规范的LR

27、(1)分析表。具有规范的LR(1)表的文法G称为一个LR(1)文法。LR(1)文法满足下面两个条件1 如果一个项目集里有项目A uxv, a，x是终结符，那就不会有项目B u,x 2 项目集里所有归约项目的向前搜索符不相交，即不能同时含有项目A u,a 和B v,a 0 S3 S4 1 2 1 acc 2 S6 S7 5 3 S3 S4 8 4 r3 r3 5 r1 6 S6 S7 9 7 r3 8 r2 r2 9 r2LR(1)分析表ab#SBACTIONGOTO状态文法GS：(0) S S (1)S BB (2)BaB (3)B b例：GS (0)SS (1)SL=R (2)SR (3)L

28、*R (4)Li (5)RL 判断文法是否是LR(1)文法？LR(1)项目集及转换函数LI1:SS ,#I5:Li ,=/#I7:L*R ,=/#I8:RL ,=/#I9:SL=R ,#I3:SR ,#I12:Li ,#I10:RL ,#I13:L*R ,#I0:S S,# S L=R,# S R,# L *R,=/#L i,=/# R L,# I4: L *R,=/# R L,=/#L i,=/# L *R,=/#I6:S L= R,# R L,# L *R,# L i,# I11:L * R,# R L,# L *R,# L i,# I2:S L =R,# R L,# sR=LRii*ii

29、RLRL*结论:1.不能用SLR(1)方法解决，但能用LR(1)，因 此LR(1)比SLR(1)分析能力强；2.每个SLR(1)文法都是LR(1)文法的，一个文法的LR(1)分析器比其SLR(1)分析器的状态要多。LALR(lookahead LR )基本思想：合并同心集同心集 I3:B a B,a/b B aB,a/b B b,a/b I6: B a B,# B aB,#B b,# I4:B b,a/bI7:B b,#I8:B aB,a/bI9:B aB,#LALR(1)分析法分析法I4和I7I8和I9I36:B a B,a/b/# B aB,a/b/# B b,a/b/# I3和I6I0:

30、S S,# S BB,# B aB,a/b B b,a/b I1:S S,#I2:S B B,# B aB,#B b,# I5:S BB,#I6:B a B,# B aB,#B b,# I3:B a B,a/b B aB,a/b B b,a/b I4:B b,a/bI7:B b,#I9:B aB,#I8:B aB,a/bsBBabbbBBaaaLR(1)项目集和转换函数bGSGS：(0)S(0)S S (1) S (1)S S BB (2)B BB (2)BaB (3)B aB (3)B b b判断文法是否为判断文法是否为LR(1)LR(1)文法和文法和LALR(1)LALR(1)文法。文法。合并同心集同心集I3和I6、I4和I7 、I8和I9 ，得到新项目集I36、I47和I89合并同心集同心集I3和I6 I4和I7 I8和I9 ，得到新项目集I36、I47和I89I0:S S,# S BB,# B aB,a/b B b,a/b I1:S S,#I2:S B B,# B aB,#B b,# I5:S BB,#I36:B a B,a/b/# B aB,a/b/# B b,a/b/# I47:B b,a/b/#I89:B aB,a/b/#sBBabbbBaaGSGS：(0)S(0)S S (1) S (1)S S BB (2