編譯程序原理與實現(xiàn)：第5章 SLR(1)-LR(1)方法

1、第五章 自底向上的語法分析5.1 自底向上的語法分析方法概述5.2 LR(0)分析的有限自動機5.3 LR(0) 分析5.4 SLR(1) 分析5.5 LR(1) 分析5.6 LALR(1) 分析5.7 LALR(1) 語法分析器的自動生成器 (YACC)5.5 LR(1) 分析LR(0) 分析的局限LR(1) 自動機LR(1) 分析表LR(1) 文法LR(1) 分析過程LR(0)分析的局限LR(0)文法僅憑符號棧里的內(nèi)容來確定可歸約活前綴, 非常容易產(chǎn)生沖突;事實上,只有有限的文法能滿足LR(0)文法的條件;LR(0)分析不是一種實用的方法，只是為介紹LR分析的思想而引進的；LR(0)文法易

2、于產(chǎn)生沖突的原因在于在確定分析動作時沒有考慮輸入串信息。LR(0)自動機的移入-歸約沖突VT = a, bVN = S, AS = SP: (1) S Ab (2) A (3) A a0 Z SS AbA aA 1Z S S2S A bA3S Abba4A a 狀態(tài)0中存在移入-歸約沖突：移入項目:(2) 歸約項目:A aA LR(0)自動機的歸約-歸約沖突VT = a, b, cVN = S, A, BS = SP: (1) S Ab (2) S Bc (3) A a (4) B a0Z SS AbS BcA a1Z S S2S A bA3S Abba6A a B a 狀態(tài)6存在歸約-歸約沖

3、突:歸約項目:(2) 歸約項目:A a B aB a4S B cB5S Bcc如何消除沖突？向前看一個輸入符號來選擇分析動作：假設(shè)下一個輸入符號是: a移入-歸約沖突(S-R沖突)移入: 如存在移入項目 A a歸約: 如果存在歸約項目 B , 且 a follow(B)歸約-歸約沖突(R-R沖突)歸約(P1): 如果存在歸約項目 A , afollow(A), 產(chǎn)生式P1= A 歸約(P2): 如果存在歸約項目 B , afollow(B), 產(chǎn)生式P2= BLR(0)分析表 (帶有S-R 沖突)Action 表Goto 表ab#SA0S5;R2R2R2131Accept2S33R1R1R14

4、R3R3R3VT = a, bVN = S, AS = SP: (1) S Ab (2) A (3) A aLR(0)分析表 (沒有沖突)Action 表Goto 表ab#SA0S5R2131Accept2S33R14R3VT = a, bVN = S, AS = SP: (1) S Ab (2) A (3) A a沖突用follow(A)解決掉了LR(0)分析表 (帶有R-R 沖突) VT = a, b, cVN = S, A, BS = SP: (1) S Ab (2) S Bc (3) A a (4) B aAction 表Goto 表abc#SAB0S71351Accept2S43R1

5、R1R1R14S65R2R2R2R26R3R4R3R4R3R4R3R4LR(0)分析表(沒有R-R沖突)VT = a, b, cVN = S, A, BS = SP: (1) S Ab (2) S Bc (3) A a (4) B aAction 表Goto 表abc#SAB0S71351Accept2S43R14S65R26R3R4沖突用 follow(A) 和 follow(B)消除了;SLR(1) 分析SLR(1) 分析的思想向前看一個輸入符號;用非終極符的follow集合解決沖突;如果能將LR(0)自動機中的所有沖突消除掉，則該文法稱為SLR(1)文法，否則稱為非SLR(1)文法。SL

6、R(1)文法文法G的SLR(1)自動機與它的LR(0)自動機完全相同SLR(1)分析表中Action表與LR(0)分析表的Action表稍有不同(移入動作沒有區(qū)別，歸約動作有區(qū)別)SLR(1)驅(qū)動程序與LR(0)驅(qū)動程序也相同非SLR(1)文法的例子VT = a, b, =VN = S, L, RS = SP: (1) S L = R (2) S R (3) L aR (4) L b (5) R L0Z SS L = RS RL2S L=R R LL aRL bR L1Z S Sfollow(R) = #, =SLR(1)分析的局限性SLR(1)分析存在的問題通過引入follow集，解決了一部

