編譯原理課件第4章語法分析

1、1第四章第四章 語法分析語法分析(3)4.5 自底向上語法分析24.5 自底向上分析自底向上分析q 移進(jìn)歸約分析法(Shift-reduce parsing)q 一般的移進(jìn)歸約法LR parsingLR(0)SLRLR(1)LALRq 自動的語法分析器的生成器（YACC）“L”：left-to-right scanning 自左向右掃描“R”：rightmost derivation in reverse 最右推導(dǎo)的逆34.5.1 歸約歸約例4.21考慮文法S aABe A Abc | bB d句子abbcde的歸約步驟如下：abbcde aAbcdeaAdeaABeS 對應(yīng)最右推導(dǎo)的逆過程：

2、S aABe aAde aAbcde abbcdeSa A B edA b cbrmrmrmrm“最右推導(dǎo)的逆最右推導(dǎo)的逆”是是“最左規(guī)約最左規(guī)約”4句柄句柄(handles)q 右句型的句柄是：產(chǎn)生式產(chǎn)生式A 和和 中的子串中的子串 的位置的位置，且用A 代替得到的仍是右句型 q 句柄的右邊w僅含終結(jié)符。S Aw wAwSrmrm*5ExampleS aABe aAde aAbcde abbcde考慮文法S aABe A Abc | bB dA b 和 b 是是abbcde的句柄。的句柄。 A Abc 和 Abc 是是aAbcde 的句柄的句柄。B d 和 d 是是aAde 的句柄的句柄。

3、S aABe 和 aABe 是是aABe 的句柄的句柄。rmrmrmrmSa A B edA b cb句柄剪枝句柄剪枝6ExampleS aABe aAde aAbcde abbcdeAbc 是是 aAbcde 的句柄。的句柄。rmrmrmrmSa A B edA b c考慮文法S aABe A Abc | bB d7ExampleS aABe aAde aAbcde abbcded 是是 aAde 的句柄。的句柄。rmrmrmrmSa A B ed考慮文法S aABe A Abc | bB d8ExampleS aABe aAde aAbcde abbcdeaABe 是是 aABe 的句柄。

4、的句柄。rmrmrmrmSa A B e考慮文法S aABe A Abc | bB d9例例4.22E E + E | E * E | (E ) | idq 如果文法二義，那么句柄可能不唯一。q 在句型E + E * id3中，句柄不唯一。E rm E + E rm E + E * E rm E + E * id3 rm E + id2 * id3 rm id1 + id2 * id3E rm E * E rm E * id3 rm E + E * id3 rm E + id2 * id3 rm id1 + id2 * id3 注意：畫出圖。104.5.2 句柄剪枝句柄剪枝 (Handle P

5、runing)q 通過“句柄剪枝”可以得到一個(gè)反向的最右推導(dǎo)。q 從被分析的終結(jié)符號串w開始，如果w是文法的句子，那么記w = n，其中n是最右推導(dǎo)的第n步句型：q 構(gòu)造最右推導(dǎo)的逆過程，在n中找句柄進(jìn)行歸約得到右句型n-1。wSnrmrmrmrm21011例例4.23右句型句柄歸約產(chǎn)生式id1 id2 * id3E id2 * id3E E * id3E E * E E EEid1id2id3E * EE + E E id E id E id E E * E E E + EEEE+*EEid1id2id3EEE+*EEid1id2id3最右推導(dǎo)的逆是最左規(guī)約12分析過程的特點(diǎn)分析過程的特點(diǎn)從

