1、6.4 LR(1)和LALR(1)分析規(guī)范LR分析,例1文法G 0）SS (1) SaAd (2) SbAc (3) Saec (4) Sbed (5) Ae,I0: SS I1: SS I2: SaAd SaAd Saec SbAc Ae Saec Sbed I3: SbAc I4: I5: Sbed SaAd Saec Ae Ae I6: I7: I8: SbAc Sbed SaAd Ae I9: Saec I10: SbAc I11: Sbed,( 0）SS (1) SaAd (2) SbAc (3) Saec (4) Sbed (5) Ae非 LR(0),非SLR(1),I5: S a

2、ec I7: S bed A e A e S=S=aAd=aed S=S=bAc=bec S=S=aec S=S=bed ae是活前綴 be是活前綴 aAc不是規(guī)范句型 , bAd不是規(guī)范句型 不作無效歸約 ？信息 在特定的規(guī)范推導中，哪些輸入符號能跟在句柄之后 GS: 若S = A = r是的前綴，則 稱r是G的一個活前綴. 哪個項目在什么條件下對某個活前綴有效,R,R,R,R,R,R,R,R,R,R,R,R,*,*,*,*,*,例2 GS:(0) SS (1) SL=R (2) SR(3) L *R (4) Lid (5) RL,I0: S S S L = R S R R L L id L

3、 *R I1: S S I2: S L = R R L I3: S R,I4: L *R R L L *R L id I5: L id I6: S L =R R L L *R L id I7: L *R I8: R L I9: S L=R,I2: S L = R R L,考慮分析表達式 id = id時，在工作到 I2 處已經(jīng)把第一個 id 歸約到 L了, 看到下一個輸入 = 要作決策，第一個項目要設置 Action2,= 為S6, 即把賦值的其它部分找到. 但 =也是屬于 Follow(R) 的. 第二個項目要用 RL歸約.出現(xiàn) shift-reduce 沖突. 若將棧頂?shù)姆栃蛄袣w約到 R

4、,會有問題！因為不可能有規(guī)范句型以 R = 開頭 (有以 *R = . 開頭的規(guī)范句型).,SLR（1）的局限,follow 集包含了在任何句型中跟在 R 后的符號但沒有嚴格地指出在一個特定的推導里哪些符號跟在 R后.所以需要擴充狀態(tài)以包含更多的信息：follow 集的哪些部分 才是進到該狀態(tài)最恰當?shù)臍w約依據(jù). 處在狀態(tài) 2時，試圖構建句子有兩條路： 1.S L = R 或 2.S R L. 如下一符號是 =, 那就不能用第二個選擇，必須用第一個,即移進. 只有下一個符號是#時才能歸約. 盡管 = 屬于 Follow(R) ，那是因為一個 R 可以出現(xiàn)在別的上下文中，在現(xiàn)在這個特定的情況，它不

5、合適,因為在用S R L推導句子時, = 不能跟在R后.,.,討論例2后有以下結果： 不是LR(0)文法 I2 SL=R RL.中存在移進/歸約沖突 SLR能否解決I2中的沖突 FOLLOW（R）=#,=與=交不為空 不是SLR（1）文法 如早有信息告知： 若用 RL 歸約 則形成R= 而 R=不是活前綴，,SLR（1）的局限,在SLR 分析中,若項目集Ik含有項目 A .,那么在相應的狀態(tài)下,只要當前輸入符號afollow(A) 集,就確定采用A 進行歸約.但在某些情況下,當狀態(tài)k呈現(xiàn)于棧頂時,棧內的串所構成的活前綴未必允許把歸約為A,.因為可能沒有一個規(guī)范句型含有前綴Aa.即在這種情況下,

