编译原理534-规范LR分析表的构造ppt课件

1、5.3.4 规范规范LR分析表的构造分析表的构造经过例子引入经过例子引入LR(k)LR(k)工程工程1.LR(k)1.LR(k)工程定义工程定义2.2.有效有效LR(1)LR(1)工程工程3.3.构造构造LR(1)LR(1)工程集规范族工程集规范族4.4.构造构造LR(1)LR(1)分析表分析表5.LR(1)5.LR(1)文法文法 文法文法5.9 p113(0)S S (1)S L=R(2)S R (3)L *R(4)L i (5)R LI2:移进移进-归归约冲突约冲突例例: :I0: SS S L=R S R L *R L i R LI6: SL=R R L L *R L iI2: SL=R

2、 R L I4:L*R R L L *R L iI1: SSI3:SRI7:L*RI8:RLI5:Li I9:SL=R = R * R L i R S * i iL*LFOLOW(R) = # , =文法不含有以文法不含有以 R= R= 为前缀的规范句型为前缀的规范句型, , 因此不能用因此不能用 R RL L 对于栈顶的对于栈顶的L L进展归约进展归约 (0) S S(1) S aAd(2) S bAc(3) S aec(4) S bed(5) A eI0: SS S aAd S bAc S aec S bedI1: SSSI2: S aAd S aec A eI3: S bAc S bed

3、 A eabAeI4: S aAd I5:S aec A eAeI6: S bAc I7:S bed A edI8: S aAdcI9: S aeccI10: S bAcdI11: S bedFOLLOW(A)=c,d I5,I7I5,I7中中冲突不能冲突不能用用SLR(1)SLR(1)方法处理方法处理 补充例补充例1(0) S S(1) S aAd(2) S bAc(3) S aec(4) S bed(5) A eI5:S aec A eI7:S bed A e一切能够的规范推导序列一切能够的规范推导序列: :S= S = aAd = aedS= S = aAd = aedS= S = bA

4、c = becS= S = bAc = becS= S = aecS= S = aecS= S = bedS= S = bedI5I5识别活前缀识别活前缀ae,ae,不存在规范句型不存在规范句型aAc,aAc,当面临输入符号为当面临输入符号为c c时应移进时应移进面临面临d d时运用产生式时运用产生式AeAe归约归约 I7I7识别活前缀识别活前缀be,be,不存在规范句型不存在规范句型bAd,bAd,当面临输入符号为当面临输入符号为d d时应移进时应移进面临面临c c时运用产生式时运用产生式AeAe归约归约 结论结论: : 并不是并不是FOLLOW(A)FOLLOW(A)的每个元素的每个元素,

5、 ,在含在含A A的一切句型中的一切句型中, ,在在A A的后面都会出现的后面都会出现 小结小结: SLR(1)分析法中的无效归约分析法中的无效归约I2: SL =R R L (0)S S (1)S L=R(2)S R (3)L *R(4)L i (5)R LFOLLOW(R) = # , =(0) S S(1) S aAd(2) S bAc(3) S aec(4) S bed(5) A eI5:S aec A eI7:S bed A eFOLLOW(A) = c,d 在在SLR(1)SLR(1)方法中方法中,假设工程集假设工程集IkIk含有含有 A , A ,那么在形状那么在形状k k时时,

6、 ,只需所面临的输入符号只需所面临的输入符号aFOLLOW(A)aFOLLOW(A)，就用，就用AA归约归约 栈里的符号串所构成的活前缀栈里的符号串所构成的活前缀未必允许把未必允许把归约为归约为A A，由，由于能够没有一个规范句型含有前缀于能够没有一个规范句型含有前缀AaAa。因此，在这种情况下，。因此，在这种情况下，用用AA进展归约未必有效。进展归约未必有效。 1.LR(K) 1.LR(K)工程定义工程定义重新定义工程重新定义工程: A: A，a1a2aka1a2akAA是一个是一个LR(0)LR(0)工程工程, , 称为心称为心, ,a1a2ak a1a2ak 称为它的向前搜索符串称为它的

7、向前搜索符串( (展望展望串串), ), aiai是终结符是终结符, ,这样的一个工程称为一个这样的一个工程称为一个LR(k)LR(k)工程。工程。向前搜索符串仅对归约工程向前搜索符串仅对归约工程AA，a1a2aka1a2ak有意义有意义. .对于任何移进或待约工程不对于任何移进或待约工程不起作用。起作用。假设存在规范推导假设存在规范推导那么工程那么工程 A A 对活前缀对活前缀 是有效的。是有效的。假设假设a aFirst(First() )， 假设假设= = 那么那么 a=# a=#那么那么LR(1)LR(1)工程工程AA , a, a对于活前缀对于活前缀 是有是有效的。效的。注注: 1)

8、: 1)假设假设a aFirst(First(),),即使即使a aFollow(A),Follow(A),工程工程AA , a, a也是无效的。也是无效的。 2) 2)规范规范LRLR分析法仅思索有效的分析法仅思索有效的LR(1)LR(1)工程。工程。2.2.有效有效LR(1)LR(1)工程工程*RR A S例例5.12 : S BBB aB | bS RBBRBaB RBabRaBab RaaBabRaaaBabRS *RaaBabaaaBabBaB, a 对活前缀对活前缀 = aaa是有效的是有效的*RR A SRS *R BaBBaaBBaB, # 对活前缀对活前缀 = Baa是有效的