6、輸入串的開頭依次讀入(移進(jìn)移進(jìn))單詞。一旦發(fā)現(xiàn)可歸約串可歸約串(在上例中是句柄句柄)就立即歸約歸約。根據(jù)句柄對分析樹進(jìn)行修剪子樹，剪去子樹的葉子。若最終能歸約成文法的開始符號，則分析成功。由于總是將句型的最左邊的可歸約串最左邊的可歸約串替換成非終結(jié)符號，該歸約方法通常得到是最右推導(dǎo)的逆過程最右推導(dǎo)的逆過程。134.5.3 用棧實(shí)現(xiàn)移進(jìn)歸約分析用棧實(shí)現(xiàn)移進(jìn)歸約分析q 必須解決兩個(gè)問題確定右句型中將要?dú)w約的子串（句柄）如何確定選擇哪一個(gè)產(chǎn)生式q 一般方法用棧保存文法符號輸入緩沖區(qū)存放待分析的串移進(jìn)(shift)輸入符號入棧，直至棧頂出現(xiàn)句柄歸約(reduce)句柄，用產(chǎn)生式左部的非終結(jié)符替代棧中的

7、句柄14棧棧 輸輸 入入 動動 作作 $ id1 + id2 * id3$ 移進(jìn)移進(jìn) $id1 + id2 * id3$ 按按E id歸約歸約 $E + id2 * id3$移進(jìn)移進(jìn) $E+ id2 * id3$ 移進(jìn)移進(jìn) $E+ id2 * id3$ 按按E id歸約歸約 $E+E * id3$ 移進(jìn)移進(jìn) $E+E* id3$ 移進(jìn)移進(jìn) $E+E*id3 $按按E id歸約歸約 $E+E*E $按按E E*E歸約歸約 $E+E $按按E E+E歸約歸約 $E $接受接受 例例4.2415q 初始狀態(tài)格局棧輸入$w$q 接受狀態(tài)格局棧輸入$S $16動作動作q 有四種動作移進(jìn)：把下一個(gè)輸入符號

8、移進(jìn)棧頂歸約：在棧中確定句柄，選擇正確的非終結(jié)符替代句柄接受報(bào)錯(cuò)17q 句柄總會出現(xiàn)在棧頂，而不會在棧的里面。q 考察任意最右推導(dǎo)中連續(xù)兩步的可能形式：xyzBxyzBxAzSyzByzAzSrmrmrmrmrmrm*18yzByzAzSrmrmrm*q 假設(shè)當(dāng)前狀態(tài)格局為：棧輸入$yz$q 把句柄歸約為B，達(dá)到狀態(tài)格局：棧輸入$B yz$q 移進(jìn)y入棧中，達(dá)到格局：棧輸入$By z$q 棧頂形成句柄By，歸約為A，達(dá)到狀態(tài)格局：棧輸入$A z$S Az B y 19q 假設(shè)當(dāng)前狀態(tài)格局為：棧輸入$xyz$q 把句柄歸約為B，達(dá)到狀態(tài)格局：棧輸入$B xyz$q 移進(jìn)x, y入棧中，達(dá)到格局：

9、棧輸入$Bxy z$q 棧頂句柄y歸約為A，達(dá)到狀態(tài)格局：棧輸入$BxA z$xyzBxyzBxAzSrmrmrm*S zB x A y結(jié)論：不需要在棧中間去尋找句柄，只要在棧頂就可以得到句柄。不需要在棧中間去尋找句柄，只要在棧頂就可以得到句柄。204.5.5 沖突沖突 (Conflicts)q 如果形成這樣的格局：根據(jù)棧中的內(nèi)容和下一個(gè)輸入符號不能決定是移進(jìn)還是歸約（移進(jìn)移進(jìn) 歸約沖歸約沖突突），或不能決定用那一條產(chǎn)生式進(jìn)行歸約（歸約歸約 歸約沖突歸約沖突）。21移進(jìn)移進(jìn) 歸約沖突歸約沖突例例4.25 stmt if expr then stmt | if expr then stmt el

