第五章 LR(0)方法

1、l5.1 自底向上的語法分析方法概述自底向上的語法分析方法概述l5.2 LR(0)分析的有限自動機分析的有限自動機l5.3 LR(0) 分析分析l5.4 SLR(1) 分析分析l5.5 LR(1) 分析分析l5.6 LALR(1) 分析分析l5.7 LALR(1) 語法分析器的自動生成器語法分析器的自動生成器 (YACC)l自底向上的分析過程自底向上的分析過程lLR分析機制分析機制lLR分析的關(guān)鍵問題分析的關(guān)鍵問題 P:(1) Z ABb(2) A a (3) A b(4) B b(5) B c(6) B bBa b c b輸入輸入符號棧符號棧動作動作abcbabcb移入移入a abcbbcb

2、歸約歸約(2)(2)A Abcbbcb移入移入AbAbcbcb移入移入AbAbc cb b歸約歸約(5)(5)AbAbB Bb b歸約歸約(6)(6)ABABb b移入移入歸約歸約(1)(1)ABbABbZ Z成功成功自底向上分析過程是從所給自底向上分析過程是從所給輸入串輸入串出發(fā)，對其進行出發(fā)，對其進行最左歸約最左歸約的過程。的過程。分析棧分析棧輸入輸入#aLR驅(qū)動程序驅(qū)動程序: - shift(移入移入) :移入型規(guī)范活前綴移入型規(guī)范活前綴 - reduce(歸約歸約):可歸約規(guī)范活前綴可歸約規(guī)范活前綴 LR分析表分析表規(guī)范活規(guī)范活前綴前綴l如何判定規(guī)范活前綴如何判定規(guī)范活前綴?l如何判定

3、移入型規(guī)范活前綴如何判定移入型規(guī)范活前綴?l如何判定歸約規(guī)范活前綴以及用哪一如何判定歸約規(guī)范活前綴以及用哪一個產(chǎn)生式歸約個產(chǎn)生式歸約?l如何判定分析結(jié)束如何判定分析結(jié)束?LR(k)自動機可以解決這些問題自動機可以解決這些問題!l構(gòu)造構(gòu)造LR(0)自動機的依據(jù)自動機的依據(jù) - 派生定理派生定理 l應用派生定理的例子應用派生定理的例子lLR(0)自動機自動機 LR(0) item (項項)LR(0) automatal構(gòu)造構(gòu)造LR(0)自動機的過程自動機的過程l派生定理派生定理: 給出了對任意一個給出了對任意一個CFG構(gòu)造歸約構(gòu)造歸約規(guī)范活前綴的方法規(guī)范活前綴的方法11* * 把把CFGCFG擴展

4、為增廣文法擴展為增廣文法 , Z , Z S S; ;2 2 文法開始符文法開始符Z Z或或S S是歸約規(guī)范活前綴是歸約規(guī)范活前綴; ;3 3 如果如果 A A 是一個是一個歸約規(guī)范活前綴歸約規(guī)范活前綴, , 且有產(chǎn)生且有產(chǎn)生式式A A, ,那么那么, , 也是一個也是一個歸約規(guī)范活前綴歸約規(guī)范活前綴; ; ( ( , , 和和 是由終極符和非終極符構(gòu)成的符號串是由終極符和非終極符構(gòu)成的符號串, ,也可以是空串也可以是空串) )4 4 任何一個歸約規(guī)范活前綴都是按照任何一個歸約規(guī)范活前綴都是按照33方式方式派生出來的派生出來的; ;(證明略)l1 Sl2 S和和S aAc產(chǎn)生產(chǎn)生aAcl3 a

5、Ac和和A Abb產(chǎn)生產(chǎn)生aAbbl4 aAc和和A b產(chǎn)生產(chǎn)生abl5 aAbb和和A Abb產(chǎn)生產(chǎn)生aAbbl6 aAbb和和A b產(chǎn)生產(chǎn)生abl7最后最后,合起來得到合起來得到 S, aAc, aAbb, abVT = a, b, cVN = S, AS = SP: S aAc A Abb A bl1 Sl2 S和S aAc產(chǎn)生aAcl3 aAc和A ABb產(chǎn)生aABbl4 aAc和A a產(chǎn)生aal5 aABb和B bB產(chǎn)生aAbBl6 aABb和B b產(chǎn)生aAbl7 aAbB和B bB產(chǎn)生aAbbBl8 aAbB和B b產(chǎn)生aAbblVT = a, b, cVN = S, A, BS

6、= SP: S aAc A ABb A a B bB B blLR(0) 項目項目:帶圓點的產(chǎn)生式帶圓點的產(chǎn)生式,圓點只能出現(xiàn)圓點只能出現(xiàn)在產(chǎn)生式的右部符號串的任意位置在產(chǎn)生式的右部符號串的任意位置;產(chǎn)生式產(chǎn)生式SaAc，LR(0)項目：項目：lS aAclS a AclS a A clS a Ac 特別地，空產(chǎn)生式特別地，空產(chǎn)生式: S , 對應對應LR(0)項目項目S lLR(0)項目集合項目集合IS關(guān)于符合關(guān)于符合X的投影的投影IS 是一個是一個LR(0)項目的集合項目的集合;X 是一個符號是一個符號(終極符或非終極符終極符或非終極符);IS(X)表示項目集表示項目集IS關(guān)于符號關(guān)于符號

