第五章 LR(0)方法

1、l5.1 自底向上的語法分析方法概述自底向上的語法分析方法概述l5.2 LR(0)分析的有限自動(dòng)機(jī)分析的有限自動(dòng)機(jī)l5.3 LR(0) 分析分析l5.4 SLR(1) 分析分析l5.5 LR(1) 分析分析l5.6 LALR(1) 分析分析l5.7 LALR(1) 語法分析器的自動(dòng)生成器語法分析器的自動(dòng)生成器 (YACC)l自底向上的分析過程自底向上的分析過程lLR分析機(jī)制分析機(jī)制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輸入輸入符號棧符號棧動(dòng)作動(dòng)作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ā)，對其進(jìn)行出發(fā)，對其進(jìn)行最左歸約最左歸約的過程。的過程。分析棧分析棧輸入輸入#aLR驅(qū)動(dòng)程序驅(qū)動(dòng)程序: - shift(移入移入) :移入型規(guī)范活前綴移入型規(guī)范活前綴 - reduce(歸約歸約):可歸約規(guī)范活前綴可歸約規(guī)范活前綴 LR分析表分析表規(guī)范活規(guī)范活前綴前綴l如何判定規(guī)范活前綴如何判定規(guī)范活前綴?l如何判定

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

4、為增廣文法擴(kuò)展為增廣文法 , Z , Z S S; ;2 2 文法開始符文法開始符Z Z或或S S是歸約規(guī)范活前綴是歸約規(guī)范活前綴; ;3 3 如果如果 A A 是一個(gè)是一個(gè)歸約規(guī)范活前綴歸約規(guī)范活前綴, , 且有產(chǎn)生且有產(chǎn)生式式A A, ,那么那么, , 也是一個(gè)也是一個(gè)歸約規(guī)范活前綴歸約規(guī)范活前綴; ; ( ( , , 和和 是由終極符和非終極符構(gòu)成的符號串是由終極符和非終極符構(gòu)成的符號串, ,也可以是空串也可以是空串) )4 4 任何一個(gè)歸約規(guī)范活前綴都是按照任何一個(gè)歸約規(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) 項(xiàng)目項(xiàng)目:帶圓點(diǎn)的產(chǎn)生式帶圓點(diǎn)的產(chǎn)生式,圓點(diǎn)只能出現(xiàn)圓點(diǎn)只能出現(xiàn)在產(chǎn)生式的右部符號串的任意位置在產(chǎn)生式的右部符號串的任意位置;產(chǎn)生式產(chǎn)生式SaAc，LR(0)項(xiàng)目：項(xiàng)目：lS aAclS a AclS a A clS a Ac 特別地，空產(chǎn)生式特別地，空產(chǎn)生式: S , 對應(yīng)對應(yīng)LR(0)項(xiàng)目項(xiàng)目S lLR(0)項(xiàng)目集合項(xiàng)目集合IS關(guān)于符合關(guān)于符合X的投影的投影IS 是一個(gè)是一個(gè)LR(0)項(xiàng)目的集合項(xiàng)目的集合;X 是一個(gè)符號是一個(gè)符號(終極符或非終極符終極符或非終極符);IS(X)表示項(xiàng)目集表示項(xiàng)目集IS關(guān)于符號關(guān)于符號

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

8、l 如果該項(xiàng)目的圓點(diǎn)后面是一個(gè)非終極符A, l 而且A的全部產(chǎn)生式是A1, , Anl 則增加如下LR(0)項(xiàng)目到CLOSURE(IS)l A 1, , A nl 3 重復(fù)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)項(xiàng)目集合;X 是一個(gè)符號(VT or VN終極符或非終極符);goto(IS, X) = CLOSU

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

10、空且IS不屬于不屬于SS,則把則把IS加入加入SS;6重復(fù)重復(fù)5直到直到SS收斂收斂;7終止?fàn)顟B(tài)終止?fàn)顟B(tài):包含形如包含形如A 項(xiàng)目的項(xiàng)目集合項(xiàng)目的項(xiàng)目集合;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)自動(dòng)機(jī)接受的語言恰好是歸約規(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é)論:一個(gè)一個(gè)CFG的的LR(0)自動(dòng)機(jī)接受的是該自動(dòng)機(jī)接受的是該CFG的所有的所有LR0歸約規(guī)范活前綴歸約規(guī)范活前綴;l5.1 自底向上的語法分析方法概述自底向上的語法分析方法概述l5.2 LR(0)分析的有限自動(dòng)機(jī)分析的有限自動(dòng)機(jī)l5.3 LR(0) 分析分析l5.4 SLR(1) 分析分析l5.5

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

15、: Z S , (Z S是增廣產(chǎn)生式是增廣產(chǎn)生式)l移入狀態(tài)移入狀態(tài):包含移入項(xiàng)目的狀態(tài)包含移入項(xiàng)目的狀態(tài)l歸約狀態(tài)歸約狀態(tài):包含歸約項(xiàng)目的狀態(tài)包含歸約項(xiàng)目的狀態(tài)l沖突狀態(tài)沖突狀態(tài)(同一個(gè)狀態(tài)中同一個(gè)狀態(tài)中):包含不同的歸約項(xiàng)目，則稱該狀態(tài)存在包含不同的歸約項(xiàng)目，則稱該狀態(tài)存在歸約歸約-歸約沖突歸約沖突 ；既包含移入項(xiàng)目，又包含歸約項(xiàng)目，則稱該狀態(tài)存在既包含移入項(xiàng)目，又包含歸約項(xiàng)目，則稱該狀態(tài)存在移移入入-歸約沖突歸約沖突l給定一個(gè)上下文無關(guān)文法給定一個(gè)上下文無關(guān)文法 GlLR0 是是G的的LR(0)自動(dòng)機(jī)自動(dòng)機(jī)l如果如果LR0的任意一個(gè)狀態(tài)都不存在沖突的任意一個(gè)狀態(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),一定存在一個(gè)一定存在一個(gè)唯一唯一的歸約項(xiàng)的歸約項(xiàng)目目,該歸約項(xiàng)目對應(yīng)一個(gè)產(chǎn)生式該歸約項(xiàng)目對應(yīng)一個(gè)產(chǎn)生式p,因此因此, 該歸約該歸約狀態(tài)稱為狀態(tài)稱為p-歸約狀態(tài)歸約狀態(tài)StackInput#aLR驅(qū)動(dòng)程序驅(qū)動(dòng)程序: - shift(移入移入) : 移入型規(guī)范活前綴移入型規(guī)范活前綴 - reduce(歸約歸約): 歸約規(guī)范活前綴歸約規(guī)范活前綴 LR分析表分析表規(guī)

17、范活規(guī)范活前綴前綴狀態(tài)棧狀態(tài)棧action表表goto表表LR(0)驅(qū)動(dòng)程序驅(qū)動(dòng)程序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符號棧輸入流分析動(dòng)作 abac#移入abac#移入abac#歸約

18、(4)aBac#移入aBac#歸約(3)aAc#移入aAc#歸約(1)S#歸約(0)Z#接受狀態(tài)狀態(tài)棧棧符號符號棧棧輸入輸入流流分析動(dòng)作分析動(dòng)作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