10、se stmt | other存在移進(jìn)歸約沖突。一般地，任何二義性文法都不是LR(k)文法。假設(shè)當(dāng)前狀態(tài)格局為：棧輸入 if expr then stmtelse $22歸約歸約 歸約沖突歸約沖突例例4.26 關(guān)于過程調(diào)用和數(shù)組引用的下標(biāo)的文法stmt id (parameter_list) | expr := exprparameter_list parameter_list, parameter | parameterparameter idexpr id (expr_list) | idexpr_list expr_list, expr | exprexpr, expr, , exprp

11、aram, param, , param例子：id(id, id)23例例4.26 關(guān)于過程調(diào)用和數(shù)組引用的下關(guān)于過程調(diào)用和數(shù)組引用的下標(biāo)的文法標(biāo)的文法q 考察輸入串A(I, J)，對應(yīng)記號流形式id(id, id)。q 假設(shè)當(dāng)前狀態(tài)格局為：棧輸入 id(id, id $q 規(guī)約/規(guī)約沖突 怎么辦?（依賴于A是一個(gè)數(shù)組或是一個(gè)過程?）244.6 LR語法分析器語法分析器q 本節(jié)介紹LR(k)分析技術(shù)“L”：left-to-right scanning 自左向右掃描“R”：rightmost derivation in reverse 最右推導(dǎo)的逆“k” ：向前看的字符的個(gè)數(shù)，當(dāng) k被省略的時(shí)候

12、, k 假設(shè)為1。25LR分析器的特點(diǎn)分析器的特點(diǎn)q 通用通用q 適用面廣適用面廣q 效率高效率高26LR分析器的特點(diǎn)分析器的特點(diǎn)q 通用通用 一般的移進(jìn)歸約法q 適用面廣適用面廣 適合大多數(shù)的上下文無關(guān)文法q 效率高效率高 實(shí)用274.6.2 LR(0)項(xiàng)目（項(xiàng)目（Item）q 在產(chǎn)生式右部加上，表示分析過程中的狀態(tài),指示產(chǎn)生式右部符號已經(jīng)被識別了多少之前的子串已經(jīng)出現(xiàn)在棧中之后的子串是下一步希望將看到的q 在文法產(chǎn)生式右部某個(gè)位置標(biāo)有 的產(chǎn)生式，稱為文法的一個(gè)LR(0)項(xiàng)目。形如 A 的項(xiàng)目稱為歸約項(xiàng)目；形如 A B 的項(xiàng)目稱為待約項(xiàng)目(基本項(xiàng)目)；形如 A a 的項(xiàng)目稱為移進(jìn)項(xiàng)目。 A

13、bYZcA bYZcA bYZc28LR(0)項(xiàng)目項(xiàng)目例如，產(chǎn)生式AXYZ對應(yīng)四個(gè)項(xiàng)目：A XYZA XYZA XYZA XYZ注意，產(chǎn)生式A只對應(yīng)一個(gè)項(xiàng)目： A 29增廣文法增廣文法q 對文法GS增加產(chǎn)生式S S， S S稱為初始項(xiàng)初始項(xiàng) S S 是唯一動作為accept的狀態(tài)。 30閉包運(yùn)算閉包運(yùn)算closureq 項(xiàng)目閉包：設(shè)I是文法G的一個(gè)LR(0)項(xiàng)目集合，I的項(xiàng)目閉包c(diǎn)losure(I)定義如下：I closure(I)若項(xiàng)目A B closure(I)，且 B 是G的產(chǎn)生式，則項(xiàng)目B closure(I) 不斷應(yīng)用這個(gè)規(guī)則，知道沒有新項(xiàng)可以加入到closure(I)中為止。clo

14、sure(I)僅包含上述兩條規(guī)則確定的LR(0)項(xiàng)目。31E EE E + T | TT T * F | FF ( E ) | id如果 I 是項(xiàng)目集合E E，那么closure(I) 包括下列項(xiàng)目：E EE E + T E TT T * F T FF ( E ) F id例例 4.26 考慮拓廣的表達(dá)式文法：考慮拓廣的表達(dá)式文法：32function closure(I) J = I; repeat for ( J中的每一項(xiàng) A B ) for ( G的每一個(gè)產(chǎn)生式B ) if ( 項(xiàng)B 不在J中 ) 將 B 加入到J中 until 在某一輪中沒有新的項(xiàng)目加入到 J中 return J；cl

15、osure的計(jì)算33核心項(xiàng)目和非核心項(xiàng)目核心項(xiàng)目和非核心項(xiàng)目q 可以把項(xiàng)目集中的項(xiàng)目分為兩類：（1）核心項(xiàng)目(Kernel items)：初始項(xiàng)S S和所有點(diǎn)不在左端的項(xiàng)目 例如：E E ，E E + T （2）非核心項(xiàng)目(Non-kernel items)：點(diǎn)在左端的非初始項(xiàng)目非核心項(xiàng)目可以通過求核心項(xiàng)目集的閉包得到。 例如：E E + T ， E T34轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù)gotoq 若I是文法G的一個(gè)LR(0)項(xiàng)目集，X是G中的文法符號，定義轉(zhuǎn)移函數(shù) goto(I, X) = closure(J)其中 J =A X | A X I functionfunction goto(I, X) J

