精品课程编译原理-第7章LR分析ppt课件

1、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 LR0分析 定义 如果有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为项目集,则定义FClose(I)=I.uP|AuPG,F A1Close(I) F 称Close(I)为I的闭包集。 F 设I为项目集,则GO(I,X)=CLOSE(IX) 其中IX=X.P|.XPI构造构造LR(0)项目集规范族项目集规范族LR(0)项目集规范族项目集规范族(构成识别一个文法的活前缀的构成识别一个文法的活前缀的DFA的

5、状态的全体的状态的全体) 。 LR0项目或配置（项目或配置（ item or configuration）.-在右端某一位置有圆点的在右端某一位置有圆点的G的产生式的产生式 A xyz A.xyz Ax.yz Axy.z Axyz. 如：如：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)。若两项目集完全相同,则作为一项目集。3.重复2至不产生

6、新项目集为止。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:d.B4 .

7、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,a

8、j=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 Ea

9、A1 EbB2 AcA3 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:E

10、b.B B.d B.cBc5: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 7S11S11S

11、5S53 36 6S10S10S4S42 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

12、。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#S

13、1 XmS1X1S0 #栈形状文法符号ACTION GOTOLR分析表产生式表例例 GSGS为为: : S S a A c B e a A c B e A A b b A A AbAb B B d d 1) 1)构造识别活前缀的构造识别活前缀的DFA DFA 2) 2)构造它的构造它的LR(0)LR(0)分析表。分析表。 3)3)分别给出对输入符号串分别给出对输入符号串abbcdeabbcde和和 AbbceAbbce的的LR(0)LR(0)分析步骤。分析步骤。GS拓广为拓广为: S S S a A c B e A b A Ab B dI0 : SI0 : S S S S S a a A c

14、B e A c B e I1 : SI1 : S S S I2 : S I2 : S a a A c B e A c B e A A b b A A Ab AbI3 : S I3 : S a A a A c B e c B e A A A A b bI4 : A I4 : A b b I5 : S I5 : S a A c a A c B e B e B B d dI7 : S I7 : S a A c B a A c B e eI8 : B I8 : B d d I9 : S I9 : S a A c B e a A c B e I6 : A I6 : A A b A b SaAbbcBed

15、GL= abbcdeGS的的LR(0)分析表分析表ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1Step 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# s

16、8 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#不是例不是例

17、6.1 文法文法 GS的句子的句子 对输入串对输入串abbce#的分析过程的分析过程7.3 SLR1分析例：有项目集 SAa.bBc Ad. Be.设：FOLLOW(A)=a，FOLLOW(B)c所以：FOLLOW(A)FOLLOW(B)=, FOLLOW(A)b=； FOLLOW(B)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,

18、i.冲突实数说明文法的LR(0)分析表如下：r2r2r2r26S65r3r3r3r34r1r1r1,S5r133S42Acc11S20DS#i,rGotoAction形状解释冲突：SrDDD,i为归约项为移进项follow(S)=follow(S)=#follow(S),=#,= 满足上述条件则可利用SLR(1)方法。转化情况如下：实数说明文法的SLR(1)分析表如下：r2r2r2r26S65r3r3r3r34r1S533S42Acc11S20DS#i,rGotoAction形状 LR1工程工程( 配置的一般形式配置的一般形式 A . ， a 意味着处在栈顶是意味着处在栈顶是的相应状态，期望相

19、应的相应状态，期望相应在栈顶的状态，在栈顶的状态，然后只有当跟在然后只有当跟在后的后的token是终结符是终结符a时进行归约时进行归约 。 a 称称作该项目作该项目( 配置）配置） 的向前搜索符（的向前搜索符（ lookahead ）向前搜索符（向前搜索符（ lookahead ）只对圆点在最后的项目起作用）只对圆点在最后的项目起作用A , a.意味着处在栈中是意味着处在栈中是 的相应状态，但只有当下一个输入符的相应状态，但只有当下一个输入符是是a时才能进行归约时才能进行归约. a 要么是一个终结符，要么是输入结要么是一个终结符，要么是输入结束标记束标记#有多个向前搜索符，比如有多个向前搜索符

20、，比如a,b,c时，可写作时，可写作 A u, a/b/c7.4 LR1分析 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)F其中IX=X.p,b|.Xp,bI例子：若文法GS为： SS0 SBB1 BaB2 Bb3则其转换图和分析表如下： I0:SS,#I0:SS,# SBB,# BaB,a|b Bb,a|b求初始项目集：求初始项目集的闭包集：I0:SS,# SBB,

21、# 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,#BBbbaar2r2r2r28 8r2r29 9r3r37 79 9S7S7S6S66 6r1r15 5r3r3r3 r3 4 48 8S4S4S3 S3 3 35 5S7S7S6S62 2accacc1 12 21 1S4S4S3 S3 0 0B BS S# #b ba aGOTO GOTO ACTION ACTION 形状形

22、状 LR(1)比比SLR1能力强能力强例例 设有文法设有文法GS (0) SS (1)SL=R(2)SR(3)L *R(4)Lid(5)RL该文法不能用该文法不能用SLR1技术解决，但能用技术解决，但能用LR1）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,# I4: L *R,=/# R L,=/#L i,=/# L *R,=/#I6:S L= R,# R L,# L *R,# L i

23、,# I11:L * R,# R L,# L *R,# L i,# I2:S L =R,# R L,# sR=LRii*iiRLLRL*例 LR(1)项目集及转换函数 每个每个SLR1文法都是文法都是LR1的，一个的，一个SLR1文法的规范文法的规范LR分析器比其分析器比其SLR1分分析器的状态要多。析器的状态要多。例子：若文法例子：若文法GSGS 为：为： S SS0S0 SBB1 SBB1 BaB2 BaB2 Bb3 Bb3（注：与前例文法同）（注：与前例文法同）LALR1LALR1方法：方法：同心项目集合：同心项目集合：I0:S.S S .BB B .aB B .bI1:S S.I2:S

24、 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在在SLR1和和LR1间寻间寻找折衷办法状态数目，分析能力）找折衷办法状态数目

25、，分析能力）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 登录方法与LR(1)分析表一样.经上述步骤构造的表若不存在冲突，则称它为G的LALR(1)分析表。存在这种分析表的文法称为LALR1文法。LR(0)、SLR(1)、LR(1)、LALR(1)方法比较方法比较实际上不同实际上不同LR