LR分析器(SLR-規(guī)范的LR)

1、LRLR分析器（分析器（SLRSLR，規(guī)范的，規(guī)范的LRLR）4.6-4.74.6-4.7SLR4.5 LR分析器分析器 4.5.3 構(gòu)造構(gòu)造SLR分析表分析表v術(shù)語：術(shù)語：LR(0)項(xiàng)目項(xiàng)目（簡稱（簡稱項(xiàng)目項(xiàng)目）在右部的某個地方加點(diǎn)的產(chǎn)生式在右部的某個地方加點(diǎn)的產(chǎn)生式4.5 LR分析器分析器 4.5.3 構(gòu)造構(gòu)造SLR分析表分析表v術(shù)語：術(shù)語：LR(0)項(xiàng)目項(xiàng)目（簡稱（簡稱項(xiàng)目項(xiàng)目）在右部的某個地方加點(diǎn)的產(chǎn)生式在右部的某個地方加點(diǎn)的產(chǎn)生式加點(diǎn)的目的是用來表示分析過程中的狀態(tài)加點(diǎn)的目的是用來表示分析過程中的狀態(tài)4.5 LR分析器分析器 4.5.3 構(gòu)造構(gòu)造SLR分析表分析表v術(shù)語：術(shù)語：LR(

2、0)項(xiàng)目項(xiàng)目（簡稱（簡稱項(xiàng)目項(xiàng)目）在右部的某個地方加點(diǎn)的產(chǎn)生式在右部的某個地方加點(diǎn)的產(chǎn)生式加點(diǎn)的目的是用來表示分析過程中的狀態(tài)加點(diǎn)的目的是用來表示分析過程中的狀態(tài)exprexpr+term 4.5 LR分析器分析器 4.5.3 構(gòu)造構(gòu)造SLR分析表分析表v術(shù)語：術(shù)語：LR(0)項(xiàng)目項(xiàng)目（簡稱（簡稱項(xiàng)目項(xiàng)目）在右部的某個地方加點(diǎn)的產(chǎn)生式在右部的某個地方加點(diǎn)的產(chǎn)生式加點(diǎn)的目的是用來表示分析過程中的狀態(tài)加點(diǎn)的目的是用來表示分析過程中的狀態(tài)exprexpr+term*termfactor 4.5 LR分析器分析器 4.5.3 構(gòu)造構(gòu)造SLR分析表分析表v術(shù)語：術(shù)語：LR(0)項(xiàng)目項(xiàng)目（簡稱（簡稱項(xiàng)目項(xiàng)

3、目）在右部的某個地方加點(diǎn)的產(chǎn)生式在右部的某個地方加點(diǎn)的產(chǎn)生式加點(diǎn)的目的是用來表示分析過程中的狀態(tài)加點(diǎn)的目的是用來表示分析過程中的狀態(tài)exprexpr+term*termfactor 4.5 LR分析器分析器 4.5.3 構(gòu)造構(gòu)造SLR分析表分析表v術(shù)語：術(shù)語：LR(0)項(xiàng)目項(xiàng)目（簡稱（簡稱項(xiàng)目項(xiàng)目）在右部的某個地方加點(diǎn)的產(chǎn)生式在右部的某個地方加點(diǎn)的產(chǎn)生式加點(diǎn)的目的是用來表示分析過程中的狀態(tài)加點(diǎn)的目的是用來表示分析過程中的狀態(tài)v例例 AXYZ對應(yīng)有四個項(xiàng)目對應(yīng)有四個項(xiàng)目A XYZA XYZA XYZA XYZ例例 A 只有一個項(xiàng)目和它對應(yīng)只有一個項(xiàng)目和它對應(yīng)A 4.5 LR分析器分析器 構(gòu)造構(gòu)造

