【正文】 若項目 E’→E .∈ k, 則置 ACTION[ k , ] =ACCEPT ACTION表中不能用步驟 2~4填入信息的 空白格，均置 ERROR 93 在狀態(tài)中可有三種類型的項目 ,其中只有兩種有移 進(jìn)或規(guī)約動作 : A→ a∈ Bt 移進(jìn)項目 分析動作 :移進(jìn) A→ α. 規(guī)約項目 分析動作 :規(guī)約 A→ B∈ Bn 待約項目 無動作 根據(jù)上述算法 ,可以構(gòu)造出文法 G’[E’]的 ACTION 94 對文法 G’[E’] k=2(I2) 有效項目 E→T. T→T.*F FOLLOW(E)={, +, )} k=1(I1) E’→E. E→E.+T FOLLOW(E’)={} k=0(I0) E’→.E E→.E+T E→.T T→.T*F T→.F F→.(E) F→.i 根據(jù)算法造出的 ACTION表為 : 95 4 狀態(tài) s 輸入符號 a i * ( ) 0 1 2 3 ACTION表 5 6 7 8 9 10 11 S5 S6 S7 r2 r2 r2 accpet S4 + 96 兩點說明 : 1. 由 DFA構(gòu)造出的 SLR分析表 ,在造表示 ,我們 只需向前看一個符號就能確定分析的動作是移 進(jìn)還是規(guī)約 .所以 SLR(1)分析表簡稱 SLR分析表 使用 SLR分析表的分析器叫 SLR分析器 . 2. 對文法 G,若使用上述算法 ,所造出的分析表 具有多重定義入口 ,分析動作就不唯一 ,則文法 G就不是 SLR的需要用別的方法來構(gòu)造分析表 . 第五章 語法分析小結(jié) 97 語法分析方法 : 自頂向上分析法 Z? S + 自頂向上分析法 S?Z + S∈ L[Z] (一 ) 自頂向下分析 1 概述自頂向下分析的一般過程 存在問題 左遞歸問題 回溯問題 消除左遞歸的方法 無回溯的條件 改寫文法 超前掃描 98 2 兩種常用方法 : (1)遞歸子程序法 a)改寫文法 ,消除作遞歸 ,回溯 b)寫遞歸子程序 (2)LL(1)分析法 LL(1)分析器的邏輯結(jié)構(gòu)及工作過程 LL(1)分析表的構(gòu)造方法 LL(1)文法的定義以及充分必要條件 First集合的算法 Follow集合的算法 99 (二 ) 自底向上分析 規(guī)約過程 : (1)一般過程 : 移進(jìn) — 規(guī)約過程 (2)算法 : 問題 :如何尋找句柄 i)算符優(yōu)先分析法 : ,分析過程 . 根據(jù)算符優(yōu)先關(guān)系矩陣來決定 是移進(jìn)還是規(guī)約 . 100 引出的 算符優(yōu)先法 的定義 “句柄” ,如何找 有句柄引出的 最左素短語 的概念 . 最左素短語的定理 ,如何找 . ii)LR分析法 概念、術(shù)語 (活前綴、項目 ) 101 1)邏輯結(jié)構(gòu) 2)分析過程 狀態(tài)棧 分析表 控制程序 GOTO表 分析動作表 SLR分析表 1)構(gòu)造 DFA 2)由 DFA構(gòu)造分析表 102 除了遞歸子程序法，其他幾種方法邏輯結(jié)構(gòu)很象： 輸入串 符號棧 (狀態(tài)棧 ) 控制程序 分析表 (1)對于 LL(1)分析法 符號棧 αi (自頂向下，保證最左推導(dǎo) ) LL(1)分析表 αi A A::=αi error 終結(jié)符 非終結(jié)符 首字符 103 (2)對于算法優(yōu)先分析 : 符號棧 棧內(nèi)終結(jié)符 = error 棧外終結(jié)符 (3)LR分析 : 符號棧 S0,S1…S m X0,X1…X m 分析表 狀態(tài)轉(zhuǎn)移 GOTO表 分析動作表 104 GOTO表 下一狀態(tài) 狀態(tài) 符號 根據(jù)棧頂狀態(tài)和棧 頂符號推導(dǎo)出下一 狀態(tài) 分析動作表 移進(jìn) S 規(guī)約 (rj) 狀態(tài) 終結(jié)符號 根據(jù)棧頂狀態(tài)和輸入 符號推導(dǎo)出下一動作 105 將 GOTO表和分析動作表壓縮后得 : 狀態(tài) 終結(jié)符號 非終結(jié)符號 GOTO表 Si rj i(下一狀態(tài)數(shù) ) ?！?E E→.E+T E→.T T→.T*F T→.F F→.(E) F→.i 81 I6: E→E+.T GOTO(I 1,+)=closure({E→E+.T})= I 6 T→.T*F GOTO(I 1,其他符號 )為空 T→.F F→.(E) F→.i I7: T→T*.F GOTO(I2,*)=closure({T→T*.F})= I 7 F→.(E) GOTO(I2,其他符號 )為空 F→.i GOTO(I3,其他符號 )為空 I1: E39?！?E E→.E+T E→.T T→.T*F T→.F F→.(E) F→.i I1: E39。[E39。[E39。 repeat for LR(0)中的每個項目集 I和 G39。 begin LR(0):={closure({E39。→LR(0) Procedure ITEMSETS(G39。 begin 將屬于 I的項目加入 closure(I)。[E]) 72 Ⅱ . 根據(jù)文法列出所有的項目 Ⅲ . 將有關(guān)項目組合成集合，即 DFA中的狀態(tài)； 所有狀態(tài)再組合成一個集合，即 LR（ 0） 項目集規(guī)范族 我們通過一個具體例子來說明 LR(0)的構(gòu)造以及 DFA 的構(gòu)造方法 例： G[E] E→E+T|T T→T*F|F F→(E)|i 73 例 :G[E] E→E+T|T T→T*F|F F→(E)|i 1 將文法拓廣為 G’[E’] (0) E’→E (4) T→F (1) E→E+T (5) F→(E) (2) E→T (6) F→i (3) T→T*F 2 列出文法的所有項目 (1) E’→.E (2) E’→E. (3) E→.E+T (4) E→E.+T (5) E→E+.T (6) E→E+T. (7) E→.T (8) E→T. (9) T→.T*F (10) T→T.*F (11)T→T*.F (12)T→T*F. (13)T→.F (14)T→F. (15)F→.(E) (16)F→(.E) (17)F→(E.) (18)F→(E). (19)F→.i (20) F→i. 74 3 將有關(guān)項目組成項目集 ,所有項目集構(gòu)成的集合即為 LR(0) 為實現(xiàn)這一步，先定義： ? 項目集閉包 closure ? 狀態(tài)轉(zhuǎn)移函數(shù) GOTO 例 :G’[E’] 令 I={E’→.E} closure(I)={E’→.E, E→.E+T, E→.T, T→.T*F, T→.F, F→.(E), F→.i } 75 closure的定義和計算 : 令 I是文法 G’的任一項目集合，定義 closure(I)為項目集合I的閉包，可用一個過程來定義并計算 closure(I)。 →E E→[E39。 方法：修改文法，使識別符號的規(guī)則只有一條 G[E] E→ 例 :產(chǎn)生式 :A→XYZ 項 目 : A→.XYZ A→ A→ A→XYZ. 產(chǎn)生式 :A→ε 項 目 : A→. 項目的直觀意義 :指明在分過程中的某一時刻已經(jīng)規(guī)約的部分和等待規(guī)約部分。 M=(S, B, GOTO, S0, Z) S0 S1 Si1 S2 Si X1 X2 Xi1 Xi 57 b. 分析動作表 (ACTION表 ) Sn 狀態(tài) s 輸入符號 a i + * ( ) S0 S1 S2 : ACTION表 ACTION[Si,a]=動作分析 a∈ Bt 58 分析動作： 1)移進(jìn) (shift) ACTION[Si,a]= Sj 動作：將 a推進(jìn)棧，并設(shè)置新的棧頂狀態(tài) Sj Sj=GOTO[Si,a]，將指針指向下一個輸入符號 2)規(guī)約 (reduce) ACTION[Si,a]=rd d：文法規(guī)則編號 (d) A→β 動作：將符號串 β(假定長度為 n)連同狀態(tài)從棧內(nèi)彈出把 A推進(jìn)棧，并設(shè)置新的棧頂狀態(tài) Sj , Sj=GOTO[Sin,A] 3)接受 (accept) ACTION[Si,]=accept 4)出錯 (error) ACTION[Si,a]=error 59 ☆ 控制程序 :(Driver Routine) 1) 根據(jù) 棧頂狀態(tài) 和 現(xiàn)行輸入符號 ，查分析動作表 (ACTION表 )，執(zhí)行有分析表所規(guī)定的操作； 2) 并根據(jù) GOTO表設(shè)置新的棧頂狀態(tài) (即實現(xiàn)狀態(tài)轉(zhuǎn)移 ) 60 例：文法 G[E] (1)E::=E+T (2)E::=T (3)T ::=T*F (4)T::=F (5)F::=(E) (6)F::=i （ 2） LR分析過程 該文法是 SLR文法 ,故可以構(gòu)造出 SLR分析表 (ACTION表和 GOTO表 ) ACTION表 GOTO表 文法 G[E] ： (1)E::=E+T (2)E::=T (3)T ::=T*F (4)T::=F (5)F::=(E) (6)F::=i 文法符號 狀態(tài) i + * ( ) E T F 0(S0) S5 S4 1 2 3 1(S1) S6 ACCEPT 2(S2) R2 S7 R2 R2 3(S3) R4 R4 R4 R4 4(S4) S5 S4 8 2 3 5(S5) R6 R6 R6 R6 6(S6) S5 S4 9 3 7(S7) S5 S4 10 8(S8) S6 S11 9(S9) R1 S7 R1 R1 1