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

2、于產(chǎn)生沖突的原因在于在確定分析動(dòng)作時(shí)沒有考慮輸入串信息。LR(0)自動(dòng)機(jī)的移入-歸約沖突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中存在移入-歸約沖突：移入項(xiàng)目:(2) 歸約項(xiàng)目:A aA LR(0)自動(dòng)機(jī)的歸約-歸約沖突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、突:歸約項(xiàng)目:(2) 歸約項(xiàng)目:A a B aB a4S B cB5S Bcc如何消除沖突？向前看一個(gè)輸入符號(hào)來選擇分析動(dòng)作：假設(shè)下一個(gè)輸入符號(hào)是: a移入-歸約沖突(S-R沖突)移入: 如存在移入項(xiàng)目 A a歸約: 如果存在歸約項(xiàng)目 B , 且 a follow(B)歸約-歸約沖突(R-R沖突)歸約(P1): 如果存在歸約項(xiàng)目 A , afollow(A), 產(chǎn)生式P1= A 歸約(P2): 如果存在歸約項(xiàng)目 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) 分析的思想向前看一個(gè)輸入符號(hào);用非終極符的follow集合解決沖突;如果能將LR(0)自動(dòng)機(jī)中的所有沖突消除掉，則該文法稱為SLR(1)文法，否則稱為非SLR(1)文法。SL

6、R(1)文法文法G的SLR(1)自動(dòng)機(jī)與它的LR(0)自動(dòng)機(jī)完全相同SLR(1)分析表中Action表與LR(0)分析表的Action表稍有不同(移入動(dòng)作沒有區(qū)別，歸約動(dòng)作有區(qū)別)SLR(1)驅(qū)動(dòng)程序與LR(0)驅(qū)動(dòng)程序也相同非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)文法條件的文法仍有限；原因在于：對于同一個(gè)非終極符可能出現(xiàn)在不同的位置，不同位置的后繼符號(hào)(follow)是不同的，統(tǒng)一看待，仍有可能引起沖突。P: (1) S L = R (2) S R (3) L aR (4) L b (5) R LS=LRLRa解決的辦法LR(1) 分析基本思想:對于非終極符的每個(gè)不同出現(xiàn)求其后繼終極符(follow), 稱為展望符;一個(gè)非終極符的一個(gè)出現(xiàn)的所有后繼終極符構(gòu)成的集合稱為展望符集;分析步驟:構(gòu)造 LR(1) 自動(dòng)機(jī)LR(1) 項(xiàng)目 = LR(0)項(xiàng)目+展望符集生成 LR(1)分析表 (action & goto)LR(1

8、)驅(qū)動(dòng)程序 = LR(0)驅(qū)動(dòng)程序LR(1) 自動(dòng)機(jī)LR(1) 項(xiàng)目兩個(gè)部分 : (A , a, ) (1) LR(0) 項(xiàng)目: A (2) 展望符集: a, ，表示非終極符A此次出現(xiàn)的所有可能follow符號(hào)。例如：S L=R , #A , a, b展望符集的作用: 對于移入型項(xiàng)目, 不起作用,但是需要保存;對于歸約型項(xiàng)目, 表示只有當(dāng)下一個(gè)輸入符是其中一個(gè)展望符時(shí), 才可以進(jìn)行歸約動(dòng)作LR(1) 自動(dòng)機(jī)LR(1) 項(xiàng)目集合關(guān)于符號(hào)X的投影IS 是 LR(1) 項(xiàng)目的集合;X 是一個(gè)符號(hào);IS(X) 表示項(xiàng)目集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) 自動(dòng)機(jī)LR(1)項(xiàng)目集合的閉包IS 是LR(1)項(xiàng)目的集合;CLOSURE(IS)是一個(gè)LR(1)項(xiàng)目集合, 按照下面的步驟計(jì)算:1初始, CLOSURE(IS) = IS;2 對于CLOSURE(IS)沒有處理的LR(1)項(xiàng)目, 如果其形式為 (B A, ss) , 而且A的全部產(chǎn)生式是A1, , An 則增加如下LR(1)項(xiàng)目到CLOSURE(IS) (A 1, ss), , (A n,

10、ss), 其中 ss = first(), 如果符號(hào)串不導(dǎo)出空; ss = (first()-) ss, 如果符號(hào)串導(dǎo)出空; 3 重復(fù)2直到 CLOSURE(IS)收斂;LR(1)自動(dòng)機(jī)goto函數(shù)()IS 是 LR(1) 項(xiàng)目集;X 是一個(gè)符號(hào);goto(IS, X) = CLOSURE(IS (X) ) LR(1)自動(dòng)機(jī)的構(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如何計(jì)算展望符集?投影得到的項(xiàng)目繼承閉包新產(chǎn)生的項(xiàng)目擴(kuò)展S X, ssXS X, ssS A, ss.A 1,

12、ss.A n, ssss = first(), 如果不導(dǎo)出空;ss = (first()-) ss, 如果導(dǎo)出空;LR(1)自動(dòng)機(jī)的構(gòu)造過程1增廣產(chǎn)生式 Z S2 = VT VN #3S0 = CLOSURE(S S, #)4ISS = S05對于ISS中的每一個(gè)項(xiàng)目集合IS, 和每個(gè)符號(hào)X , 計(jì)算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)項(xiàng)目, (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) 文法給定一個(gè)上下文無關(guān)文法 GLR1 是文法G的 LR(1) 自動(dòng)機(jī)A1 是G的action表如果對于任意一個(gè)狀態(tài)s和任意的一個(gè)終極符a, A1(s,a)只有一個(gè)唯一的動(dòng)作, 則文法G稱為LR(1)文法;ShiftReduceAcceptError LR(1) 分析方法輸入#a狀態(tài)棧action表goto表LR(1)驅(qū)動(dòng)程序LR(1) 分析驅(qū)動(dòng)程序初始化: 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;如