4、SLR分析表的兩大步驟分析表的兩大步驟1、從文法構(gòu)造識別可行前綴的、從文法構(gòu)造識別可行前綴的DFA2、從上述、從上述DFA構(gòu)造分析表構(gòu)造分析表4.5 LR分析器分析器 1、從文法構(gòu)造識別可行前綴的、從文法構(gòu)造識別可行前綴的DFA1）拓廣文法）拓廣文法E E + T | TT T F | F F ( E ) | id 4.5 LR分析器分析器 1、從文法構(gòu)造識別可行前綴的、從文法構(gòu)造識別可行前綴的DFA1）拓廣文法）拓廣文法E E E E + T | TT T F | F F ( E ) | id 4.5 LR分析器分析器 1、從文法構(gòu)造識別可行前綴的、從文法構(gòu)造識別可行前綴的DFA2）構(gòu)造）構(gòu)

5、造LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族I0:E E4.5 LR分析器分析器 1、從文法構(gòu)造識別可行前綴的、從文法構(gòu)造識別可行前綴的DFA2）構(gòu)造）構(gòu)造LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族I0:E EE E + T E T4.5 LR分析器分析器 1、從文法構(gòu)造識別可行前綴的、從文法構(gòu)造識別可行前綴的DFA2）構(gòu)造）構(gòu)造LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族I0:E EE E + T E TT T F T F4.5 LR分析器分析器 1、從文法構(gòu)造識別可行前綴的、從文法構(gòu)造識別可行前綴的DFA2）構(gòu)造）構(gòu)造LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族I0:E EE E + T E TT T FT FF (E)F

6、id4.5 LR分析器分析器 1、從文法構(gòu)造識別可行前綴的、從文法構(gòu)造識別可行前綴的DFA2）構(gòu)造）構(gòu)造LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族I0:E E( (核心項(xiàng)目核心項(xiàng)目) )E E + T E T( (非核心項(xiàng)目，非核心項(xiàng)目，T T F 通過對核心項(xiàng)目求閉包通過對核心項(xiàng)目求閉包T F 而獲得而獲得) )F (E)F id4.5 LR分析器分析器 1、從文法構(gòu)造識別可行前綴的、從文法構(gòu)造識別可行前綴的DFA2）構(gòu)造）構(gòu)造LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族I0: I1:E EE E E E + T E E + T E TT T F T FF (E)F idE4.5 LR分析器分析器 1、從文法

7、構(gòu)造識別可行前綴的、從文法構(gòu)造識別可行前綴的DFA2）構(gòu)造）構(gòu)造LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族I0: I1:E EE E E E + T E E + T E TT T F I1 := goto ( I0, E )T FF (E)F idE4.5 LR分析器分析器 1、從文法構(gòu)造識別可行前綴的、從文法構(gòu)造識別可行前綴的DFA2）構(gòu)造）構(gòu)造LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族I0: I1:E EE E E E + T E E + T E TT T F I2:T FE T F (E)T T F F idET4.5 LR分析器分析器 1、從文法構(gòu)造識別可行前綴的、從文法構(gòu)造識別可行前綴的DFA2）構(gòu)