16、= ; J = ; for ( 對I中的每個(gè)形如A X的產(chǎn)生式 ) 把項(xiàng) A X 加入到J中； returnreturn closure(J) q 項(xiàng)目A X 稱為項(xiàng)目A X的后繼。35例例 4.27q 若項(xiàng)目集 I = E E, E E +T，計(jì)算 goto(I, +)得到以下項(xiàng)目集：E E + TT T * F T F F ( E )F id J= E E + T closure(J)36void items(G) C = closure(S S) repeat for ( C 的每個(gè)項(xiàng)目集 I ) for ( 每個(gè)文法符號 X ) if ( goto(I, X) 非空且不在C中 ) 將將

17、goto(I, X) 加入到 C中 until 在某一輪中沒有新的項(xiàng)集被加入到 C中The sets-of-Items construction構(gòu)造構(gòu)造LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族37例例4.28 設(shè)文法設(shè)文法G的產(chǎn)生式為的產(chǎn)生式為拓廣文法G：E EE E + T | TT T * F | FF ( E ) | id的LR(0)項(xiàng)目集規(guī)范族為：38構(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 id39I0: I1:= got

18、o ( I0, E )E EE E E E + T E E + T E TT T F I2:= goto ( I0, T )T FE T F (E)T T F F idI3:= goto ( I0, F ) T F 40I4:=goto ( I0, ( )F (E ) E E + T E TT T FT FF (E)F idI5:=goto ( I0, id )F id I6 :=goto ( I1, + )EE + TT T F T F F (E) F id 41I7 :=goto ( I2, * ) T T * F F (E) F idI8 :=goto ( I4, E ) F (E )

19、E E + T I9 :=goto ( I1, + ) E E + T T T *F I10 : T T *F I11: F (E) 42文法的文法的LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族I0: E E E E+T E T T T*F T F F (E) F idI1: E E E E +TI2: E T T T *FI3 : T F I4: F ( E) E E+T E T T T*F T F F (E) F idI5: F id I6: E E+ T T T *F T FF (E) F idI7: T T * F F (E) F idI8: F (E ) E E + T I9: E E + T

20、 T T *F I10: T T *F I11: F (E) 4344LR(0)文法：如果輸入符號為文法：如果輸入符號為a,且狀態(tài)且狀態(tài)j有轉(zhuǎn)換，則移入，否則規(guī)約。有轉(zhuǎn)換，則移入，否則規(guī)約。最右推導(dǎo) E=T=T*F = T*id=F*id =id*id實(shí)際上，不需要Symbols這個(gè)棧454.6.3 LR分析器的模型分析器的模型輸入輸入LR分析驅(qū)動程序分析驅(qū)動程序輸出輸出 棧棧ActionGotosmXmsm-1Xm-1s0a1ai an$分析表分析表M動作表動作表 轉(zhuǎn)向表轉(zhuǎn)向表46例例 4.33 算法表達(dá)式文法算法表達(dá)式文法(1) E E + T (4) T E(2) E T (5) F (

21、E ) (3) T T * F (6) F id 各個(gè)動作的編碼的含義：1. si表示把當(dāng)前輸入符號和狀態(tài)i進(jìn)棧2. rj表示用第j條產(chǎn)生式歸約3. acc表示接受4. 空白項(xiàng)表示出錯(cuò)移進(jìn)shift歸約reduce47action goto 狀 態(tài) id + * ( ) $ E T F 0 1 2 3 4 5 6 7 8 9 10 11 s5 s4 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 r6 r6 r6 r6 s5 s4 s5 s4 s6 s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5 1 2 3 8 2 3 9 3 10 圖

22、圖4.31 表達(dá)式文法的表達(dá)式文法的LR(0)分析表分析表r2r2r4r4r6r6r1r1r3r3r5r5LR(0)文法：如果輸入符號為文法：如果輸入符號為a,且狀態(tài)且狀態(tài)j有轉(zhuǎn)換，則移入，否則歸約。有轉(zhuǎn)換，則移入，否則歸約。48LR語法分析器的行為語法分析器的行為q 為描述LR語法分析的行為，引入概念 格局(Configuration) 用二元組表示 (s0X1s1X2s2Xmsm, aiai+1an$) 棧的內(nèi)容 尚未處理的輸入Xi代表文法符號，si表示狀態(tài)代表右句型代表右句型X1X2Xmaiai+1an在分析棧中增加了狀態(tài)實(shí)際上，只需 (s0s1s2sm, aiai+1an$)。49LR

23、分析算法的動作分析算法的動作q 語法分析器的下一動作由當(dāng)前輸入符號ai和棧頂狀態(tài)sm查詢分析表actionsm, ai 決定 移進(jìn) 歸約 接受 出錯(cuò)50移進(jìn)之前移進(jìn)之前 (s0X1s1X2s2Xmsm, aiai+1an$) 輸入輸入LR分析程序分析程序輸出輸出 Actionsm, ai= “shift s”GotosmXmsm-1Xm-1s0a1ai an$棧棧51移進(jìn)之后移進(jìn)之后 (s0X1s1X2s2Xmsmais , ai+1an$) LR分析程序分析程序輸出輸出 Actionsm, ai= “shift s”GotosmXmsm-1Xm-1s0a1ai an$ais輸入輸入棧棧52歸

24、約之前歸約之前LR分析程序分析程序輸出輸出 棧棧Actionsm, ai= “r A ”smXmsm-rXm-rs0a1ai an$Gotosm-r, A= s 輸入輸入出棧53歸約歸約 從棧中彈出2*| 個(gè)符號LR分析程序分析程序輸出輸出 Actionsm, ai= “r A ”sm-rXm-rs0a1ai an$Gotosm-r, A= s 2*|輸入輸入棧棧54歸約歸約 從棧中彈出2*| 個(gè)符號，再進(jìn)棧LR分析程序分析程序輸出輸出 Actionsm, ai= “r A ”ssm-rXm-rs0a1ai an$Gotosm-r, A= s A2*|輸入輸入棧棧55接受接受LR分析程序分析程

25、序輸出輸出 Actions, $= “accept”sX1s0a1ai an$Goto輸入輸入棧棧56報(bào)錯(cuò)報(bào)錯(cuò)LR分析程序分析程序輸出輸出 Actions, a未定義a1ai an$GotosmXmsm-rXm-rs0輸入輸入棧棧57初始格局初始格局LR分析程序分析程序輸出輸出 Actions, aGotos0a1ai an$輸入輸入棧棧58算法算法4.7 LR分析算法分析算法輸入：一個(gè)輸入串w和文法G的一張LR分析表M。輸出：若wL(G)，輸出w的一個(gè)自底向上的分析； 否則，報(bào)錯(cuò)。方法：初始狀態(tài)s0 分別放在棧頂，w$放在輸入緩沖區(qū)；語法分析器執(zhí)行下面的程序，直至遇見接受或出錯(cuò)動作。59置i

26、p指向w$的第一個(gè)符號；a1ai an$ip60置ip指向w$的第一個(gè)符號；while(1) 61置ip指向w$的第一個(gè)符號；while(1) 令s是棧頂狀態(tài)，a是ip所指向的符號 ss0a1a an$iptopip就是lookaheadinput pointer62置ip指向w$的第一個(gè)符號；while(1) 令s是棧頂狀態(tài)，a是ip所指向的符號if actions, a = “shift s” then begin將a和s先后壓入棧內(nèi)； 讓ip指向下一個(gè)輸入符號；end 63置ip指向w$的第一個(gè)符號；while(1) 令s是棧頂狀態(tài)，a是ip所指向的符號if actions, a = “

27、shift s” then begin將a和s先后壓入棧內(nèi)； 讓ip指向下一個(gè)輸入符號；endelse if actions,a = “reduce A” then begin從棧頂彈出2*|個(gè)符號； 令s是當(dāng)前棧頂狀態(tài)； 把A和gotos, A先后入棧； 輸出產(chǎn)生式A end 64置ip指向w$的第一個(gè)符號；while(1) 令s是棧頂狀態(tài)，a是ip所指向的符號if actions, a = “shift s” then begin將a和s先后壓入棧內(nèi)； 讓ip指向下一個(gè)輸入符號；endelse if actions,a = “reduce A” then begin從棧頂彈出2*|個(gè)符號；

28、 令s是當(dāng)前棧頂狀態(tài)； 把A和gotos, A先后入棧； 輸出產(chǎn)生式A endelse if actions, a = “acc” then return 65置ip指向w$的第一個(gè)符號；while(1) 令s是棧頂狀態(tài)，a是ip所指向的符號if actions, a = “shift s” then begin將a和s先后壓入棧內(nèi)； 讓ip指向下一個(gè)輸入符號；endelse if actions,a = “reduce A” then begin從棧頂彈出2*|個(gè)符號； 令s是當(dāng)前棧頂狀態(tài)； 把A和gotos, A先后入棧； 輸出產(chǎn)生式A endelse if actions, a = “a

29、cc” then return else error( ) 66例例 4.33 算法表達(dá)式文法算法表達(dá)式文法(1) E E + T (4) T E(2) E T (5) F (E ) (3) T T * F (6) F id 各個(gè)動作的編碼的含義：1. si表示把當(dāng)前輸入符號和狀態(tài)i進(jìn)棧2. rj表示用第j條產(chǎn)生式歸約3. acc表示接受4. 空白項(xiàng)表示出錯(cuò)67action goto 狀 態(tài) id + * ( ) $ E T F 0 1 2 3 4 5 6 7 8 9 10 11 s5 s4 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 r6 r6 r6 r6 s5

30、 s4 s5 s4 s6 s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5 1 2 3 8 2 3 9 3 10 圖圖4.31 表達(dá)式文法的表達(dá)式文法的LR(0)分析表分析表r2r2r4r4r6r6r1r1r3r3r5r56869思考：考慮思考：考慮算法算法4.7的效率的效率q 時(shí)間復(fù)雜度O(|w|)無回溯廣泛應(yīng)用的編譯器開發(fā)工具已實(shí)現(xiàn)了這一算法YaccBison70思考：思考：如何構(gòu)造動作表和分析表？如何構(gòu)造動作表和分析表？輸入輸入LR分析程序分析程序輸出輸出 smXmsm-1Xm-1s0a1ai an$棧棧ActionGoto71action goto 狀 態(tài)

31、 id + * ( ) $ E T F 0 1 2 3 4 5 6 7 8 9 10 11 s5 s4 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 r6 r6 r6 r6 s5 s4 s5 s4 s6 s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5 1 2 3 8 2 3 9 3 10 圖圖4.31 表達(dá)式文法的表達(dá)式文法的LR(0)分析表分析表r2r2r4r4r6r6r1r1r3r3r5r5LR(0)文法：如果輸入符號為文法：如果輸入符號為a,且狀態(tài)且狀態(tài)j有轉(zhuǎn)換，則移入，否則歸約。有轉(zhuǎn)換，則移入，否則歸約。72FOLLOW(E)

32、=$, +,)文法文法4.34的的SLR分析表分析表action goto 狀 態(tài) id + * ( ) $ E T F 0 1 2 3 4 5 6 7 8 9 10 11 s5 s4 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 r6 r6 r6 r6 s5 s4 s5 s4 s6 s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5 1 2 3 8 2 3 9 3 10 SLR文法：如果輸入符號為文法：如果輸入符號為a,且狀態(tài)且狀態(tài)j有轉(zhuǎn)換，則移入；有轉(zhuǎn)換，則移入；如果輸入符號在如果輸入符號在Follow(A)中，則歸約，否則報(bào)錯(cuò)。中，

33、則歸約，否則報(bào)錯(cuò)。73q 后續(xù)的內(nèi)容圍繞動作表和分析表的構(gòu)造原理展開q 事實(shí)上，算法4.7是通用的，不同的動作表和分析表的構(gòu)造決定了不同的LR分析方法SLR(1)LR(1)LALR(1)744.6.4 構(gòu)造構(gòu)造SLR分析表分析表q 簡單LR分析（Simple LR）75構(gòu)造構(gòu)造SLR分析表分析表q 狀態(tài)i從Ii構(gòu)造，它的action函數(shù)確定如下：如果Aa在Ii中，并且goto(Ii, a ) = Ij，那么置actioni, a為sj。如果A在Ii中，那么對FOLLOW(A)中的所有a，置actioni, a為rj，j是產(chǎn)生式A的編號。如果SS在Ii中，那么置actioni, $ 為接受acc

34、ept。如果出現(xiàn)動作沖突，那么該文法就不是SLR(1)的。76從從DFA構(gòu)造構(gòu)造SLR分析表分析表q 使用下面規(guī)則構(gòu)造狀態(tài)i的goto函數(shù)：對所有的非終結(jié)符A，如果goto(Ii, A) = Ij, 那么gotoi, A = j。 q 不能由上面兩步定義的條目都置為error。q 分析器的初始狀態(tài)是包含SS的項(xiàng)目集對應(yīng)的狀態(tài)。77算法算法4.32 SLR分析算法分析算法輸入：一個(gè)拓廣文法G輸出：對于G 的分析表的action子表和goto子表方法：1. 構(gòu)造G 的LR(0)項(xiàng)目集規(guī)范族。2. 對于狀態(tài)Ii的分析動作如下： (a) 若A . aB Ii且 goto (Ii ,a)= Ij act

35、ioni,a = “shift j” (b) 若A . Ii, 對于所有a FOLLOW(A) actioni,a = “reduce A” , A S (c) 若SS. Ii, actioni, $= “accept”3. 若goto(Ii, A) = Ij, AVN , 則 gotoi,A = j4. 分析表其余位置為error78action goto 狀 態(tài) id + * ( ) $ E T F 0 1 2 3 4 5 6 7 8 9 10 11 s5 s4 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 r6 r6 r6 r6 s5 s4 s5 s4 s6

36、s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5 1 2 3 8 2 3 9 3 10 FOLLOW(E)=$, +,)文法文法4.34的的SLR分析表分析表79例例4.33q I2:E TT T * Fq 因?yàn)镕OLLOW(E) = $, +, ), 所以action2, $ = action2, + = action2, ) = r2action2, * = s780例例4.34q 每個(gè)SLR(1)文法都不是二義的，但是，有許多非二義的文法不是SLR(1)。q 例如，下面的產(chǎn)生式文法S L=RS RL *RL idR L *id = id *id = *id*

