PPT课件第7章LR分析.ppt

第第7章章 LR分析分析7.1 LR分析概述Z aBDc aBdc abdcZ aBDc abDc abdcrrrlll设有文法G[Z]:Z→aBDc B→b D→d  LR(K)的含义的含义: L表示从左到右扫描输入串，表示从左到右扫描输入串，R表示最左表示最左规约规约(即最右推导的逆过程即最右推导的逆过程)，，K表示向右查看表示向右查看输入串符号的个数当输入串符号的个数当K=1时，能满足当前时，能满足当前绝大多数高级语言编译程序的需要，所以着绝大多数高级语言编译程序的需要，所以着重介绍重介绍LR(0)，，SLR(1)，，LR(1)，，LALR(1)方方法ＬＲ分析特征特征:．规范的范的．符符号号栈中中的的符符号号是是规范范句句型型的的前前缀，，且且不不含含句句柄以后的任何符号柄以后的任何符号(活前活前缀)．分分析析决决策策依依据据――栈顶状状态和和现行行输入入符符号号．． 识别活前活前缀的的 DFA.四种技术LR(0) SLR(1) LR(1) LALR(1) LR(0)文法文法 能力最弱，理能力最弱，理论上最重要上最重要存在存在FA 识别活前活前缀识别活前活前缀的的DFA如何构造如何构造（（LR(0)项目集目集规范族的构造）范族的构造）LR(0)分析表的构造分析表的构造7.2 LR（0）分析 定义 如果有Z αβ(Z为开始符)，且β为终极符串(或空)。

称α是规范前缀若α是含有句柄的规范前缀,且每个句柄是α的后端，称α是可归规范前缀r*例子：SmABcde-mABcdeemABcddemABccdemAB后缀规范前缀 若其中Abc是句柄，根据定义有mABc是可归规范前缀 定理 设α1Aα2为可归前缀，A∈VN，A→u为一产生式，则α1u也为可归前缀例: G[Z]: Z→abAd A→c 若abAd是可归前缀，根据此定理abc也是可归前缀即：α1Aα2  α1uα2例: G [ S ] : S→aAc [1] A→Abb [2] A→b [3] 求：该文法的可归前缀图123[2]0[3]cabbAb[1]可归前缀图[1]bcAa[3]bbA[2]S:A:子自动机生成过程：12,34[2]0[3]cabbAb[1][1]bcAa[3]bA[2]b34120构造可归前缀图方法自动机直观法形式化方法 形式化方法,设B→X1X2…Xn[P]是产生式P，则称形如X1X2…XiXi+1…Xn[P]的侯选式为LR(0)项目(简称项目)。

圆点可在X1之前,也可在Xn之后) 定义F称形如X1X2…Xn●[P]的项目为归约项目移进项目:除归约项目外的其它形式F 设I为项目集,则定义Close(I)=I∪{.u[P]|A→u[P]∈G, α●Aβ[1]∈Close(I)} 称Close(I)为I的闭包集 F 设I为项目集,则GO(I,X)=CLOSE(IX) 其中IX={αX.β[P]|α.Xβ[P]∈I}构造LR(0)项目集规范族LR(0)项目目集集规范范族族(构构成成识别一一个个文文法法的的活活前前缀的的DFA的的状状态的全体的全体) LR（（0））项目或配置（目或配置（ item or configuration）.---在右端某一位置有在右端某一位置有圆点的点的G的的产生式生式 A xyz A.xyz Ax.yz Axy.z Axyz. 如：如：S→aAd S→aAd S→.aAd S→a .Ad S→aA .d S→aAd . S→.aAd S→a .Ad S→aA .d S→aAd . 例子： U→XYZ，求项目 U→XYZ U→XYZ U→XYZ U→XYZ 移进项目归约项目 可归前缀图的构造算法1.先产生初始项目集I1=Close({.α[P] |Z→α[P]∈G,Z为初始符})。

