1、2021/7/2312021/7/2327.1 LR分析概述Z aBDc aBdc abdcZ aBDc abDc abdcrrrlll设有文法GZ:ZaBDc Bb Dd 2021/7/233 LR(K)的含义的含义:L表示从左到右扫描输入串，表示从左到右扫描输入串，R表示最左表示最左规约规约(即最右推导的逆过程即最右推导的逆过程)，K表示向右查表示向右查看输入串符号的个数。当看输入串符号的个数。当K=1时，能满足当时，能满足当前绝大多数高级语言编译程序的需要，所以前绝大多数高级语言编译程序的需要，所以着重介绍着重介绍LR(0)，SLR(1)，LR(1)，LALR(1)方法。方法。2021/
2、7/234分析分析特征特征:规范的规范的符号栈中的符号是规范句型的前缀，且不符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号含句柄以后的任何符号(活前缀活前缀)分析决策依据分析决策依据栈顶状态和现行输入符栈顶状态和现行输入符号号 识别活前缀的识别活前缀的 DFA.四种技术LR(0)SLR(1)LR(1)LALR(1)2021/7/235 LR(0)文法文法 能力最弱，理论上最重要能力最弱，理论上最重要存在存在FA 识别活前缀识别活前缀识别活前缀的识别活前缀的DFA如何构造如何构造（LR(0)项目集规范族的构造）项目集规范族的构造）LR(0)分析表的构造分析表的构造7.2 LR（0）分析
3、2021/7/236 定义 如果有Z (Z为开始符)，且为终极符串(或空)。称是规范前缀。若是含有句柄的规范前缀,且每个句柄是的后端，称是可归规范前缀。r*2021/7/237例子：SmABcde-mABcdeemABcddemABccdemAB后缀规范前缀 若其中Abc是句柄，根据定义有mABc是可归规范前缀。2021/7/238 定理 设1A2为可归前缀，AVN，Au为一产生式，则1u也为可归前缀。例:GZ:ZabAd Ac 若abAd是可归前缀，根据此定理abc也是可归前缀。即：1A2 1u22021/7/239例:G S :SaAc 1 AAbb 2 Ab 3 求：该文法的可归前缀图1
4、23203cabbAb1可归前缀图2021/7/23101bcAa3bbA2S:A:子自动机生成过程：2021/7/231112,34203cabbAb11bcAa3bA2b341202021/7/2312构造可归前缀图方法自动机直观法形式化方法 形式化方法,设BX1X2XnP是产生式P，则称形如X1X2XiXi+1XnP的侯选式为LR(0)项目(简称项目)。(圆点可在X1之前,也可在Xn之后)。2021/7/2313 定义F称形如X1X2XnP的项目为归约项目。移进项目:除归约项目外的其它形式。F 设I为项目集,则定义Close(I)=I.uP|AuPG,A1Close(I)称Close(I
5、)为I的闭包集。F 设I为项目集,则GO(I,X)=CLOSE(IX)其中IX=X.P|.XPI2021/7/2314构造构造LR(0)项目集规范族项目集规范族LR(0)项目集规范族项目集规范族(构成识别一个文法的活前缀的构成识别一个文法的活前缀的DFA的状态的全体的状态的全体)。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 S
6、aAd.2021/7/2315例子：UXYZ，求项目 UXYZ UXYZ UXYZ UXYZ 移进项目归约项目2021/7/2316 可归前缀图的构造算法1.先产生初始项目集I1=Close(.P|ZPG,Z为初始符)。2.若I是新项目集,则对每X(VNVT),产生项目集GO(I,X)。若两项目集完全相同,则作为一项目集。3.重复2至不产生新项目集为止。4.图的结点由上述项目集组成,且若GO(Ii,X)=Ij,则有Ii Ij。x2021/7/2317例:G(S):SaAc 1 AbB2|ba3 BdB4|e 5 0:S.aAc 1a1:a.Ac1 .bB2 .ba3A2:aA.c11:a.Ac
7、1 .bB2 .ba3caAc.1b1:a.Ac1 .bB2 .ba32021/7/23183: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:d.B4.dB4 .e5e4:d.B4.dB4 .e5d4:d.B4.dB4 .e52021/7/2319 定义 二义性结点：可归前缀图的一个结点包含多个归约项目或同时包含移进项目和归约项目。Aa.SBD.移进、归约冲突AaS.BD.
8、归约、归约冲突例：2021/7/2320 LR(0)文法：文法的可归前缀图不包含二义性结点(可用于判是否LR(0)文法)。LR分析法的分析栈由两个栈组成：状态栈、符号栈。例子：AaBc Ba Bab2021/7/2321LR分析法的步骤：格局为(0 1i,#X0X1Xi,ajaj+1an#)状态栈 符号栈 输入流 1.若ACTIONi,aj=sk,则有(0 1K,#X0X1Xi,ajaj+1an#)。2.若ACTIONi,aj=rp,则先把符号栈归约Ap(P产生式的左部),从状态栈删除 np(为侯选式的长度)个状态(后端),再压入=Gotoi-np,Ap有(0i-np,#X0XiAp,ajaj
9、+1an#)。2021/7/2322 3.若ACTIONi,aj=ok,则成功。4.若ACTIONi,aj=en,则失败。分析法的动作:Sjs表示“移进”,j表压入编号rjr表示“归约”,j表产生式号 ok表示分析成功eje表示错误,j表错误编号 2021/7/2323例：G(E):EaA|bB AcA|d BcB|d1.用形式化方法作可归前缀图。2.求LR(0)矩阵。3.写出输入串bccd的LR(0)分析过程。2021/7/2324 解：可归前缀图 G(S):SE 0 EaA1 EbB2 AcA3 Ad 4 BcB5 Bd 6 解：拓展文法的新文法如下：2021/7/23250:S.E E.
10、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.aA2021/7/23263:Eb.B B.d B.cBB7:EbB.3:Eb.B B.d B.cBd11:Bd.3:Eb.B B.d B.cBc5:Bc.B B.cB B.d3:Eb.B B.d
11、 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表示归约2021/7/2327r4r4r4r4r4r4r4r4r4r41010r6r6r6r6r6r6r6r6r6r61111r5r5r5r5r5r5r5r5r5r59 9r3r3r3r3r3r3r3r3r3r38 8r2r2r2r2r2r2r2r2r2r27 7r1r1r1r1r1r1r1r1r1r16 69 9S11S11S5S55 58 8S10S10S4S44 47 7S11S11S5S53 36 6S10S10S4S42 2AccAc
12、c1 11 1S3S3S2S20 0B BA AE E#d dc cb ba aGotoGotoActionAction状态状态2021/7/2328 LR(0)分析过程的关键点：1.用分析栈的栈顶元素对输入串的第一个元素查矩阵，以确定下一步的动作。2.每一步都要保持分析栈和符号栈长度一致。3.归约时，符号栈的元素（产生式的右部）弹出栈时，等长的分析栈元素同时弹出栈，以保持两栈长度一致。4.归约时，产生式的左部压进符号栈时，分析栈压进分析栈栈顶元素对产生式左边查goto矩阵得到的状态编号。例如：第5步：用Bd归约,d，(11)出栈，B进栈；5对B查表得9。2021/7/2329S11d#bcc
13、03554S5cd#bc0353S5ccd#b032S3bccd#01GOTO Action 输入串 符号栈 状态栈 步骤 r6#bccd0355(11)59r6#bccB03555r5#bccB0355969r5#bcB0356 解：串bccd的LR(0)分析过程2021/7/2330acc#E0191r2#bB03787r5#bcB035979r5#bccB0355969r6#bccd0355(11)5S11d#bcc03554S5cd#bc0353S5ccd#b032S3bccd#01GOTO Action 输入串 符号栈 状态栈 步骤 2021/7/2331分析器模型分析器模型总控程序
14、outputInput#S1 XmS1X1S0#栈状态文法符号ACTION GOTOLR分析表产生式表2021/7/2332例例 GS为为:S a A c B e A b A Ab B d 1)构造识别活前缀的构造识别活前缀的DFA 2)构造它的构造它的LR(0)分析表。分析表。3)分别给出对输入分别给出对输入符号串符号串abbcdeabbcde和和 AbbceAbbce的的LR(0)分析步骤。分析步骤。2021/7/2333GS拓广拓广为为: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
15、 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 SaAbbcBedGL=abbcde2021/7/2334GS的的LR(0)分析表分析表ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r12021/7/2335Step states.Syms.The rest of inputactio
16、n 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#的分析过程的分析过程2021/7/2336Step states.Syms.The rest of inputaction goto 1 0#abbce#s2 2 02#a b
17、bce#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 文法文法 GSGS的的句子句子 对输入串对输入串abbce#的分析过程的分析过程2021/7/2337 当有I=xb Ar时，为移进-归约冲突，如果FOLLOW(A)b=；或当有I=Ar B时，为归约-归约冲突，如果FOLLOW(A)FOLLOW(B)=,则称该冲突可以解决。7.3 SLR（1）分析2021/7/2338SLR(1)方法:是只在LR(0)
18、可归前缀图的二义性状态下向前看一符。当有I=xb Ar B FOLLOW(A)FOLLOW(B)=,FOLLOW(A)b=；FOLLOW(B)b=则称该冲突可以解决。满足上述条件则可利用SLR(1)方法2021/7/2339例：有项目集 SAa.bBc Ad.Be.设：FOLLOW(A)=a，FOLLOW(B)c所以：FOLLOW(A)FOLLOW(B)=,FOLLOW(A)b=；FOLLOW(B)b=所以本文法是SLR(1)文法。2021/7/2340现举实型变量说明文法为例：real，ii将该文法缩写后并拓广为G如下：1.SS 0 2.SrD 1 3.DD,i 2 4.Di 3 得图如下：
19、2021/7/23410:S.S S.rDS1:SS.r2:Sr.D D.D,i D.iD3:SrD.DD.,ii4:Di.,5:DD,.ii6:DD,i.冲突2021/7/2342实数说明文法的LR(0)分析表如下：r2r2r2r26S65r3r3r3r34r1r1r1,S5r133S42Acc11S20DS#i,rGotoAction状态2021/7/2343解释冲突：SrDDD,i为归约项为移进项follow(S)=follow(S)=#follow(S),=#,=满足上述条件则可利用SLR(1)方法。转化情况如下：2021/7/2344实数说明文法的SLR(1)分析表如下：r2r2r2
20、r26S65r3r3r3r34r1S533S42Acc11S20DS#i,rGotoAction状态2021/7/2345 LR（1）项目）项目(配置）的一般形式配置）的一般形式 A .，a 意味着处在栈顶是 的相应状态，期望相应的相应状态，期望相应 在栈顶的状态，然后只有当跟在跟在 后的token是终结符a时进行归约时进行归约。a 称作该项目项目(配置）配置）的向前搜索符（lookahead）向前搜索符（lookahead）只对圆点在最后的项目起作用A ,a.意味着处在栈中是 的相应状态，但的相应状态，但只有当下一个输入符是a时才能进行归约时才能进行归约.a 要么是一个终结符，要么是输入结束
21、标记#有多个向前搜索符，比如a,b,c时，可写作 A u,a/b/c7.4 LR（1）分析2021/7/2346 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的闭包。2021/7/2347F GO(I,X)=Close(IX)其中IX=X.p,b|.Xp,bI2021/7/2348例子：若文法GS为：SS0 SBB1 BaB2 Bb3则其转换图和分析表如下：2021/7/2349I0:SS,#I0:SS,#SBB,#BaB,
22、a|b Bb,a|b求初始项目集：求初始项目集的闭包集：2021/7/2350I0: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|bBB2021/7/2351I6:BaB,#BaB,#Bb,#I5:SBB,#I7:Bb,#I2:SBB,#BaB,#Bb#I9:BaB,#BBbbaa2021/7/2352r 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
23、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 状态状态 2021/7/2353LR(1)比比SLR（1）能力强）能力强例例 设有文法设有文法GS(0)SS(1)SL=RL=R(2)SR(2)SR(3)L(3)L*R R(4)Lid(4)Lid(5)RL(5)RL该文法不能用该文法不能用SLR（1）技术解决，但能用）技术解决，但能用LR（1）2021/7/2354I1:SS,#I5:Li,=/#I7:L*R,=/#I8:RL,=/#I9:SL=R,#I3:SR,#I
24、12: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*iiRLLRL*例 LR(1)项目集及转换函数2021/7/2355 每个每个SLR（1）文法都是）文法都是LR（1）的，一个）的，一个SLR（1）文法的规范）文法的规范LR分析器比其分析器比其SLR（1）分）分析器的状态要多。析器的状态要多。例子：若文法例
25、子：若文法GSGS为：为：SS0SS0 SBB1 SBB1 BaB2 BaB2 Bb3 Bb3（注：与前例文法同）（注：与前例文法同）LALR1LALR1方法：方法：2021/7/2356同心项目集合：同心项目集合：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.2021/7/2357I0: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
26、 aB,a/b B b,a/b I4:B b,a/bI7:B b,#I9:B aB,#I8:B aB,a/bsBBabbbBBaaaLR(1)项目集和转换函数b2021/7/2358 LALR在在SLR（1）和）和LR（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,#2021/7/2359构造构造 LALR(1)分析
27、表分析表.方法方法11.构造文法G的规范 LR(1)状态.2.合并同心集（除搜索符外两个集合是相同的）的状态.3.新 LALR(1)状态的GO函数是合并的同心集状态的GO函数的并.4.LALR(1)分析表的action 和 goto 登录方法与LR(1)分析表一样.经上述步骤构造的表若不存在冲突，则称它为G的LALR(1)分析表。存在这种分析表的文法称为LALR（1）文法。2021/7/2360LR(0)、SLR(1)、LR(1)、LALR(1)方法比较方法比较实际上不同实际上不同LR方法之间的主要区别就在于归约的判方法之间的主要区别就在于归约的判定方法上：定方法上：LR(0)是不看展望符判定
28、归约；是不看展望符判定归约；SLR(1)是看展望符，但把所有是看展望符，但把所有B 的展望符集均的展望符集均定义为定义为Follow(B)。即把符号栈顶上的句柄。即把符号栈顶上的句柄 归约为归约为B的条件是：展望符为的条件是：展望符为Follow(B)中的元素。换句话中的元素。换句话说，归约任何位置上的说，归约任何位置上的B，都用统一的展望符集；，都用统一的展望符集；LR(1)也是看展望符，但归约不同位置上的也是看展望符，但归约不同位置上的B时，时，采用不同的展望符集。每个项由心与向前搜索符组采用不同的展望符集。每个项由心与向前搜索符组成，搜索符长度为成，搜索符长度为1 1。由于。由于LR(1
29、)方法对于归约条件方法对于归约条件的判定比的判定比SLR(1)更精确，可大大减少移入更精确，可大大减少移入/归约冲归约冲突；突；LALR(1):LALR(1):对对LR(1)LR(1)项目集规范族合并同心集项目集规范族合并同心集2021/7/2361LR(0)LR(0)、SLR(1)SLR(1)、LR(1)LR(1)、LALR(1)LALR(1)分析表比较分析表比较LR(0)LR(0)分析表局限性大，但其构造方法是其他分析表局限性大，但其构造方法是其他构造方法的基础；构造方法的基础；SLRSLR分析表虽然不是对所有文法都存在，但这分析表虽然不是对所有文法都存在，但这种分析表较易实现又极有使用价值；种分析表较易实现又极有使用价值；LRLR分析表的分析能力最强，能适用于一大类分析表的分析能力最强，能适用于一大类文法，但是，实现代价过高（表过大）；文法，但是，实现代价过高（表过大）；LALRLALR分析表的能力介于分析表的能力介于SLRSLR和和LRLR之间，实现效之间，实现效率较高。率较高。2021/7/2362总结：语法分析自顶向下递归子程序法LL(1)方法自底向上简单优先方法算符优先法LR方法LR(0)SLR(1)LR(1)LALR(1)问题解答问题解答?