37、id = id*id=*id81拓廣文法拓廣文法G 的的LR(0)項(xiàng)目集規(guī)范族為：項(xiàng)目集規(guī)范族為：I0:S SS L=RS RL *RL idR LI1:SS I2:SL =RRL I3:SR I4:L* RR L L *RL idI5:Lid I6:SL= RR LL *RL idI7:L*R I8:RL I9:SL=R S L=RS RL *RL idR L82idS SS L=RS RL *RL idR LL id S L =RR L S S I0I1I2I3S R I4L * RR LL idL * RI5SL*idRS L= RR LL *RL idI6=RS L=R R L LLI

38、7idI3*L *R RI8I9識別產(chǎn)生式文法識別產(chǎn)生式文法(4-20) 的的DFA83I1I0I3I2I6I9I8I7I5I4startSRLid*=ididLLR*R識別產(chǎn)生式文法識別產(chǎn)生式文法(4-20) 的的DFA84SLR(1)文法的描述能力有限文法的描述能力有限q I2: SL =RRL q 第一個(gè)項(xiàng)目使得action2, = 為shift q 第二個(gè)項(xiàng)目使得action2, = 為reduce，F(xiàn)OLLOW(R) = = , $ =是R的一個(gè)后繼符S L = R * R = R q I2存在移進(jìn)歸約沖突！q 但是，實(shí)際不存在以R=開始的右句型S L=RS RL *RL idR L