6、用A 歸約未必有效. . 所以需要擴充狀態(tài)以包含更多的信息：follow 集的哪些部分 才是進到該狀態(tài)最恰當?shù)臍w約依據(jù). 必須重新定義項目. LR（1）方法的思路: 若 A .B I 則 B . I （ B 是一產(chǎn)生式） 把FIRST（ ）中的符號作為用B 歸約的搜索符，向前搜索符 .,LR（1）項目( 配置）的一般形式 A . ， a a 稱作該項目( 配置） 的向前搜索符（ lookahead ） 向前搜索符（ lookahead ）只對圓點在最后的項目起作用 A , a .意味著處在棧中是 的相應狀態(tài)，但只有當下一個輸入符是a時才能進行歸約. a 是一個終結符，或是輸入結束標記# 有多個

7、向前搜索符，比如a,b,c時，可寫作 A u, a/b/c,LR(0)項目對某個活前綴有效,定義 項目A 1.2對活前綴r=1是有效的,如果存在一個規(guī)范推導S = A =12 若項目A .B對活前綴r=是有效的且B是一個產(chǎn)生式,則項目B.對r=也是有效的. 因為由假定,存在一個規(guī)范推導 S = A = B 設 =,則對B有規(guī)范推導 S = A=B=B = 于是項目B.對r=也是有效的,LR(1)項目對某個活前綴有效,定義 一個LR(1)項目A .,a對活前綴r=是有效的,如果存在一個規(guī)范推導S = A = 其中或的第一個符號為a,或=而a為# 若LR(1)項目A .B,a對活前綴r=是有效的且

8、B是一個產(chǎn)生式,則項目B.,b對r=也是有效的.其中b或者是從推出的第一個終結符,或者= 而b=a,兩者結合在一起,即:b FIRST(a),構造LR(1)項目集規(guī)范族和G0函數(shù),closure(I)按如下方式構造 (1) I的任何項目屬closure(I)； (2)若A1B2，aclosure(I)，B是一產(chǎn)生式，那么對于FIRST(2a)中的每個終結符b，如果B,b不在closure(I)中，則把它加進去； (3)重復（1）（2），直至closure(I)不再增大。 GO函數(shù)： 若I是一個項目集，X是一個文法符號 GO(I, X)= closure(J) 其中 J= 任何形如AX,a的項目

9、A.X,aI LR(I)項目規(guī)范族C的構造算法類同LR(0)的，只是初始時： C= closure(SS,#);,例1的LR(1)項目集規(guī)范族,I0: SS, # I5: S aec,# S aAd, # A e,d S bAc, # I6: S bAc, # S aec, # I7: S bed, # S bed, # A e,c I1: S S,# I8: S aAd, # I2: S aAd, # I9: S aec, # S aec, # I10: S bAc, # A e, d I11: S bed, # I3: S bAc, # S bed, # Ae,c I4: S aAd, #

10、,規(guī)范的LR(1)分析表的構造,假定LR(1)項目集規(guī)范族C=I0, I1,，In，令每個項目集Ik的下標k 為分析器的一個狀態(tài)，G 的LR（1）分析表含有狀態(tài)0，1，n。 1.令那個含有項目SS ，#的Ik的下標k為狀態(tài)0（初態(tài)）.ACTION表和GOTO表可按如下方法構造 2.若項目A,b屬于Ik, 那么置ACTIONk, b為“用產(chǎn)生式A進行規(guī)約”，簡記為“rj”;(假定A為文法G的第j個產(chǎn)生式) 3.若項目Aa,b屬于Ik且GO (Ik, a)= Ij,則置ACTIONk, a為“把狀態(tài)j和符號a移進?！?，簡記為“sj”; 4.若項目SS,#屬于Ik, 則置ACTIONk, #為“接受

11、”，簡記為“acc”; 5.若GO (Ik, A)= Ij, A為非終結符，則置GOTO(k, A)=j; 分析表中凡不能用規(guī)則1至5填入信息的空白格均置上“出錯標志”。 按上述算法構造的含有ACTION和GOTO兩部分的分析表，如果每個入口不含多重定義，則稱它為文法G的一張規(guī)范的LR(1)分析表。具有規(guī)范的LR(1)表的文法G稱為一個LR（1）文法。,LR(1) 文法滿足下面兩個條件 1.如果一個項目集里有項目 A uxv , a ， x是終結符，那就不會有項目B u, x 2.項目集里所有歸約項目 的向前搜索符不相交，即不能同時含有項目 A u, a 和B v , a,LR（K）分析,LR

12、（K）項目 A . ， a1 a2 aK a1 a2 aK 向前搜索符串 移進項目 A . a， a1 a2 aK 待約項目 A . B， a1 a2 aK 歸約項目 A . ， a1 a2 aK ,LR(1)比SLR（1）能力強,例2 (0) SS (1)SL=R (2)SR (3)L *R (4)Lid (5)RL不能用SLR（1）技術解決，但能用LR（1）,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,#

13、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,#,s,R,=,L,R,i,i,*,i,i,R,L,L,R,L,*,*,*,例2的 LR(1)項目集及轉換函數(shù),每個SLR（1）文法都是LR（1）的，一個SLR（1）文法的規(guī)范LR分析器比其SLR（1）分析器的狀態(tài)要多。,例 G(S):S BB BaB B b I0:S.S S .BB B .aB B .b I1:S S

14、. I2:S B.B B.aB B.b I3:Ba.B B.aB B.b I4:BaB. I5: Bb. I6: SBB.,I0:S S,# S BB,# B aB,a/b B b,a/b,I1:S S,#,I2:S BB,# B aB,# B b,#,I5:S BB,#,I6:BaB,# B aB,# B b,#,I3:B aB,a/b B aB,a/b B b,a/b,I4:B b,a/b,I7:B b,#,I9:B aB,#,I8:B aB,a/b,s,B,B,a,b,b,b,B,B,a,a,a,LR(1)項目集規(guī)范族和轉換函數(shù),b,LALR在SLR（1）和LR（1）間尋找折衷辦法（狀態(tài)

15、數(shù)目，分析能力）,LALR (lookahead LR) 合并LR（1）項目集規(guī)范族的同心集I36 I47 I89（除搜索符外兩個集合是相同的）.,I3:B aB,a/b B aB,a/b B b,a/b,I6:B aB,# B aB,# B b,#,I4:B b,a/b,I7:B b,#,I8:B aB,a/b,I9:B aB,#,構造 LALR(1)分析表.方法1-“brute-force”,1.構造文法G的規(guī)范 LR(1) 狀態(tài). 2.合并同心集的狀態(tài). 3.新 LALR(1) 狀態(tài)的GO函數(shù)是合并的同心集狀態(tài)的GO函數(shù)的并. 4. LALR(1)分析表的ACTION 和 GOTO 登錄

16、方法與LR(1)分析表一樣. 經(jīng)上述步驟構造的表若不存在沖突，則稱它為G的LALR(1)分析表。 存在這種分析表的文法稱為LALR（1）文法。,0 S3 S4 1 2 1 acc 2 S6 S7 5 3 S3 S4 8 4 r3 r3 5 r1 6 S6 S7 9 7 r3 8 r2 r2 9 r2,LR(1)分析表,0 S3,6 S4,7 1 2 1 acc 2 S3,6 S4,7 5 3,6 S3,6 S4,7 8,9 4,7 r3 r3 r3 5 r1 8,9 r2 r2 r2,LALR(1)分析表,對 輸入串a(chǎn)b#用LR(1)分析的過程,1 0 # ab# S3 2 03 #a b#

17、S4 3 034 #ab # 出錯,步驟,狀態(tài)棧,符號棧,輸入串,ACTION,GOTO,對輸入串a(chǎn)b#用LALR(1)分析的過程,1 0 # ab# S3,6 2 0(3,6) #a b# S4,7 3 0(3,6)(4,7) #ab # r3 (8,9) 4 0(3,6)(8,9) #aB # r2 2 5 02 #B # 出錯,步驟,狀態(tài)棧,符號棧,輸入串,ACTION,GOTO,討論:,LR（1）項目集不存在動作沖突，合并同心集后會不會產(chǎn)生新的沖突（移進-歸約，歸約-歸約） 不會產(chǎn)生新的移進-歸約沖突（討論見講義） 會產(chǎn)生新的歸約-歸約沖突,LR（1）項目集不存在動作沖突，合并同心集后會不會產(chǎn)生新的沖突（移進-歸約，歸約-歸約）,例 S S S aBc | bCc | aCd | bBd B e C e,LR(1) 項目集規(guī)范族:,I0: S S, # S aBc, # S bCc, # S aCd, # S bBd, # I1: S S, # I2: S aBc, # S aCd, # B e, c C e, d I3: S bCc, # S bBd, # C e, c B e, d I4: S aBc, #,I5: S aCd, # I6: B e, c C e, d I7: S b