8、造構(gòu)造LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族I0: I1:E EE E E E + T E E + T E TT T F I2:T FE T F (E)T T F F id I3: T F ETF4.5 LR分析器分析器 I0: I4:E EF (E ) E E + T E TT T FT FF (E)F id(4.5 LR分析器分析器 I0: I4:E EF (E ) E E + T E E + T E TE TT T FT T FT FT FF (E)F (E)F idF id(4.5 LR分析器分析器 I0: I4:E EF (E ) E E + T E E + T E TE TT T FT

9、 T FT FT FF (E)F (E)F idF id I5:F id (id4.5 LR分析器分析器 I1I0EI3I2I4I5TF(id 4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI1:E E E E+ T 4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI1:E E E E+ TI6 :EE + TT T F T F F (E) F id +4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI1: I2:E EET E E+ TTT F I6 :EE + TT T F T F F (E) F id +4.5 LR分析器分析器 I1I0EI3

10、I2I4I5TF(idI1: I2:E EET E E+ TTT F I6 : I7:EE + TTT F T T F F (E) T F F id F (E) F id + 4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI3:T F 無狀態(tài)轉(zhuǎn)換無狀態(tài)轉(zhuǎn)換4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI4:F (E )E E + TE TT T F T FF ( E )F id 4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI4: I8:F (E )F (E) E E + TE E+ T E TT T F T FF ( E )F id E4.5

11、LR分析器分析器 I1I0EI3I2I4I5TF(idI4: I8:F (E )F (E) E E + TE E+ T E TT T F I2:T FETF ( E )TT F F id TE4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI4: I8:F (E )F (E) E E + TE E+ T E TT T F I2:T FETF ( E )TT F F id I3:TF TFE4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI4: I8:F (E )F (E) E E + TE E+ T E TT T F I2:T FETF ( E )TT F F id

12、 I3:TF I4: F (E ) . . .TF(E4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI4: I8:F (E )F (E) E E + TE E+ T E TT T F I2:T FETF ( E )TT F F id I3:TF I4: I5: F (E ) F id . . .TF(idE4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI5:F id 無狀態(tài)轉(zhuǎn)換無狀態(tài)轉(zhuǎn)換4.5 LR分析器分析器 I1I0+EI6I3I2I4I8I7I5指向指向I2指向指向I3T* *F(Eidid(FT4.5 LR分析器分析器 I1I0+指向指向I7EI6I9I

13、3I2I4I11I8I7I10* *TI5指向指向I4指向指向I3指向指向I5指向指向I4指向指向I5指向指向I6指向指向I2指向指向I3F(FTid* *id(F(Eid+)id(FTE E E+T E+T F E+T id E+T F id把所有狀態(tài)都把所有狀態(tài)都作為接受狀態(tài)作為接受狀態(tài)這是一個這是一個DFAE+T F 的所有前綴都可接受的所有前綴都可接受4.5 LR分析器分析器 I0:E EE E + TE TT T FT FF (E)F id 也可以構(gòu)造一個識別可行前綴的也可以構(gòu)造一個識別可行前綴的NFA N例子v1. 給出接受文法S-(L)|a L-L,S|S的活前綴的一個DFA答案

14、-1例子v2. 求接受文法S-Aa|bAc|dc|bdaA-d的活前綴DFA和SLR(1)分析表答案-2（DFA）答案-2（狀態(tài)分析表）4.5 LR分析器分析器 構(gòu)造構(gòu)造SLR分析表的兩大步驟分析表的兩大步驟1、從文法構(gòu)造識別可行前綴的、從文法構(gòu)造識別可行前綴的DFA2、從上述、從上述DFA構(gòu)造構(gòu)造分析表分析表4.5 LR分析器分析器 v例例 SLR(1)文法的描述能力有限文法的描述能力有限S V = ES E V EV id E V I0 : S S S V = ES E V EV id E V I2 : S V = EE V V 第一項(xiàng)目使得第一項(xiàng)目使得action2, = = s6 第二

15、項(xiàng)目使得第二項(xiàng)目使得action2, = 為按為按EV歸約，因?yàn)闅w約，因?yàn)?是是E的一個后繼符的一個后繼符=是是E的一個后繼符：的一個后繼符： S $ V = E $ E = E $4.5 LR分析器分析器 v例例 SLR(1)文法的描述能力有限文法的描述能力有限S V = ES E V EV id E V I0 : S S S V = ES E V EV id E V I2 : S V = EE V V 第一項(xiàng)目使得第一項(xiàng)目使得action2, = = s6 第二項(xiàng)目使得第二項(xiàng)目使得action2, = 為按為按EV歸約，因?yàn)闅w約，因?yàn)?是是E的一個后繼符的一個后繼符在所關(guān)注場合在所關(guān)注場合

16、E的后繼是的后繼是$： S $ V = E $ E = E $S $ E $ V $4.5 LR分析器分析器 4.5.4 構(gòu)造規(guī)范的構(gòu)造規(guī)范的LR分析表分析表LR(1)項(xiàng)目：項(xiàng)目：重新定義項(xiàng)目重新定義項(xiàng)目，讓它帶上搜索符，成為如下形式讓它帶上搜索符，成為如下形式A , aLR(1)項(xiàng)目項(xiàng)目A , a對可行前綴對可行前綴 有效：有效：如果存在著推導(dǎo)如果存在著推導(dǎo)S *rm Aw rm w，其中：其中： = ；a是是w的第一個符號，或者的第一個符號，或者w是是 且且a是是$4.5 LR分析器分析器 v例例 S BBB bB | a從最右推導(dǎo)從最右推導(dǎo)S *rm bbBba rm bbbBba看出：

17、看出： BbB, b對可行前綴對可行前綴 = bbb是有效的是有效的 對于項(xiàng)目對于項(xiàng)目A , a，當(dāng)當(dāng) 為空時，是根據(jù)搜索為空時，是根據(jù)搜索符符a來填表（歸約項(xiàng)目），而不是根據(jù)來填表（歸約項(xiàng)目），而不是根據(jù)A的后繼符來的后繼符來填表填表4.5 LR分析器分析器 S S, $ I0S BB, $B bB, b/aB a, b/a4.5 LR分析器分析器 S S, $ I0S BB, $B bB, b/aB a, b/aS S, $ I1S BB, $B bB, $B a, $ I2SBB bB, b/aB bB, b/aB a, b/a I3B a, b/a I4ab4.5 LR分析器分析器 S

18、 S, $ I0S BB, $B bB, b/aB a, b/aS S, $ I1S BB, $B bB, $B a, $ I2SBB bB, b/aB bB, b/aB a, b/a I3B a, b/a I4aabbS BB, $ I5B bB, $B bB, $B a, $ I6B bB, $ I9B a, $ I7B bB, b/a I8BbbBaaB4.5 LR分析器分析器 構(gòu)造規(guī)范的構(gòu)造規(guī)范的LR分析表分析表(1) 基于基于LR(1)項(xiàng)目來構(gòu)造識別項(xiàng)目來構(gòu)造識別G 可行前綴的可行前綴的DFA(2)從從Ii構(gòu)造分析器的狀態(tài)構(gòu)造分析器的狀態(tài)i, 狀態(tài)狀態(tài)i的的action函數(shù)如下確函數(shù)

19、如下確定定如果如果A a , b在在Ii中，且中，且goto(Ii, a) = Ij ，那那么置么置actioni, a為為sj如果如果A , a在在Ii中，且中，且A S ，那么置那么置actioni, a為為rj 如果如果SS, $在在Ii中，那么置中，那么置actioni, $ = acc如果用上面規(guī)則構(gòu)造出現(xiàn)了沖突，那么文法就不是如果用上面規(guī)則構(gòu)造出現(xiàn)了沖突，那么文法就不是LR(1)的的4.5 LR分析器分析器 v先前基于先前基于SLR(1)有移進(jìn)有移進(jìn)- -歸約沖突的例子，歸約沖突的例子，在基于規(guī)范在基于規(guī)范LR(1)時無沖突時無沖突S V = ES E V EV id E V I0

20、 : S S， $S V = E, $S E, $V E, =/$V id, =/$ E V, $I2 : S V = E, $E V , $V 4.5 LR分析器分析器 4.5.5 構(gòu)造構(gòu)造LALR分析表分析表v研究研究LALR的的原因原因規(guī)范規(guī)范LR分析表的狀態(tài)數(shù)偏多分析表的狀態(tài)數(shù)偏多vLALR特點(diǎn)特點(diǎn)LALR和和SLR的分析表有同樣多的狀態(tài)，比規(guī)范的分析表有同樣多的狀態(tài)，比規(guī)范LR分析表要小得多分析表要小得多LALR的能力介于的能力介于SLR和和規(guī)范規(guī)范LR之間之間LALR的能力在很多情況下已經(jīng)夠用的能力在很多情況下已經(jīng)夠用vLALR分析表構(gòu)造方法分析表構(gòu)造方法通過合并規(guī)范通過合并規(guī)范L

21、R(1)項(xiàng)目集來得到項(xiàng)目集來得到4.5 LR分析器分析器 S S, $ I0S BB, $B bB, b/aB a, b/aS S, $ I1S BB, $B bB, $B a, $ I2SBB bB, b/aB bB, b/aB a, b/a I3B a, b/a I4aabbS BB, $ I5B bB, $B bB, $B a, $ I6B bB, $ I9B a, $ I7B bB, b/a I8BbbBaaBI4和和I7僅搜索符不一樣僅搜索符不一樣4.5 LR分析器分析器 S S, $ I0S BB, $B bB, b/aB a, b/aS S, $ I1S BB, $B bB, $

22、B a, $ I2SBB bB, b/aB bB, b/aB a, b/a I3B a, b/a I4aabbS BB, $ I5B bB, $B bB, $B a, $ I6B bB, $ I9B a, $ I7B bB, b/a I8BbbBaaBI4和和I7合并合并4.5 LR分析器分析器 S S, $ I0S BB, $B bB, b/aB a, b/aS S, $ I1S BB, $B bB, $B a, $ I2SBB bB, b/aB bB, b/aB a, b/a I3B a, b/a I4aabbS BB, $ I5B bB, $B bB, $B a, $ I6B bB, $

23、 I9B a, $ I7B bB, b/a I8BbbBaaB輸入為輸入為bbabba$4.5 LR分析器分析器 S S, $ I0S BB, $B bB, b/aB a, b/aS S, $ I1S BB, $B bB, $B a, $ I2SBB bB, b/aB bB, b/aB a, b/a I3B a, b/a I4aabbS BB, $ I5B bB, $B bB, $B a, $ I6B bB, $ I9B a, $ I7B bB, b/a I8BbbBaaB輸入為輸入為bba$4.5 LR分析器分析器 S S, $ I0S BB, $B bB, b/aB a, b/aS S,

24、$ I1S BB, $B bB, $B a, $ I2SBB bB, b/aB bB, b/aB a, b/a I3B a, b/a I4aabbS BB, $ I5B bB, $B bB, $B a, $ I6B bB, $ I9B a, $ I7B bB, b/a I8BbbBaaB有三組同心集，都合并有三組同心集，都合并4.5 LR分析器分析器 S S, $ I0S BB, $B bB, b/aB a, b/aS S, $ I1S BB, $B bB, $B a, $ I2SBB bB, b/a/$B bB, b/a/$B a, b/a/$ I36B a, b/a/$ I47aabbS

25、BB, $ I5B bB, b/a/$ I89BbBa4.5 LR分析器分析器 S S, $ I0S BB, $B bB, b/aB a, b/aS S, $ I1S BB, $B bB, $B a, $ I2SBB bB, b/a/$B bB, b/a/$B a, b/a/$ I36B a, b/a/$ I47aabbS BB, $ I5B bB, b/a/$ I89BbBa棧棧 輸入輸入0 bba$4.5 LR分析器分析器 S S, $ I0S BB, $B bB, b/aB a, b/aS S, $ I1S BB, $B bB, $B a, $ I2SBB bB, b/a/$B bB, b/a/$B a, b/a/$ I36B a, b/a/$ I47aabbS BB, $ I5B bB, b/a/$ I89BbBa棧棧 輸入輸入0b36 ba$4.5 LR分析器分析器 S S, $ I0S BB, $B bB, b/aB a, b/aS S, $ I1S BB, $B bB, $B a, $ I2SBB bB, b/a/$B bB, b/a/$B a, b/a/$ I3