編譯原理534-規(guī)范LR分析表的構(gòu)造ppt課件

1、5.3.4 規(guī)范規(guī)范LR分析表的構(gòu)造分析表的構(gòu)造經(jīng)過例子引入經(jīng)過例子引入LR(k)LR(k)工程工程1.LR(k)1.LR(k)工程定義工程定義2.2.有效有效LR(1)LR(1)工程工程3.3.構(gòu)造構(gòu)造LR(1)LR(1)工程集規(guī)范族工程集規(guī)范族4.4.構(gòu)造構(gòu)造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:移進(jìn)移進(jìn)-歸歸約沖突約沖突例例: :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= 為前綴的規(guī)范句型為前綴的規(guī)范句型, , 因此不能用因此不能用 R RL L 對(duì)于棧頂?shù)膶?duì)于棧頂?shù)腖 L進(jìn)展歸約進(jìn)展歸約 (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)方法處理方法處理 補(bǔ)充例補(bǔ)充例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一切能夠的規(guī)范推導(dǎo)序列一切能夠的規(guī)范推導(dǎo)序列: :S= S = aAd = aedS= S = aAd = aedS= S = bA

4、c = becS= S = bAc = becS= S = aecS= S = aecS= S = bedS= S = bedI5I5識(shí)別活前綴識(shí)別活前綴ae,ae,不存在規(guī)范句型不存在規(guī)范句型aAc,aAc,當(dāng)面臨輸入符號(hào)為當(dāng)面臨輸入符號(hào)為c c時(shí)應(yīng)移進(jìn)時(shí)應(yīng)移進(jìn)面臨面臨d d時(shí)運(yùn)用產(chǎn)生式時(shí)運(yùn)用產(chǎn)生式AeAe歸約歸約 I7I7識(shí)別活前綴識(shí)別活前綴be,be,不存在規(guī)范句型不存在規(guī)范句型bAd,bAd,當(dāng)面臨輸入符號(hào)為當(dāng)面臨輸入符號(hào)為d d時(shí)應(yīng)移進(jìn)時(shí)應(yīng)移進(jìn)面臨面臨c c時(shí)運(yùn)用產(chǎn)生式時(shí)運(yùn)用產(chǎn)生式AeAe歸約歸約 結(jié)論結(jié)論: : 并不是并不是FOLLOW(A)FOLLOW(A)的每個(gè)元素的每個(gè)元素,

5、 ,在含在含A A的一切句型中的一切句型中, ,在在A A的后面都會(huì)出現(xiàn)的后面都會(huì)出現(xiàn) 小結(jié)小結(jié): 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)方法中方法中,假設(shè)工程集假設(shè)工程集IkIk含有含有 A , A ,那么在形狀那么在形狀k k時(shí)時(shí),

6、 ,只需所面臨的輸入符號(hào)只需所面臨的輸入符號(hào)aFOLLOW(A)aFOLLOW(A)，就用，就用AA歸約歸約 棧里的符號(hào)串所構(gòu)成的活前綴棧里的符號(hào)串所構(gòu)成的活前綴未必允許把未必允許把歸約為歸約為A A，由，由于能夠沒有一個(gè)規(guī)范句型含有前綴于能夠沒有一個(gè)規(guī)范句型含有前綴AaAa。因此，在這種情況下，。因此，在這種情況下，用用AA進(jìn)展歸約未必有效。進(jìn)展歸約未必有效。 1.LR(K) 1.LR(K)工程定義工程定義重新定義工程重新定義工程: A: A，a1a2aka1a2akAA是一個(gè)是一個(gè)LR(0)LR(0)工程工程, , 稱為心稱為心, ,a1a2ak a1a2ak 稱為它的向前搜索符串稱為它的

7、向前搜索符串( (展望展望串串), ), aiai是終結(jié)符是終結(jié)符, ,這樣的一個(gè)工程稱為一個(gè)這樣的一個(gè)工程稱為一個(gè)LR(k)LR(k)工程。工程。向前搜索符串僅對(duì)歸約工程向前搜索符串僅對(duì)歸約工程AA，a1a2aka1a2ak有意義有意義. .對(duì)于任何移進(jìn)或待約工程不對(duì)于任何移進(jìn)或待約工程不起作用。起作用。假設(shè)存在規(guī)范推導(dǎo)假設(shè)存在規(guī)范推導(dǎo)那么工程那么工程 A A 對(duì)活前綴對(duì)活前綴 是有效的。是有效的。假設(shè)假設(shè)a aFirst(First() )， 假設(shè)假設(shè)= = 那么那么 a=# a=#那么那么LR(1)LR(1)工程工程AA , a, a對(duì)于活前綴對(duì)于活前綴 是有是有效的。效的。注注: 1)

8、: 1)假設(shè)假設(shè)a aFirst(First(),),即使即使a aFollow(A),Follow(A),工程工程AA , a, a也是無效的。也是無效的。 2) 2)規(guī)范規(guī)范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 對(duì)活前綴對(duì)活前綴 = aaa是有效的是有效的*RR A SRS *R BaBBaaBBaB, # 對(duì)活前綴對(duì)活前綴 = Baa是有效的