2.若I是新项目集,则对每X∈(VN∪VT),产生项目集GO(I,X)若两项目集完全相同,则作为一项目集3.重复2至不产生新项目集为止4.图的结点由上述项目集组成,且若GO(Ii,X)=Ij,则有Ii Ij x例: G(S): S→aAc [1] A→bB[2]|ba[3] B→dB[4]|e [5] 0:S→.aAc [1]a1:a.Ac[1] .bB[2] .ba[3]A2:aA.c[1]1:a.Ac[1] .bB[2] .ba[3]caAc.[1]b1:a.Ac[1] .bB[2] .ba[3]3:b.B[2] b.a[3] .dB[4] .e[5]BbB.[2]3:b.B[2] b.a[3] .dB[4] .e[5]aba.[3]3:b.B[2] b.a[3] .dB[4] .e[5]e e.[5]3:b.B[2] b.a[3] .dB[4] .e[5]d4:d.B[4] .dB[4] .e[5]3:b.B[2] b.a[3] .dB[4] .e[5]BdB.[4]4:d.B[4] .dB[4] .e[5]e4:d.B[4] .dB[4] .e[5]d4:d.B[4] .dB[4] .e[5] 定义Ø 二义性结点：可归前缀图的一个结点包含多个归约项目或同时包含移进项目和归约项目。

A→a.SB→D.移进、归约冲突A→aS.B→D.归约、归约冲突例：Ø LR(0)文法：文法的可归前缀图不包含二义性结点(可用于判是否LR(0)文法) LR分析法的分析栈由两个栈组成：状态栈、符号栈例子：A→aBc B→a B→abLR分析法的步骤：格局为(0 1…i,#X0X1…Xi,ajaj+1…an#) 状态栈 符号栈 输入流 1.若ACTION[i,aj]=sk,则有(0 1…K, #X0X1…Xi,ajaj+1……an#) 2.若ACTION[i,aj]=rp,则先把符号栈归约Ap(P产生式的左部),从状态栈删除 np(为侯选式的长度)个状态(后端),再压入=Goto[i-np,Ap]有(0…i-np , #X0…XiAp,ajaj+1…an#)  3.若ACTION[i,aj]=ok,则成功 4.若ACTION[i,aj]=en,则失败 分析法的动作:Sj—s表示“移进”,j表压入编号rj—r表示“归约”,j表产生式号 ok—表示分析成功ej—e表示"错误",j表错误编号 例： G(E): E→aA|bB A→cA|d B→cB|d1.用形式化方法作可归前缀图。

2.求LR(0)矩阵3.写出输入串bccd的LR(0)分析过程 解：可归前缀图 G(S): S→E [0] E→aA[1] E→bB[2] A→cA[3] A→d [4] B→cB[5] B→d [6] 解：拓展文法的新文法如下：0:S→.E E→.bB E→.aAE1:S→E.0:S→.E E→.bB E→.aAa2:E→a.A A→.d A→.cA0:S→.E E→.bB E→.aAA6:E→aA.2:E→a.A A→.d A→.cAd10:A→d.2:E→a.A A→.d A→.cAc4:A→c.A A→.d A→.cA2:E→a.A A→.d A→.cAd4:A→c.A A→.d A→.cAc4:A→c.A A→.d A→.cAA8:A→cA.4:A→c.A A→.d A→.cAb0:S→.E E→.bB E→.aA3:E→b.B B→.d B→.cBB7:E→bB.3:E→b.B B→.d B→.cBd11:B→d.3:E→b.B B→.d B→.cBc5:B→c.B B→.cB B→.d3:E→b.B B→.d B→.cBd5:B→c.B B→.cB B→.dc5:B→c.B B→.cB B→.dB9:B→cB.5:B→c.B B→.cB B→.d解：LR(0)矩阵 s表示状态 r表示归约r4r4r4r4r4r4r4r4r4r41010r6r6r6r6r6r6r6r6r6r61111r5r5r5r5r5r5r5r5r5r59 9r3r3r3r3r3r3r3r3r3r38 8r2r2r2r2r2r2r2r2r2r27 7r1r1r1r1r1r1r1r1r1r16 69 9S11S11S5S55 58 8S10S10S4S44 47 7S11S11S5S53 36 6S10S10S4S42 2AccAcc1 11 1S3S3S2S20 0B BA AE E# #d dc cb ba aGotoGotoActionAction状态状态 LR(0)分析过程的关键点： 1.用分析栈的栈顶元素对输入串的第一个元素查矩阵，以确定下一步的动作。

2.每一步都要保持分析栈和符号栈长度一致 3.归约时，符号栈的元素（产生式的右部）弹出栈时，等长的分析栈元素同时弹出栈，以保持两栈长度一致 4.归约时，产生式的左部压进符号栈时，分析栈压进分析栈栈顶元素对产生式左边查goto矩阵得到的状态编号例如：第5步：用B→d归约,d，(11)出栈，B进栈；5对B查表得9动画演示动画演示S11d##bcc03554S5cd##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 Xm…S1…X1S0#栈状态文法符号ACTIONGOTOLR分析表产生式表例例 G[S]为为: S a A c B e A b A Ab B d 1)构造构造识别活前活前缀的的DFA 2)构造它的构造它的LR(0)分析表。

分析表 3)分分别给出出对输入入符号串符号串abbcdeabbcde和和 AbbceAbbce的的LR(0)分析步分析步骤G[S]拓广拓广为为: 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 I5 : 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 •SaAbbcBedG[L]= abbcdeG[S]的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 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 文法文法 G[S]G[S]的的句子句子 对输入串对输入串abbce#的分析过程的分析过程 当有I={x→●b A→r●}时，为移进-归约冲突， 如果FOLLOW(A)∩b=； 或当有I={A→r● B→●}时，为归约-归约冲突， 如果FOLLOW(A)∩FOLLOW(B)=,则称该冲突可以解决。