7、X的投影的投影:IS(X) = S X | S X IS, X VT VNIS(x)只對只對IS中圓點后面是中圓點后面是X的項目起作用，所起的項目起作用，所起的作用就是將圓點從的作用就是將圓點從X的前面移到的前面移到X的后面的后面lIS = A A Bb, B a , B b B , Z cBlX = BlIS(B) = A AB b, B bB lLR(0)項目集合的閉包項目集合的閉包IS 是 LR(0)項目的集合;CLOSURE(IS)也是一個LR(0)項目集合, 按照下面的步驟計算:l1 初始, CLOSURE(IS) = ISl2 對于CLOSURE(IS)中沒有處理的LR(0)項目,

8、l 如果該項目的圓點后面是一個非終極符A, l 而且A的全部產(chǎn)生式是A1, , Anl 則增加如下LR(0)項目到CLOSURE(IS)l A 1, , A nl 3 重復2直到 CLOSURE(IS)收斂;VT = a, b, cVN = S, A, BS = SP: S aAc A ABb A Ba B bIS = S aAcCLOSURE(IS) = S aAcIS = S aAcCLOSURE(IS) = S aAc, A ABb, A Ba, B b lgoto函數(shù)IS 是 LR(0)項目集合;X 是一個符號(VT or VN終極符或非終極符);goto(IS, X) = CLOSU