9、是有效的3.3.構(gòu)造構(gòu)造LR(1)LR(1)工程集規(guī)范族工程集規(guī)范族一、工程集一、工程集I I的閉包的閉包CLOSURE(I) CLOSURE(I) (1)I(1)I的任何工程都屬于的任何工程都屬于CLOSURE(I) CLOSURE(I) (2)(2)假設(shè)工程假設(shè)工程ABAB，aa屬于屬于CLOSURE(I) CLOSURE(I) 假設(shè)假設(shè)B,bB,b原來原來不在不在CLOSURE(I)CLOSURE(I)中，中， 那么把那么把它加進(jìn)去。它加進(jìn)去。 BB是一個(gè)產(chǎn)生式是一個(gè)產(chǎn)生式, bFIRST(a) , bFIRST(a) (3)(3)反復(fù)執(zhí)行步驟反復(fù)執(zhí)行步驟(2),(2),直到直到CLOS

10、URE(I)CLOSURE(I)不再增大不再增大為止為止二、二、GOGO函數(shù)函數(shù)令令I(lǐng) I是一個(gè)工程集，是一個(gè)工程集，X X是一個(gè)文法符號(hào)，是一個(gè)文法符號(hào)，GO(I,X) = CLOSURE(J)GO(I,X) = CLOSURE(J)，其中，其中J= J= 任何形如任何形如AAX X,a,a的工程的工程 | | AAX X,a,aI I 注：在執(zhí)行轉(zhuǎn)換函數(shù)注：在執(zhí)行轉(zhuǎn)換函數(shù)GOGO時(shí)，搜索符并不改動(dòng)。時(shí)，搜索符并不改動(dòng)。三、構(gòu)造三、構(gòu)造GG的的LR(1)LR(1)工程集族工程集族C C的算法的算法 BEGIN C:= CLOSURE( SS, # ) ; REPEAT FOR C中的每個(gè)工程

11、集中的每個(gè)工程集I和和G的每個(gè)文法符號(hào)的每個(gè)文法符號(hào)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 構(gòu)造構(gòu)造LR(1)LR(1)工程集規(guī)范族工程集規(guī)范族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函數(shù)函數(shù) p116 p116更正教材更正教材(0)S S (1)S BB(2)B aB (3)B

13、 b I1：S S , #4.4.構(gòu)造構(gòu)造LR(1)LR(1)分析表分析表(1)(1)假設(shè)工程假設(shè)工程Aa,bAa,bIk Ik 且且GO(Ik,a)=Ij GO(Ik,a)=Ij ， 置置 ACTIONk,a ACTIONk,a為為 sj sj。(2)(2)假設(shè)工程假設(shè)工程A ,aA ,aIk Ik ，j j是產(chǎn)生式是產(chǎn)生式AA的的編號(hào)編號(hào) 置置 ACTIONk,a ACTIONk,a為為rj rj ，(3)(3)假設(shè)工程假設(shè)工程SS SS ，#IkIk， 置置 ACTIONk,# ACTIONk,#為為 acc acc。(4) (4) 假設(shè)假設(shè)GO(Ik,A)=IjGO(Ik,A)=Ij，

14、置置 GOTOk,A=j GOTOk,A=j。(5)(5)分析表中凡不能用規(guī)那么分析表中凡不能用規(guī)那么(1)(1)(4)(4)填入的空白格均填入的空白格均置為置為“出錯(cuò)標(biāo)志。出錯(cuò)標(biāo)志。表表5.5 5.5 例例5.13 5.13 的的 LR LR分析表分析表 p116 p116狀狀 態(tài)態(tài)ACTIONGOTOab#SB0s3s4121acc2s6s753s3S484r3r35r16s6s797r38r2r29r25.LR(1)5.LR(1)文法文法假設(shè)文法假設(shè)文法G按構(gòu)造按構(gòu)造LR(1)分析表算法構(gòu)造出來分析表算法構(gòu)造出來的分析表不包含多重定義項(xiàng)，那么該文法的分析表不包含多重定義項(xiàng)，那么該文法G是

15、是LR(1)文法。文法。注注: 1每個(gè)每個(gè)SLR(1)文法都是文法都是LR(1)文法，文法， 反之不一定成立；反之不一定成立；2一個(gè)文法的規(guī)范一個(gè)文法的規(guī)范LR分析表比其分析表比其SLR分析表含有更多的形狀。在嚴(yán)重的情況下，分析表含有更多的形狀。在嚴(yán)重的情況下，形狀數(shù)能夠成倍增長。因此需求簡化。形狀數(shù)能夠成倍增長。因此需求簡化。 文法文法5.9 p113(0)S S (1)S L=R(2)S R (3)L *R(4)L i (5)R L例例求求LR(1)工程集規(guī)范族工程集規(guī)范族S S, #SL=R, #SR, #L*R, =/#L i, =/#RL, #I0初態(tài)初態(tài)簡化為簡化為S S,#SL=

16、R,#SR, #L*R, =L i, =RL, #L*R, #L i, #I0初態(tài)初態(tài)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初態(tài)