7.3 SLR（1）分析 SLR(1)方法:是只在LR(0)可归前缀图的二义性状态下向前看一符 当有I={x→●b A→r● B→●} FOLLOW(A)∩FOLLOW(B)=, FOLLOW(A)∩b=； FOLLOW(B)∩b= 则称该冲突可以解决满足上述条件则可利用SLR(1)方法例：有项目集 S→Aa.bBc A→d. B→e.设：FOLLOW(A)=a，FOLLOW(B)＝c所以：FOLLOW(A)∩FOLLOW(B)=, FOLLOW(A)∩b=； FOLLOW(B)∩b= 所以本文法是SLR(1)文法现举实型变量说明文法为例：<实型变量说明>→real<标识符表><标识符表>→<标识符表>，i<标识符表>→i将该文法缩写后并拓广为G’如下： 1.S’→S [0] 2.S→rD [1] 3.D→D,i [2] 4.D→i [3] 得图如下：0:S’→.S S→.rDS1:S’→S.r2:S→r.D D→.D,i D→.iD3:S→rD. D→D.,ii4:D→i.,5:D→D,.ii6:D→D,i.冲突实数说明文法的LR(0)分析表如下：r2r2r2r26S65r3r3r3r34r1r1r1,S5r133S42Acc11S20DS#i,rGotoAction状态解释冲突：S→rD●D→D●,i为归约项为移进项follow(S)=follow(S’)={#}follow(S)∩{,}={#}∩{,}=φ 满足上述条件则可利用SLR(1)方法。

转化情况如下：实数说明文法的SLR(1)分析表如下：r2r2r2r26S65r3r3r3r34r1S533S42Acc11S20DS#i,rGotoAction状态 LR（（1））项目目( 配置）的一般形式配置）的一般形式[ A  .  ，， a ]意味着处在栈顶是 的相的相应状状态，期望相，期望相应 在栈顶的状态，然后只有当跟在跟在 后的token是终结符a时进行行归约 a 称作该项目目( 配置）配置） 的向前搜索符（ lookahead ）向前搜索符（ lookahead ）只对圆点在最后的项目起作用A –>     •, a.意味着处在栈中是   的相的相应状状态，但，但只有当下一个输入符是a时才能才能进行行归约. a 要么是一个终结符，要么是输入结束标记#有多个向前搜索符，比如a,b,c时，可写作 A –> u•, a/b/c7.4 LR（1）分析 LR(1)项目:即为二元组[α,a],其中α是LR(0)项目,a∈VT∪｛#｝ 定义3.17 设I为LR(1)项目集,则定义 Close(I)=I∪{[.β[p],b]| B→β[p]∈G, [α.Bω[e],a]∈Close(I), b∈first(ωa)} 称Close(I)为I的闭包。

