精品课程《编译原理第7章LR分析》PPT课件.ppt

《精品课程《编译原理第7章LR分析》PPT课件.ppt》由会员分享，可在线阅读，更多相关《精品课程《编译原理第7章LR分析》PPT课件.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第7章章 LR分析分析7.1 LR分析概述Z aBDc aBdc abdcZ aBDc abDc abdcrrrlll设有文法GZ:ZaBDc Bb Dd LR(K)的含义的含义:L表示从左到右扫描输入串，表示从左到右扫描输入串，R表示最左表示最左规约规约(即最右推导的逆过程即最右推导的逆过程)，K表示向右查表示向右查看输入串符号的个数。当看输入串符号的个数。当K=1时，能满足当时，能满足当前绝大多数高级语言编译程序的需要，所以前绝大多数高级语言编译程序的需要，所以着重介绍着重介绍LR(0)，SLR(1)，LR(1)，LALR(1)方法。方法。分析分析特征特征:规范的规范的符符号号栈栈中中的

2、的符符号号是是规规范范句句型型的的前前缀缀，且且不不含含句柄以后的任何符号句柄以后的任何符号(活前缀活前缀)分分析析决决策策依依据据栈栈顶顶状状态态和和现现行行输输入入符符号号 识别活前缀的识别活前缀的 DFA.四种技术LR(0)SLR(1)LR(1)LALR(1)LR(0)文法文法 能力最弱，理论上最重要能力最弱，理论上最重要存在存在FA 识别活前缀识别活前缀识别活前缀的识别活前缀的DFA如何构造如何构造（LR(0)项目集规范族的构造）项目集规范族的构造）LR(0)分析表的构造分析表的构造7.2 LR（0）分析 定义 如果有Z (Z为开始符)，且为终极符串(或空)。称是规范前缀。若是含有句柄

3、的规范前缀,且每个句柄是的后端，称是可归规范前缀。r*例子：SmABcde-mABcdeemABcddemABccdemAB后缀规范前缀 若其中Abc是句柄，根据定义有mABc是可归规范前缀。定理 设1A2为可归前缀，AVN，Au为一产生式，则1u也为可归前缀。例:GZ:ZabAd Ac 若abAd是可归前缀，根据此定理abc也是可归前缀。即：1A2 1u2例:G S :SaAc 1 AAbb 2 Ab 3 求：该文法的可归前缀图123203cabbAb1可归前缀图1bcAa3bbA2S:A:子自动机生成过程：12,34203cabbAb11bcAa3bA2b34120构造可归前缀图方法自动机

4、直观法形式化方法 形式化方法,设BX1X2XnP是产生式P，则称形如X1X2XiXi+1XnP的侯选式为LR(0)项目(简称项目)。(圆点可在X1之前,也可在Xn之后)。定义F称形如X1X2XnP的项目为归约项目。移进项目:除归约项目外的其它形式。F 设I为项目集,则定义Close(I)=I.uP|AuPG,A1Close(I)称Close(I)为I的闭包集。F 设I为项目集,则GO(I,X)=CLOSE(IX)其中IX=X.P|.XPI构造构造LR(0)项目集规范族项目集规范族LR(0)项项目目集集规规范范族族(构构成成识识别别一一个个文文法法的的活活前前缀缀的的DFA的状态的全体的状态的全

5、体)。LR（0）项目或配置（）项目或配置（item or configuration）.-在右端某一位置有圆点的在右端某一位置有圆点的G的产生式的产生式 A xyz A.xyz Ax.yz Axy.z Axyz.如：如：SaAd SaAd S.aAd Sa.Ad SaA.d SaAd.S.aAd Sa.Ad SaA.d SaAd.例子：UXYZ，求项目 UXYZ UXYZ UXYZ UXYZ 移进项目归约项目 可归前缀图的构造算法1.先产生初始项目集I1=Close(.P|ZPG,Z为初始符)。2.若I是新项目集,则对每X(VNVT),产生项目集GO(I,X)。若两项目集完全相同,则作为一项目

6、集。3.重复2至不产生新项目集为止。4.图的结点由上述项目集组成,且若GO(Ii,X)=Ij,则有Ii Ij。x例:G(S):SaAc 1 AbB2|ba3 BdB4|e 5 0:S.aAc 1a1:a.Ac1 .bB2 .ba3A2:aA.c11:a.Ac1 .bB2 .ba3caAc.1b1:a.Ac1 .bB2 .ba33:b.B2 b.a3 .dB4 .e5BbB.23:b.B2 b.a3 .dB4 .e5aba.33:b.B2 b.a3 .dB4 .e5e e.53:b.B2 b.a3 .dB4 .e5d4:d.B4.dB4 .e53:b.B2 b.a3 .dB4 .e5BdB.44

