【正文】 →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 關于自動機的說明 : 1 除 I0以外 ,其余狀態(tài)都是活前綴的識別狀態(tài) ,從 I0到每一狀態(tài) 的每條路徑都識別和接受一個規(guī)范句型的活前綴 如對文法句子 i+i*i 進行規(guī)范規(guī)約， 所得到的 規(guī)范句型 的 活前綴 都可 以由該自動機識別 ,如 : 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)中每個項目對該狀態(tài)能識別的活前綴都 有效 . 有效項目定義 :若項目 A→ β 1 .β2，對活前綴 αβ 1 有效，則其條件是存在規(guī)范推導 E’?αAw ? αβ1β2 w 注意： 項目中圓點前的符號串成為活前綴的后綴 * * 88 3 有效項目能預測分析的下一步動作： E→E+T. 表示已將輸入串規(guī)約為 E+T,下一步應 該將 E+T規(guī)約為 E E’ ?(E)?(E+T) T→T.*F 表示已將輸入串規(guī)約為 T,下一步動作 是移進輸入符號 * 注意： 經(jīng)移進或規(guī)約后 ,在棧內(nèi)仍是規(guī)范句型的活前綴 89 4 DFA中的狀態(tài) ,既代表了分析歷史又提供了展望信息 每條規(guī)范句型的活前綴都代表了一個確定的 的規(guī)范規(guī)約過程 ,故有狀態(tài)可以代表分析歷史 . 由于狀態(tài)中的項目都是有效項目 ,所以提供了 下一步可能采取的動作 . 歷史 +展望 +實現(xiàn) ? 句柄 90 （ 2）由 DFA構(gòu)造 SLR分析表 * GOTO表在求 LR（ 0）時已求出 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 設 k為狀態(tài)編號 ,E為原文法識別符號， E’為擴充文法識別符號 * 求 ACTION表 求出文法每個非終結(jié)符的 FOLLOW集合 若項目 A→p .aq ∈ k,且 a ∈ Bt,則置 ACTION[k,a]=S (移進） 92 若項目 A→p .∈ k, 那么對輸入符號 a,若 a∈ FOLLOW(A),則置 ACTION[k,a]=rj 其中 A→p 為文法 G’的第 j個產(chǎn)生式。]共有 20個項目 LR(0)={I0,I1,I2,…I 11} 有 12個項目組成 : I0: E39。的每個符號 X do if GOTO(I , X)非空 ,且不屬于 LR(0) then 把 GOTO(I , X)放入 LR(0)中 until LR(0)不再增大 end 79 例 .求 G39。)。 Procedure closure(I)。 E→] E39。 E→ 71 Ⅰ . 將文法擴充 構(gòu)造 LR(0)文法的方法 (三步 ) 目的：使構(gòu)造出來的分析表只有一個接受狀態(tài) ,這是 為了實現(xiàn)的方便。 53 S E E T ( ) E T i 54 ☆ 分析表 是一個矩陣： 行 分析器的狀態(tài) 列 文法符號 狀態(tài) 符號 E T F S0 S1 S2 : Sn GOTO表 a. 狀態(tài)轉(zhuǎn)移表 (GOTO表 ) 55 GOTO[Si1, xi]=Si Si1 當前狀態(tài) (棧頂狀態(tài) ) xi 新的棧頂符號 Si 新的棧頂狀態(tài) (狀態(tài)轉(zhuǎn)移 ) Si需要滿足條件是 : 若 X1X2…. X i1是由 S0到 Si1所識別的規(guī)范句型的活前綴 ,則 X1X2…. X i是由 S0到 Si所識別的規(guī)范句型的活前綴 S0x1S1x2...... xi1Si1 xiSi 狀態(tài) 符號 E T F S0 S1 S2 : Sn GOTO表 56 通過對有窮自動機的了解 ,我們可以看出 : 狀態(tài)轉(zhuǎn)移函數(shù) GOTO是定義了一個以文法符號集為字母表的有窮自動機，該自動機識別文法 所有 規(guī)范句型的活前綴 。 id + * f 6 6 4 2 g 7 5 3 2 41 注意特點 : (a) 優(yōu)先函數(shù)值不唯一 (b) 優(yōu)點： ? 節(jié)省內(nèi)存空間 ? 若文法有 n個終結(jié)符，則關系矩陣為 n2 而優(yōu)先函數(shù)為 2n ? 易于比較：算法上容易實現(xiàn) ,數(shù)與數(shù)比 ,不必 查矩陣 . (c) 缺點：可能掩蓋錯誤 . 算符優(yōu)先分析小結(jié) 優(yōu)點 、效率高 缺點 、存在查不到的語法錯誤 LR分析法的概述 43 (1)LR分析法的優(yōu)缺點 (2)LR分析器有三部分 : 狀態(tài)棧、分析表、控制程序 (3)分析表的種類 (4)補充說明 (1) LR分析法的優(yōu)缺點 : 1) 適合文法類足夠大 ,適用于所有上下文無關文法 2) 分析效率高 3) 報錯及時 4) 可以自動生成 5) 手工實現(xiàn)工作量大 45 狀態(tài)棧：放置分析 器狀態(tài)和文法符號 . 分析表：由兩個矩陣組成，其功能是指示分析器的動作， 是 移進 還是 規(guī)約 ，根據(jù)不同的文法類要采用不同 的構(gòu)造方法 . 控制程序：執(zhí)行分析表所規(guī)定的動作，對棧進行操作。 a = b, 從 fa至 gb畫一條弧；也從 gb至 fa畫 一條弧 ， b ∈ VT， 若 a 3. 當 a 優(yōu)先函數(shù) 為了節(jié)約存儲空間和便于執(zhí)行比較運算 ?，用兩個優(yōu)先函數(shù) f和 g，它們是從終結(jié)符號映射到整數(shù)的函數(shù)。 END。 FOR 每個形如 A::=…a 或 A::=…aB 的規(guī)則 DO INSERT (A,a)。 /* b∈ FIRSTVT(A)*/ END OF WHILE END 上述算法的工作結(jié)果是得到一個二維的布爾數(shù)組 F,從 F 可以得到任何非終結(jié)符號 A的 FIRSTVT FIRSTVT(A)={b|F[A,b]=TRAE} 29 構(gòu)造 LASTBT(A)的算法 A::=…a 或 A::==…aB, 則 a∈ LASTVT(A) A::=…B, 且 a∈ LASTVT(B)則 a∈ LASTVT(A) 設一個棧 ST,和一個布爾數(shù)組 B PROCEDARE INSERT(A,a) IF NOT B[A,a] THEN BEGIN B[A,a]::=TRAE。168。168。 。 的規(guī)則，其中 B? b 2) ab if 文法中有形如 A→ 168。 168。 BC 2) 稱為算符優(yōu)先分析是因為這種方法是 仿效 算術式的四則運算 而建立起來的，作算術式的四則運算時，為了保證 計算結(jié)果 和過程的 唯一性 ，規(guī)定了一個統(tǒng)一的 四則運算法則 ，規(guī)定運 算符之間的 優(yōu)先關系 。