F GO(I,X)=Close(IX)其中IX={[αX.β[p],b]|[α.Xβ[p],b]∈I}例子：若文法G’[S’]为： S’→S[0] S→BB[1] B→aB[2] B→b[3]则其转换图和分析表如下： I0:S’→●S,#I0:S’→●S,# S→●BB,# B→●aB,a|b B→●b,a|b求初始项目集：求初始项目集的闭包集：I0:S’→●S,# S→●BB,# B→●aB,a|b B→●b,a|bI1:S’→S●,#SI4:B→b●,a|bbbI3:B→a●B,a|b B→●aB,a|b B→●b,a|ba.aI8:B→aB●,a|bBBI6:B→a●B,# B→●aB,# B→●b,#I5:S→BB●,#I7:B→b●,#I2:S→B●B,# B→●aB,# B→●b#I9:B→aB●,#BBbbaar 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 S3 3 0 0B BS S# #b ba aGOTO GOTO ACTION ACTION 状态状态 LR(1)比SLR（1）能力强例例 设有文法有文法G[S’] (0) S`→→S (1)S→L=R→L=R(2)S→R(2)S→R(3)L→ *R(3)L→ *R(4)L→id(4)L→id(5)R→L(5)R→L该文法不能用文法不能用SLR（（1）技）技术解决，但能用解决，但能用LR（（1））I1:S’S •,#I5:Li •,=/#I7:L*R •,=/#I8:RL •,=/#I9:SL=R •,#I3:SR •,#I12:Li •,#I10:RL •,#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*iiRLLRL***例 LR(1)项目集及转换函数￿￿￿￿￿￿￿￿每个SLR（1）文法都是LR（1）的，一个SLR（1）文法的规范LR分析器比其SLR（1）分析器的状态要多。

例子：若文法例子：若文法G[SG[S’] ]为：为： S S’→S[0]→S[0] S→BB[1] S→BB[1] B→aB[2] B→aB[2] B→b[3] B→b[3]（注：与前例文法同）（注：与前例文法同）LALR1LALR1方法：方法：同心同心项目集合：目集合：I0:S’.S S .BB B .aB B .bI1:S’ S.I2:S B.B B.aB B.bI3:Ba.B B.aB B.b I4:BaB. I5: Bb.I6: SBB.I0:S’ S, # S BB, #B aB, a/bB b, a/b I1:S’ S, #I2:S BB, # B aB, #B b, # I5:S BB, #I6:S 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)项目集和转换函数b￿￿￿￿￿￿￿￿￿￿LALR—在SLR（1）和LR（1）间寻找折衷办法（状态数目，分析能力）LALR (lookahead LR)合并同心集合并同心集I36 I47 I89I3:B aB, a/b B aB, a/b B b, a/b I6:S aB, # 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 登录方法与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)中的元素中的元素换句句话说，，归约任何位置上的任何位置上的B，都用，都用统一的展望符集；一的展望符集；ØLR(1)也是看展望符，但也是看展望符，但归约不同位置上的不同位置上的B时，采，采用不同的展望符集每个用不同的展望符集每个项由心与向前搜索符由心与向前搜索符组成，成，搜索符搜索符长度度为1 1由于LR(1)方法方法对于于归约条件的判条件的判定比定比SLR(1)更精确，可大大减少移入更精确，可大大减少移入/归约冲突；冲突；ØLALR(1): LALR(1): 对LR(1)LR(1)项目集目集规范族合并同心集范族合并同心集LR(0)LR(0)、、SLR(1)SLR(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)。