7、:d.B4.dB4 .e5e4:d.B4.dB4 .e5d4:d.B4.dB4 .e5 定义 二义性结点：可归前缀图的一个结点包含多个归约项目或同时包含移进项目和归约项目。Aa.SBD.移进、归约冲突AaS.BD.归约、归约冲突例：LR(0)文法：文法的可归前缀图不包含二义性结点(可用于判是否LR(0)文法)。LR分析法的分析栈由两个栈组成：状态栈、符号栈。例子：AaBc Ba BabLR分析法的步骤：格局为(0 1i,#X0X1Xi,ajaj+1an#)状态栈 符号栈 输入流 1.若ACTIONi,aj=sk,则有(0 1K,#X0X1Xi,ajaj+1an#)。2.若ACTIONi,aj=

8、rp,则先把符号栈归约Ap(P产生式的左部),从状态栈删除 np(为侯选式的长度)个状态(后端),再压入=Gotoi-np,Ap有(0i-np,#X0XiAp,ajaj+1an#)。3.若ACTIONi,aj=ok,则成功。4.若ACTIONi,aj=en,则失败。分析法的动作:Sjs表示“移进”,j表压入编号rjr表示“归约”,j表产生式号 ok表示分析成功eje表示错误,j表错误编号 例：G(E):EaA|bB AcA|d BcB|d1.用形式化方法作可归前缀图。2.求LR(0)矩阵。3.写出输入串bccd的LR(0)分析过程。解：可归前缀图 G(S):SE 0 EaA1 EbB2 AcA

9、3 Ad 4 BcB5 Bd 6 解：拓展文法的新文法如下：0:S.E E.bB E.aAE1:SE.0:S.E E.bB E.aAa2:Ea.A A.d A.cA0:S.E E.bB E.aAA6:EaA.2:Ea.A A.d A.cAd10:Ad.2:Ea.A A.d A.cAc4:Ac.A A.d A.cA2:Ea.A A.d A.cAd4:Ac.A A.d A.cAc4:Ac.A A.d A.cAA8:AcA.4:Ac.A A.d A.cAb0:S.E E.bB E.aA3:Eb.B B.d B.cBB7:EbB.3:Eb.B B.d B.cBd11:Bd.3:Eb.B B.d B.c

10、Bc5:Bc.B B.cB B.d3:Eb.B B.d B.cBd5:Bc.B B.cB B.dc5:Bc.B B.cB B.dB9:BcB.5:Bc.B B.cB B.d解：LR(0)矩阵 s表示状态 r表示归约r4r4r4r4r4r4r4r4r4r41010r6r6r6r6r6r6r6r6r6r61111r5r5r5r5r5r5r5r5r5r59 9r3r3r3r3r3r3r3r3r3r38 8r2r2r2r2r2r2r2r2r2r27 7r1r1r1r1r1r1r1r1r1r16 69 9S11S11S5S55 58 8S10S10S4S44 47 7S11S11S5S53 36 6S1

11、0S10S4S42 2AccAcc1 11 1S3S3S2S20 0B BA AE E#d dc cb ba aGotoGotoActionAction状态状态 LR(0)分析过程的关键点：1.用分析栈的栈顶元素对输入串的第一个元素查矩阵，以确定下一步的动作。2.每一步都要保持分析栈和符号栈长度一致。3.归约时，符号栈的元素（产生式的右部）弹出栈时，等长的分析栈元素同时弹出栈，以保持两栈长度一致。4.归约时，产生式的左部压进符号栈时，分析栈压进分析栈栈顶元素对产生式左边查goto矩阵得到的状态编号。例如：第5步：用Bd归约,d，(11)出栈，B进栈；5对B查表得9。动画演示动画演示S11d#b

12、cc03554S5cd#bc0353S5ccd#b032S3bccd#01GOTO Action 输入串 符号栈 状态栈 步骤 r6#bccd0355(11)59r6#bccB03555r5#bccB0355969r5#bcB0356 解：串bccd的LR(0)分析过程acc#E0191r2#bB03787r5#bcB035979r5#bccB0355969r6#bccd0355(11)5S11d#bcc03554S5cd#bc0353S5ccd#b032S3bccd#01GOTO Action 输入串 符号栈 状态栈 步骤 分析分析器模型器模型总控程序outputInput#S1 XmS1X

13、1S0#栈状态文法符号ACTION GOTOLR分析表产生式表例例 GS为为:S a A c B e A b A Ab B d 1)构造识别活前缀的构造识别活前缀的DFA 2)构造它的构造它的LR(0)分析表。分析表。3)分别给出对输入分别给出对输入符号串符号串abbcdeabbcde和和 Abbce Abbce的的LR(0)分析步骤。分析步骤。GS拓广拓广为为:S S S a A c B e A b A Ab B dI I0:S S S a A c B e I I1:S S I I2:S a A c B e A b A AbI I3:S a A c B e A A bI I4:A b I I

14、5:S a A c B e B dI I7:S a A c B eI I8:B d I I9:S a A c B e I I6:A A b SaAbbcBedGL=abbcdeGS的的LR(0)分析表分析表Step states.Syms.The rest of inputaction goto 1 0#abbcde#s2 2 02#a bbcde#s4 3 024#ab bcde#r2 3 4 023#aA bcde#s6 5 0236#aAb cde#r3 3 6 023#aA cde#s5 7 0235#aAc de#s8 8 02358#aAcd e#r4 7 9 02357#aAcB

15、 e#s9 10 023579#aAcBe#r1 1 11 01#S#acc 对输入串对输入串abbcde#的分析过程的分析过程Step states.Syms.The rest of inputaction goto 1 0#abbce#s2 2 02#a bbce#s4 3 024#ab bce#r2 3 4 023#aA bce#s6 5 0236#aAb ce#r3 3 6 023#aA ce#s5 7 0235#aAc e#出错出错说明说明abbce#abbce#不是例不是例6.1 6.1 文法文法 GS GS的的句子句子 对输入串对输入串abbce#的分析过程的分析过程 当有I=x

16、b Ar时，为移进-归约冲突，如果FOLLOW(A)b=；或当有I=Ar B时，为归约-归约冲突，如果FOLLOW(A)FOLLOW(B)=,则称该冲突可以解决。7.3 SLR（1）分析 SLR(1)方法:是只在LR(0)可归前缀图的二义性状态下向前看一符。当有I=xb Ar B FOLLOW(A)FOLLOW(B)=,FOLLOW(A)b=；FOLLOW(B)b=则称该冲突可以解决。满足上述条件则可利用SLR(1)方法例：有项目集 SAa.bBc Ad.Be.设：FOLLOW(A)=a，FOLLOW(B)c所以：FOLLOW(A)FOLLOW(B)=,FOLLOW(A)b=；FOLLOW(B

17、)b=所以本文法是SLR(1)文法。现举实型变量说明文法为例：real，ii将该文法缩写后并拓广为G如下：1.SS 0 2.SrD 1 3.DD,i 2 4.Di 3 得图如下：0:S.S S.rDS1:SS.r2:Sr.D D.D,i D.iD3:SrD.DD.,ii4:Di.,5:DD,.ii6:DD,i.冲突实数说明文法的LR(0)分析表如下：r2r2r2r26S65r3r3r3r34r1r1r1,S5r133S42Acc11S20DS#i,rGotoAction状态解释冲突：SrDDD,i为归约项为移进项follow(S)=follow(S)=#follow(S),=#,=满足上述条件

18、则可利用SLR(1)方法。转化情况如下：实数说明文法的SLR(1)分析表如下：r2r2r2r26S65r3r3r3r34r1S533S42Acc11S20DS#i,rGotoAction状态 LR（1）项目）项目(配置）的一般形式配置）的一般形式 A .，a 意味着处在栈顶是 的相应状态，期望相应的相应状态，期望相应 在栈顶的状态，然后只有当跟在跟在 后的token是终结符a时进行归约时进行归约。a 称作该项目项目(配置）配置）的向前搜索符（lookahead）向前搜索符（lookahead）只对圆点在最后的项目起作用A ,a.意味着处在栈中是 的相应状态，但的相应状态，但只有当下一个输入符是

19、a时才能进行归约时才能进行归约.a 要么是一个终结符，要么是输入结束标记#有多个向前搜索符，比如a,b,c时，可写作 A u,a/b/c7.4 LR（1）分析 LR(1)项目:即为二元组,a,其中是LR(0)项目,aVT#。定义3.17 设I为LR(1)项目集,则定义 Close(I)=I.p,b|BpG,.Be,aClose(I),bfirst(a)称Close(I)为I的闭包。F GO(I,X)=Close(IX)其中IX=X.p,b|.Xp,bI例子：若文法GS为：SS0 SBB1 BaB2 Bb3则其转换图和分析表如下：I0:SS,#I0:SS,#SBB,#BaB,a|b Bb,a|b

20、求初始项目集：求初始项目集的闭包集：I0:SS,#SBB,#BaB,a|b Bb,a|bI1:SS,#SI4:Bb,a|bbbI3:BaB,a|b BaB,a|b Bb,a|ba.aI8:BaB,a|bBBI6:BaB,#BaB,#Bb,#I5:SBB,#I7:Bb,#I2:SBB,#BaB,#Bb#I9:BaB,#BBbbaar r2 2r r2 28 8r r2 29 9r r3 37 79 9S S7 7S S6 66 6r r1 15 5r r3 3r r3 3 4 48 8S S4 4S S3 3 3 35 5S S7 7S S6 62 2accacc1 12 21 1S S4 4S

21、 S3 3 0 0B BS S#b ba aGOTO GOTO ACTION ACTION 状态状态 LR(1)比比SLR（1）能力强）能力强例例 设有文法设有文法GS(0)SS(1)SL=RL=R(2)SR(2)SR(3)L*R(3)L*R(4)Lid(4)Lid(5)RL(5)RL该文法不能用该文法不能用SLR（1）技术解决，但能用）技术解决，但能用LR（1）I1: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,#I

22、4: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*iiRLLRL*例 LR(1)项目集及转换函数 每个每个SLR（1）文法都是）文法都是LR（1）的，一个）的，一个SLR（1）文法的规范）文法的规范LR分析器比其分析器比其SLR（1）分）分析器的状态要多。析器的状态要多。例子：若文法例子：若文法GSGS为：为：SS0 SS0 SBB1 SBB1 BaB2 BaB2 Bb3 Bb3（注：与前例文法同）（注：与前例文法同）LALR1LAL

23、R1方法：方法：同心项目集合：同心项目集合：I0:S.S S.BB B.aB B.bI1:S S.I2:S B.B B.aB B.bI3:Ba.B B.aB B.b I4:BaB.I5:Bb.I6:SBB.I0:S S,#S BB,#B aB,a/bB b,a/b I1:S S,#I2:S BB,#B aB,#B b,#I5:S BB,#I6:S aB,#B aB,#B b,#I3:B aB,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)项目集和转换函数b LALR在在SLR（1）和）和L

24、R（1）间寻）间寻找折衷办法（状态数目，分析能力）找折衷办法（状态数目，分析能力）LALR(lookahead LR)合并同心集合并同心集I36 I47 I89I3:B aB,a/b B aB,a/b B b,a/b I6:S aB,#B aB,#B b,#I4:B b,a/bI7:B b,#I8:B aB,a/bI9:B aB,#构造构造 LALR(1)分析表分析表.方法方法11.构造文法G的规范 LR(1)状态.2.合并同心集（除搜索符外两个集合是相同的）的状态.3.新 LALR(1)状态的GO函数是合并的同心集状态的GO函数的并.4.LALR(1)分析表的action 和 goto 登录

25、方法与LR(1)分析表一样.经上述步骤构造的表若不存在冲突，则称它为G的LALR(1)分析表。存在这种分析表的文法称为LALR（1）文法。LR(0)、SLR(1)、LR(1)、LALR(1)方法比较方法比较实际上不同实际上不同LR方法之间的主要区别就在于归约的判方法之间的主要区别就在于归约的判定方法上：定方法上：LR(0)是不看展望符判定归约；是不看展望符判定归约；SLR(1)是看展望符，但把所有是看展望符，但把所有B 的展望符集的展望符集均定义为均定义为Follow(B)。即把符号栈顶上的句柄即把符号栈顶上的句柄 归约归约为为B的条件是：展望符为的条件是：展望符为Follow(B)中的元素。

26、换句中的元素。换句话说，归约任何位置上的话说，归约任何位置上的B，都用统一的展望符集；都用统一的展望符集；LR(1)也是看展望符，但归约不同位置上的也是看展望符，但归约不同位置上的B时，采时，采用不同的展望符集。每个用不同的展望符集。每个项由心与向前搜索符组成，项由心与向前搜索符组成，搜索符长度为搜索符长度为1 1。由于由于LR(1)方法对于归约条件的判方法对于归约条件的判定比定比SLR(1)更精确，可大大减少移入更精确，可大大减少移入/归约冲突；归约冲突；LALR(1):LALR(1):对对LR(1)LR(1)项目集规范族合并同心集项目集规范族合并同心集LR(0)LR(0)、SLR(1)SL

27、R(1)、LR(1)LR(1)、LALR(1)LALR(1)分析表比较分析表比较LR(0)LR(0)分析表局限性大，但其构造方法是其他分析表局限性大，但其构造方法是其他构造方法的基础；构造方法的基础；SLRSLR分析表虽然不是对所有文法都存在，但这分析表虽然不是对所有文法都存在，但这种分析表较易实现又极有使用价值；种分析表较易实现又极有使用价值；LRLR分析表的分析能力最强，能适用于一大类分析表的分析能力最强，能适用于一大类文法，但是，实现代价过高（表过大）；文法，但是，实现代价过高（表过大）；LALRLALR分析表的能力介于分析表的能力介于SLRSLR和和LRLR之间，实现效之间，实现效率较高。率较高。总结：语法分析自顶向下递归子程序法LL(1)方法自底向上简单优先方法算符优先法LR方法LR(0)SLR(1)LR(1)LALR(1)