9、是有效的3.3.构造构造LR(1)LR(1)工程集规范族工程集规范族一、工程集一、工程集I I的闭包的闭包CLOSURE(I) CLOSURE(I) (1)I(1)I的任何工程都属于的任何工程都属于CLOSURE(I) CLOSURE(I) (2)(2)假设工程假设工程ABAB，aa属于属于CLOSURE(I) CLOSURE(I) 假设假设B,bB,b原来原来不在不在CLOSURE(I)CLOSURE(I)中，中， 那么把那么把它加进去。它加进去。 BB是一个产生式是一个产生式, bFIRST(a) , bFIRST(a) (3)(3)反复执行步骤反复执行步骤(2),(2),直到直到CLOS

10、URE(I)CLOSURE(I)不再增大不再增大为止为止二、二、GOGO函数函数令令I I是一个工程集，是一个工程集，X X是一个文法符号，是一个文法符号，GO(I,X) = CLOSURE(J)GO(I,X) = CLOSURE(J)，其中，其中J= J= 任何形如任何形如AAX X,a,a的工程的工程 | | AAX X,a,aI I 注：在执行转换函数注：在执行转换函数GOGO时，搜索符并不改动。时，搜索符并不改动。三、构造三、构造GG的的LR(1)LR(1)工程集族工程集族C C的算法的算法 BEGIN C:= CLOSURE( SS, # ) ; REPEAT FOR C中的每个工程

11、集中的每个工程集I和和G的每个文法符号的每个文法符号X IF GO(I, X)非空非空 且不属于且不属于 C THEN 把把GO(I, X)参与参与C中；中； UNTILL C不再增大；不再增大； END例例5.13 5.13 思索如下拓广文法思索如下拓广文法 p115 p115 (0)S(0)S S S (1)S (1)S BB BB(2)B (2)B aB aB (3)B (3)B b b 构造构造LR(1)LR(1)工程集规范族工程集规范族I0 : CLOSURE(SI0 : CLOSURE(SS,#) S,#) SS S, # S, #S S BB, # BB, #B B aB, a/

12、b aB, a/bB B b, a/b b, a/b S I0：S S, # S BB, # B aB, a/b B b, a/bB I2：S BB, # B aB, # B b, # I4：B b, a/bb I3：B aB, a/b B aB, a/b B b, a/bbb I7：B b, # I8：B aB, a/baB I5：S BB, # I6：B aB, # B aB, # B b, #Baa I9：B aB, #baB图图5.10 LR(1)5.10 LR(1)工程集和工程集和GOGO函数函数 p116 p116更正教材更正教材(0)S S (1)S BB(2)B aB (3)B

13、 b I1：S S , #4.4.构造构造LR(1)LR(1)分析表分析表(1)(1)假设工程假设工程Aa,bAa,bIk Ik 且且GO(Ik,a)=Ij GO(Ik,a)=Ij ， 置置 ACTIONk,a ACTIONk,a为为 sj sj。(2)(2)假设工程假设工程A ,aA ,aIk Ik ，j j是产生式是产生式AA的的编号编号 置置 ACTIONk,a ACTIONk,a为为rj rj ，(3)(3)假设工程假设工程SS SS ，#IkIk， 置置 ACTIONk,# ACTIONk,#为为 acc acc。(4) (4) 假设假设GO(Ik,A)=IjGO(Ik,A)=Ij，

14、置置 GOTOk,A=j GOTOk,A=j。(5)(5)分析表中凡不能用规那么分析表中凡不能用规那么(1)(1)(4)(4)填入的空白格均填入的空白格均置为置为“出错标志。出错标志。表表5.5 5.5 例例5.13 5.13 的的 LR LR分析表分析表 p116 p116状状 态态ACTIONGOTOab#SB0s3s4121acc2s6s753s3S484r3r35r16s6s797r38r2r29r25.LR(1)5.LR(1)文法文法假设文法假设文法G按构造按构造LR(1)分析表算法构造出来分析表算法构造出来的分析表不包含多重定义项，那么该文法的分析表不包含多重定义项，那么该文法G是

15、是LR(1)文法。文法。注注: 1每个每个SLR(1)文法都是文法都是LR(1)文法，文法， 反之不一定成立；反之不一定成立；2一个文法的规范一个文法的规范LR分析表比其分析表比其SLR分析表含有更多的形状。在严重的情况下，分析表含有更多的形状。在严重的情况下，形状数能够成倍增长。因此需求简化。形状数能够成倍增长。因此需求简化。 文法文法5.9 p113(0)S S (1)S L=R(2)S R (3)L *R(4)L i (5)R L例例求求LR(1)工程集规范族工程集规范族S S, #SL=R, #SR, #L*R, =/#L i, =/#RL, #I0初态初态简化为简化为S S,#SL=

16、R,#SR, #L*R, =L i, =RL, #L*R, #L i, #I0初态初态I1: Go(I0 , S) S S , #I2: Go(I0 , L) SL =R, # RL , #I3: Go(I0 , R) SR , #I4: Go(I0 , *) L* R, =/# R L, =/# L *R, =/# L i, =/#I5: Go(I0 , i) L i , =/#I6: Go(I2 , =) SL= R, # R L, # L *R, # L i, #I7: Go(I4 , R) L* R , =/#I8: Go(I4 , L) R L , =/# Go(I4 , *) 同同 I4 Go(I4 , i) 同同 I5 I9: Go(I6 , R) SL=R, #I10: Go(I6 , L) R L , #I11: Go(I6 , *) L* R, # R L, # L *R, # L i, #I12: Go(I6 , i) L i , #I13: Go(I11 , R) L* R , # Go(I11 , L) 同同 I10 Go(I11 , *) 同同 I11 Go(I11 , i) 同同 I12 S S, #SL=R, #SR, #L*R, =/#L i, =/#RL, #I0初态