7、分文法的沖突問題，但滿足SLR(1)文法條件的文法仍有限；原因在于：對于同一個非終極符可能出現(xiàn)在不同的位置，不同位置的后繼符號(follow)是不同的，統(tǒng)一看待，仍有可能引起沖突。P: (1) S L = R (2) S R (3) L aR (4) L b (5) R LS=LRLRa解決的辦法LR(1) 分析基本思想:對于非終極符的每個不同出現(xiàn)求其后繼終極符(follow), 稱為展望符;一個非終極符的一個出現(xiàn)的所有后繼終極符構(gòu)成的集合稱為展望符集;分析步驟:構(gòu)造 LR(1) 自動機LR(1) 項目 = LR(0)項目+展望符集生成 LR(1)分析表 (action & goto)LR(1

8、)驅(qū)動程序 = LR(0)驅(qū)動程序LR(1) 自動機LR(1) 項目兩個部分 : (A , a, ) (1) LR(0) 項目: A (2) 展望符集: a, ，表示非終極符A此次出現(xiàn)的所有可能follow符號。例如：S L=R , #A , a, b展望符集的作用: 對于移入型項目, 不起作用,但是需要保存;對于歸約型項目, 表示只有當(dāng)下一個輸入符是其中一個展望符時, 才可以進行歸約動作LR(1) 自動機LR(1) 項目集合關(guān)于符號X的投影IS 是 LR(1) 項目的集合;X 是一個符號;IS(X) 表示項目集IS關(guān)于X的投影:IS(X) = (S X, ss) | (S X, ss) IS

9、, X VT VN投影對展望符集沒有影響！IS = (A ABb, a,b), (B a, #), (B bB, b)X = BIS(B) = (A ABb, a, b), (B bB, b)LR(1) 自動機LR(1)項目集合的閉包IS 是LR(1)項目的集合;CLOSURE(IS)是一個LR(1)項目集合, 按照下面的步驟計算:1初始, CLOSURE(IS) = IS;2 對于CLOSURE(IS)沒有處理的LR(1)項目, 如果其形式為 (B A, ss) , 而且A的全部產(chǎn)生式是A1, , An 則增加如下LR(1)項目到CLOSURE(IS) (A 1, ss), , (A n,

10、ss), 其中 ss = first(), 如果符號串不導(dǎo)出空; ss = (first()-) ss, 如果符號串導(dǎo)出空; 3 重復(fù)2直到 CLOSURE(IS)收斂;LR(1)自動機goto函數(shù)()IS 是 LR(1) 項目集;X 是一個符號;goto(IS, X) = CLOSURE(IS (X) ) LR(1)自動機的構(gòu)造VT = a, b, =VN = S, L, RS = SP: (1) S L = R (2) S R (3) L aR (4) L b (5) R L0Z S , #S L = R, #S R, #R3S R, # L aR, =L b , =R L , #1ZS,

11、#Sb4L b, =, # L5S L=R, # R L, #L aR, #L b , #L aR, =, #L b , =, #=6a126S L=R, # R L , #L aR, #L b , #LR7S L=R, # a9L aR, # R L , #L aR, #L b , #R10L aR, # L8R L, # ab11L b, # b12L aR, =, # R L , =,#L aR, =,#L b , =,#R13L aR, =,# baL14R L, =,# 4如何計算展望符集?投影得到的項目繼承閉包新產(chǎn)生的項目擴展S X, ssXS X, ssS A, ss.A 1,

12、ss.A n, ssss = first(), 如果不導(dǎo)出空;ss = (first()-) ss, 如果導(dǎo)出空;LR(1)自動機的構(gòu)造過程1增廣產(chǎn)生式 Z S2 = VT VN #3S0 = CLOSURE(S S, #)4ISS = S05對于ISS中的每一個項目集合IS, 和每個符號X , 計算IS = goto(IS, X), 如果IS不為空, 則 建立 IS IS, 如果IS不為空且IS不屬于ISS,則把IS加入ISS;6重復(fù)5直到ISS收斂;XLR(1) 分析表action表goto表LR(1) 分析表action表 終極符狀 態(tài) a1#S1Sn(1)action(Si,a) =

13、Sj, 如果Si到Sj有a輸出邊(2)action(Si,a) = Rp, 如果Si中包含這樣LR(1)項目, (A, ss),其中A是產(chǎn)生式P,且ass; (3)action(Si,#) = accept, 如果Si是接受狀態(tài)(4)action(Si,a) = error, 其他情形LR(1) 分析表goto表 非終極符狀 態(tài) A1AnS1Sngoto (Si, A) = Sj, 如果Si到Sj有A輸出邊 goto (Si, A) = error,如果Si沒有A輸出邊 LR(1) 分析表Action 表Goto 表ab=#SLR0S12S41531Accept 3R24R4R45S6R56S

14、9S11877R1 LR(1) 分析表 (接上頁.)Action 表Goto 表ab=#SLR8R59S9S111010R311R412S12S4141313R3R314R4R415LR(1) 文法給定一個上下文無關(guān)文法 GLR1 是文法G的 LR(1) 自動機A1 是G的action表如果對于任意一個狀態(tài)s和任意的一個終極符a, A1(s,a)只有一個唯一的動作, 則文法G稱為LR(1)文法;ShiftReduceAcceptError LR(1) 分析方法輸入#a狀態(tài)棧action表goto表LR(1)驅(qū)動程序LR(1) 分析驅(qū)動程序初始化: push(S0); a = readOne();L: Switch action(stack(top), a) Case error: error();Case accept: return true;Case Si: push(Si), a=readOne(); goto L;Case RP: pop(|P|); push(goto(stack(top), PA ); goto L;如