【正文】 →.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 I2: E→T. T→T.*F 82 I8: F→(E.) GOTO(I4,F)=closure({F→(E.),E→E.+T})= I 8 E→E.+T GOTO(I4,T)= I2 ∈ LR(0) GOTO(I4,F)= I3 ∈ LR(0) GOTO(I4,()= I4 ∈ LR(0) GOTO(I4,i)= I5 ∈ LR(0) GOTO(I4,+)=φ GOTO(I4,*)=φ GOTO(I4,))=φ GOTO(I5,其他符號 )=φ I9: E→E+T. GOTO(I6,T)=closure({E→E+T.,T→T.*F})= I 9 E→T.*F GOTO(I6,F)= I3 GOTO(I6,()= I4 GOTO(I6,i)= I5 I4: F→(.E) E→ .E+T E→ .T T→.T*F T→.F F→.(E) F→.i 83 I10:T→T*F. GOTO(I7,T)=closure({T→T*F .})= I 10 GOTO(I7,()= I4 GOTO(I7,i)= I5 I11:F→(E). GOTO(I8,))=closure({F→(E) .})= I 11 GOTO(I7,()= I4 GOTO(I7,i)= I5 求完所有 Ii的后繼 GOTO(I8,+)= I6 GOTO(I9,*)= I7 GOTO(I10,所有符號 )=φ, GOTO(I11,所有符號 )=φ 84 （ 3）構(gòu)造 DFA M=(S, B, GOTO, S0, Z) S ={I0, I1, I2, …, I 11}=LR(0) B ={+, *, i, (, ), E, T, F} GOTO(Im , X)= Im S0=I0 Z=S{I0}={I1, I2, …, I 11} M的圖解表示如下 : 85 I0 I5 I2 I4 I3 I1 I11 I8 I6 I10 I7 I9 start E + + i F ( T T F ( i F ( i E ( * * ) + i F 86 關(guān)于自動(dòng)機(jī)的說明 : 1 除 I0以外 ,其余狀態(tài)都是活前綴的識別狀態(tài) ,從 I0到每一狀態(tài) 的每條路徑都識別和接受一個(gè)規(guī)范句型的活前綴 如對文法句子 i+i*i 進(jìn)行規(guī)范規(guī)約， 所得到的 規(guī)范句型 的 活前綴 都可 以由該自動(dòng)機(jī)識別 ,如 : I0~I3 F(+i*i) I0~I2 T(+i*i) I0~I1 識別規(guī)范句型的活前綴 E(+i*i) I0~I6 識別規(guī)范句型的活前綴 E+(i*i) I0~I7 識別規(guī)范句型的活前綴 E+T*(i) I0~I9 識別規(guī)范句型的活前綴 E+T(*i) I0~I10 識別規(guī)范句型的活前綴 E+T*F E E T + T T * F F i i 8 5 F i 7 4 3 2 1 (0) E’→E (3) T→T*F (6) F→i (1) E→E+T (4) T→F (2) E→T (5) F→(E) 6 87 2 要求狀態(tài)中每個(gè)項(xiàng)目對該狀態(tài)能識別的活前綴都 有效 . 有效項(xiàng)目定義 :若項(xiàng)目 A→ β 1 .β2，對活前綴 αβ 1 有效，則其條件是存在規(guī)范推導(dǎo) E’?αAw ? αβ1β2 w 注意： 項(xiàng)目中圓點(diǎn)前的符號串成為活前綴的后綴 * * 88 3 有效項(xiàng)目能預(yù)測分析的下一步動(dòng)作： E→E+T. 表示已將輸入串規(guī)約為 E+T,下一步應(yīng) 該將 E+T規(guī)約為 E E’ ?(E)?(E+T) T→T.*F 表示已將輸入串規(guī)約為 T,下一步動(dòng)作 是移進(jìn)輸入符號 * 注意： 經(jīng)移進(jìn)或規(guī)約后 ,在棧內(nèi)仍是規(guī)范句型的活前綴 89 4 DFA中的狀態(tài) ,既代表了分析歷史又提供了展望信息 每條規(guī)范句型的活前綴都代表了一個(gè)確定的 的規(guī)范規(guī)約過程 ,故有狀態(tài)可以代表分析歷史 . 由于狀態(tài)中的項(xiàng)目都是有效項(xiàng)目 ,所以提供了 下一步可能采取的動(dòng)作 . 歷史 +展望 +實(shí)現(xiàn) ? 句柄 90 （ 2）由 DFA構(gòu)造 SLR分析表 * GOTO表在求 LR（ 0）時(shí)已求出 11(S11) 10(S10) 7 9(S9) 11 6 8(S8) 4 5 10 7(S7) 4 5 3 9 6(S6) 5(S5) 4 5 3 2 8 4(S4) 3(S3) 7 2(S2) 6 1(S1) 4 5 3 2 1 0(S0) ) ( * + i F T E GOTO表 文法符號 狀態(tài) 91 設(shè) k為狀態(tài)編號 ,E為原文法識別符號， E’為擴(kuò)充文法識別符號 * 求 ACTION表 求出文法每個(gè)非終結(jié)符的 FOLLOW集合 若項(xiàng)目 A→p .aq ∈ k,且 a ∈ Bt,則置 ACTION[k,a]=S (移進(jìn)） 92 若項(xiàng)目 A→p .∈ k, 那么對輸入符號 a,若 a∈ FOLLOW(A),則置 ACTION[k,a]=rj 其中 A→p 為文法 G’的第 j個(gè)產(chǎn)生式。 若項(xiàng)目 E’→E .∈ k, 則置 ACTION[ k , ] =ACCEPT ACTION表中不能用步驟 2~4填入信息的 空白格，均置 ERROR 93 在狀態(tài)中可有三種類型的項(xiàng)目 ,其中只有兩種有移 進(jìn)或規(guī)約動(dòng)作 : A→ a∈ Bt 移進(jìn)項(xiàng)目 分析動(dòng)作 :移進(jìn) A→ α. 規(guī)約項(xiàng)目 分析動(dòng)作 :規(guī)約 A→ B∈ Bn 待約項(xiàng)目 無動(dòng)作 根據(jù)上述算法 ,可以構(gòu)造出文法 G’[E’]的 ACTION 94 對文法 G’[E’] k=2(I2) 有效項(xiàng)目 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 兩點(diǎn)說明 : 1. 由 DFA構(gòu)造出的 SLR分析表 ,在造表示 ,我們 只需向前看一個(gè)符號就能確定分析的動(dòng)作是移 進(jìn)還是規(guī)約 .所以 SLR(1)分析表簡稱 SLR分析表 使用 SLR分析表的分析器叫 SLR分析器 . 2. 對文法 G,若使用上述算法 ,所造出的分析表 具有多重定義入口 ,分析動(dòng)作就不唯一 ,則文法 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ù)語 (活前綴、項(xiàng)目 ) 101 1)邏輯結(jié)構(gòu) 2)分析過程 狀態(tài)棧 分析表 控制程序 GOTO表 分析動(dòng)作表 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表 分析動(dòng)作表 104 GOTO表 下一狀態(tài) 狀態(tài) 符號 根據(jù)棧頂狀態(tài)和棧 頂符號推導(dǎo)出下一 狀態(tài) 分析動(dòng)作表 移進(jìn) S 規(guī)約 (rj) 狀態(tài) 終結(jié)符號 根據(jù)棧頂狀態(tài)和輸入 符號推導(dǎo)出下一動(dòng)作 105 將 GOTO表和分析動(dòng)作表壓縮后得 : 狀態(tài) 終結(jié)符號 非終結(jié)符號 GOTO表 Si rj i(下一狀態(tài)數(shù) )