39、SLR文法：如果輸入符號為文法：如果輸入符號為a,且狀態(tài)且狀態(tài)j有轉(zhuǎn)換，則移入；有轉(zhuǎn)換，則移入；如果輸入符號在如果輸入符號在Follow(A)中，則歸約，否則報(bào)錯(cuò)。中，則歸約，否則報(bào)錯(cuò)。4.5.4 可行前綴可行前綴 (Viable prefix)q 出現(xiàn)在移進(jìn)歸約分析器棧中的右句型的前綴集合稱為可行前綴。又翻譯成：活前綴(、(E、(E) 是可行前綴， (E) *不是可行前綴E=F*id=(E)*idq 可行前綴是右句型的前綴，不含右句柄之后的任何符號。q 可行前綴后加上終結(jié)符可以得到右句型。q 只有輸入串中已分析過的那部分能歸約成可行前綴，就沒有語法錯(cuò)誤。 棧輸入$( id+id)*id$ $

40、(E )*id$ $(E) *id$*86棧棧 輸輸 入入 動動 作作 $ id1 + id2 * id3$ 移進(jìn)移進(jìn) $id1 + id2 * id3$ 按按E id歸約歸約 $E + id2 * id3$移進(jìn)移進(jìn) $E+ id2 * id3$ 移進(jìn)移進(jìn) $E+ id2 * id3$ 按按E id歸約歸約 $E+E * id3$ 移進(jìn)移進(jìn) $E+E* id3$ 移進(jìn)移進(jìn) $E+E*id3 $按按E id歸約歸約 $E+E*E $按按E E*E歸約歸約 $E+E $按按E E+E歸約歸約 $E $接受接受 可行前綴E+E*中， E*不能歸約，還需從輸入中移進(jìn)。可行前綴E+E*E中，E*E是待歸約的部分。87LR(0)LR(0)自動機(jī)能夠識別可行前綴。自動機(jī)能夠識別可行前綴。LR（0）自動機(jī)）自動機(jī)是一個(gè)識別可行是一個(gè)識別可行前綴的前綴的DFA。88有效項(xiàng)目有效項(xiàng)目q 有效項(xiàng)目：有效項(xiàng)目：如果存在規(guī)范推導(dǎo) S Aw 12w 1xw，則說項(xiàng)目A1 2對可行前