9、RE(IS(x) lCFG G=VT, VN, S, P 的LR(0)自動機l(，SS，S0，TS， ) 是否需要是否需要 增廣產(chǎn)生式增廣產(chǎn)生式 Z S ？ = VT VN#S0 = CLOSURE(Z S) SSTS 構(gòu)造構(gòu)造 LR(0)自動機的過程中逐步生成的。自動機的過程中逐步生成的。1增廣產(chǎn)生式增廣產(chǎn)生式 Z S2 = VT VN #3S0 = CLOSURE(Z S)4SS = S05對于對于SS中的每一個項目中的每一個項目IS, 和每個符號和每個符號X , 計算計算IS = goto(IS, X), 如果如果IS不為空不為空, 則則 建立建立 IS IS, 如果如果IS不為空且不為

10、空且IS不屬于不屬于SS,則把則把IS加入加入SS;6重復重復5直到直到SS收斂收斂;7終止狀態(tài)終止狀態(tài):包含形如包含形如A 項目的項目集合項目的項目集合;XVT = a, b, cVN = S, A, BS = SP: S aAc A ABb A Ba B b Z SS aAc Z S Sa S a AcA ABb A BaB b A S aA c A A BbB b bB A B aa A Ba B b S aAc cB A AB bb A ABb b0*VT = a, b, cVN = S, A, BS = SP: S aAc A ABb A Ba B Z SS aAc Z S Sa S

11、 a AcA ABb A BaB A S aA c A A BbB B A B bb A Bb S aAc cB A AB b A ABb b0*l1 Sl2 S和S aAc產(chǎn)生aAcl3 aAc和A Abb產(chǎn)生aAbbl4 aAc和A b產(chǎn)生abl5 aAbb和A Abb產(chǎn)生aAbbl6 aAbb和A b產(chǎn)生abl7最后,合起來得到 S, aAc, aAbb, abVT = a, b, cVN = S, AS = SP: S aAc A Abb A bVT = a, b, cVN = S, AS = SP: S aAc A Abb A b Z S S aAcS Z S a S a Ac A

12、Abb A bA S aA cA A A bbbbb A b c S aAc b A Ab b b b A Abb LR(0)自動機接受的語言恰好是歸約規(guī)范活前綴的集合：S,aAc,aAbb,abVT = a, b, cVN = S, A, BS = SP: S aAc A ABb A a B bB B bl1 Sl2 S和S aAc產(chǎn)生aAcl3 aAc和A ABb產(chǎn)生aABbl4 aAc和A a產(chǎn)生aal5 aABb和B bB產(chǎn)生aAbBl6 aABb和B b產(chǎn)生aAbl7 aAbB和B bB產(chǎn)生aAbbBl8 aAbB和B b產(chǎn)生aAbblVT = a, b, cVN = S, A, B

13、S = SP: S aAc A ABb A a B bB B b Z S S aAcS Z S a S a Ac A ABb A aA S aA cA A BbB bBB ba A a c S aAc bB b BB b B bBB bB B bB B A AB b b b A ABb bl結(jié)論結(jié)論:一個一個CFG的的LR(0)自動機接受的是該自動機接受的是該CFG的所有的所有LR0歸約規(guī)范活前綴歸約規(guī)范活前綴;l5.1 自底向上的語法分析方法概述自底向上的語法分析方法概述l5.2 LR(0)分析的有限自動機分析的有限自動機l5.3 LR(0) 分析分析l5.4 SLR(1) 分析分析l5.5

14、 LR(1) 分析分析l5.6 LALR(1) 分析分析l5.7 LALR(1) 語法分析器的自動生成器語法分析器的自動生成器 (YACC)l派生定理派生定理lLR(0)項目項目lLR(0)項目集的閉包項目集的閉包lLR(0)項目集關(guān)于符號項目集關(guān)于符號X的投影的投影l(fā)LR(0)自動機的構(gòu)造過程自動機的構(gòu)造過程lLR(0) 自動機的相關(guān)概念自動機的相關(guān)概念lLR(0) 文法文法lLR(0) 語法分析方法語法分析方法LR(0) 分析表分析表LR(0) 分析的驅(qū)動程序分析的驅(qū)動程序lLR(0) 分析過程分析過程l移入項目移入項目: A a , a VTl歸約項目歸約項目: A ,l接受項目接受項目

15、: Z S , (Z S是增廣產(chǎn)生式是增廣產(chǎn)生式)l移入狀態(tài)移入狀態(tài):包含移入項目的狀態(tài)包含移入項目的狀態(tài)l歸約狀態(tài)歸約狀態(tài):包含歸約項目的狀態(tài)包含歸約項目的狀態(tài)l沖突狀態(tài)沖突狀態(tài)(同一個狀態(tài)中同一個狀態(tài)中):包含不同的歸約項目，則稱該狀態(tài)存在包含不同的歸約項目，則稱該狀態(tài)存在歸約歸約-歸約沖突歸約沖突 ；既包含移入項目，又包含歸約項目，則稱該狀態(tài)存在既包含移入項目，又包含歸約項目，則稱該狀態(tài)存在移移入入-歸約沖突歸約沖突l給定一個上下文無關(guān)文法給定一個上下文無關(guān)文法 GlLR0 是是G的的LR(0)自動機自動機l如果如果LR0的任意一個狀態(tài)都不存在沖突的任意一個狀態(tài)都不存在沖突(歸歸約約-歸

16、約沖突、移入歸約沖突、移入-歸約沖突歸約沖突), 則則G稱為稱為LR(0)文法文法;l可以推知：在可以推知：在LR(0)文法中，文法中，任意狀態(tài)或者是移入狀態(tài)任意狀態(tài)或者是移入狀態(tài),或者是歸約狀態(tài)或者是歸約狀態(tài)如果是歸約狀態(tài)如果是歸約狀態(tài),一定存在一個一定存在一個唯一唯一的歸約項的歸約項目目,該歸約項目對應一個產(chǎn)生式該歸約項目對應一個產(chǎn)生式p,因此因此, 該歸約該歸約狀態(tài)稱為狀態(tài)稱為p-歸約狀態(tài)歸約狀態(tài)StackInput#aLR驅(qū)動程序驅(qū)動程序: - shift(移入移入) : 移入型規(guī)范活前綴移入型規(guī)范活前綴 - reduce(歸約歸約): 歸約規(guī)范活前綴歸約規(guī)范活前綴 LR分析表分析表規(guī)

17、范活規(guī)范活前綴前綴狀態(tài)棧狀態(tài)棧action表表goto表表LR(0)驅(qū)動程序驅(qū)動程序VT = a, b, cVN = S, A, BS = SP: (1) S aAc (2)A ABb (3)A Ba (4)B b Z SS aAc Z S Sa S a AcA ABb A BaB b A S aA c A A BbB b bB A B aa A Ba B b S aAc cB A AB bb A ABb b0123567894P: (0) Z S (1) S aAc (2)A ABb (3)A Ba (4)B ba b a c符號棧輸入流分析動作 abac#移入abac#移入abac#歸約

18、(4)aBac#移入aBac#歸約(3)aAc#移入aAc#歸約(1)S#歸約(0)Z#接受狀態(tài)狀態(tài)棧棧符號符號棧棧輸入輸入流流分析動作分析動作0abac# 移入移入02abac#移入移入027abac#歸約歸約 (4)025aBac#移入移入0256aBac#歸約歸約(3)023aAc#移入移入0234aAc#歸約歸約(1)01S#歸約歸約(0)01Z#接受接受P: (0) Z S (1) S aAc (2)A ABb (3)A Ba (4)B ba b a claction表表lgoto表表laction表 終極符終極符狀狀 態(tài)態(tài) a1#S1Sn action(Si,a) = Sj, 如果

19、Si到Sj有a輸出邊 action(Si,c) = Rp, 如果Si是p-歸約狀態(tài),cVt # action(Si,#) = accept, 如果Si是接受狀態(tài) action(Si,a) = error, 其他情形lgoto表 非終極符非終極符狀狀 態(tài)態(tài) A1S1Sngoto (Si, A) = Sj, 如果Si到Sj有A輸出邊 goto (Si, A) = error,如果Si沒有A輸出邊VT = a, b, cVN = S, A, BS = SP: (1) S aAc (2)A ABb (3)A Ba (4)B b Z SS aAc Z S Sa S a AcA ABb A BaB b A S aA c A A BbB b bB A B aa A Ba B b S aAc cB A AB bb A AB