【正文】 bB. I7 B?cB. I9 B?d. I11 B d d B c c c 識別文法 活前綴的 DFA 84 LR(0)分析表 a c t i o n g o t o 狀態(tài) a b c d S A B 0 1 2 3 4 5 6 7 8 9 10 11 s 2 s 3 a c c s 4 s 1 0 s 5 s 1 1 s 4 s 1 0 s 5 s 1 1 r 1 r 1 r 1 r 1 r 1 r 2 r 2 r 2 r 2 r 2 r 3 r 3 r 3 r 3 r 3 r 5 r 5 r 5 r 5 r 5 r 4 r 4 r 4 r 4 r 4 r 6 r 6 r 6 r 6 r 6 1 6 7 8 9 85 續(xù)例：已知文法 G： S→E E→aA | bB A→cA | d B→cB | d G 的所有 LR(0)項目為： [1] S→E [2] S→E [3] E→aA [4] E→aA [5] E→a A [6] E→bB [7] E→bB [8] E→bB [9] A→cA [10] A→cA [11] A→cA [12] A→d [13] A→d [14] B→cB [15] B→cB [16] B→cB [17] B→d [18] B→d I0=closure({S→E })={ S→E, E→aA , E→bB } ； GO(I0, E)={ S→E}= I1 ； GO(I0, a)={ E→aA , A→cA, A→d }= I2 ； GO(I0, b)={ E→bB , B→cB, B→d }= I3 ； GO(I2, A)={ E→a A}= I4 ； GO(I2, c)={ A→cA , A→cA, A→d }= I5 ； GO(I2, d)={ A→d}= I6 ； GO(I3, B)={ E→bB}= I7 ； GO(I3, c)= { B→cB , B→cB, B→d }= I8 ； GO(I3, d)= { B→d}= I9 ； GO(I5, A)={ A→cA}= I10 ； GO(I5, c)= { A→cA , A→cA, A→d }= I5 ； GO(I5, d)= { A→d}= I6 ； GO(I8, B)= { B→c B}= I11 ； GO(I8, c)= { B→cB , B→cB, B→d }= I8 ； GO(I8, d)= { B→d}= I9 。 則該文法的 LR(0)項目集規(guī)范族 C={ I0, I1, I2, I3, I4, I5, I6, I7, I8, I9, I10, I11}。 該文法的 LR(0)分析表為： 狀態(tài) ACTION GOTO a b c d E A B 0 S2 S3 1 1 acc 2 S5 S6 4 3 S8 S9 7 4 r2 r2 r2 r2 r2 5 S5 S6 10 6 r5 r5 r5 r5 r5 7 r3 r3 r3 r3 r3 8 S8 S9 11 9 r7 r7 r7 r7 r7 10 r4 r4 r4 r4 r4 11 r6 r6 r6 r6 r6 SLR分析表的構造 我們以一個簡單的變量聲明作為例子來分析沖突問題和解決方法。設整型變量的聲明的文法 整型變量聲明 → integer 標識符表 標識符表 → 標識符表 , v | v 將它縮寫后并增廣如下： (0) D? → D (1) D → i L (2) L → L, v (3) L → v 87 SLR分析表的構造 I5： L → L,v ， v i I0： D’ →D D →iL I1： D’→ D I3： D→ i L ? L → L,v I4： L → v I2： D → iL L →L,v L →v D L v I6： L → L, v 從 I0=CLOSURE({R’ → ?R })出發(fā)構造 DFA，結果如下圖。 分析狀態(tài) I3可以發(fā)現，它包含了歸約項 D→ i L 和移進項 L → L,v 。 依據 LR(0)的分析方式，在該狀態(tài)，不論面臨什么輸入符號，特別是包括符號逗號“，”都要把 i L規(guī)約成 D；但是，按照移進項 L → L,v 則在面臨符號“，”時，應該把它移入符號棧，同時轉到狀態(tài) 5。 這樣，對于 ACTION[3, ,]就會有 r1和 s5兩個動作，出現移進－歸約沖突，控制程序將不知所措。 88 SLR分析表的構造 – 對沖突情況有兩種解決途徑：修改文法，或者對分析方法加以改進。顯然，修改文法 LR(0)分析并不可取，更好的措施是改善分析技術，以適應更廣泛、實用的文法。 – 在這種情況下，我們只需考察把句柄 iL歸約成 D時， D之后的跟隨符號集是否包含當前所有移進項中移進符號（“，”），如果不包含這樣就可以解決這種移進－歸約沖突。 – 例子中 FOLLOW(D)={$}，而狀態(tài) 3中移進符號的集合是 {,}，所以，在面臨輸入符號是“ $”時，就執(zhí)行歸約，即ACTION[3,$]= r1，在面臨輸入符號是“ ,”時，就執(zhí)行移進操作，即 ACTION[3,]= s5。這種處理沖突的方法只需要對 LR(0)分析表簡單地進行改動，稱作簡單 LR(0)分析， SLR(1)。 89 SLR分析表的構造 一般，設 LR(0)項集規(guī)范族的某個項集 I含有 m個移進項 A1 →αa1β1 ...... Am →αamβm 和 n個歸約項 B1 → γ1 ...... Bn → γn 若集合 {a1,..., am}和 FOLLOW(B1),......, FOLLOW(Bn)兩兩不相交，那么， 隱含在項集 I中沖突可以根據當前輸入符號 a唯一地確定動作，解決沖突： （ 1）若 a?{a1,..., ai}，則移進； （ 2）若 a? FOLLOW(Bi)， i=1,2,...,m，則用 Bi → γi 進行歸約； （ 3）否則，報錯。 90 SLR分析表的構造 – 如果一個文法項集中的所有沖突性動作的都可以按這種方法解決，這樣的文法稱作 SLR(1)文法，由此構造的分析表叫做 SLR(1)分析表，使用 SLR(1)分析表的分析器叫做 SLR(1)分析器。 – SLR(1)分析表的構造步驟和 LR(0)分析表的構造類似，只須在完成 DFA以后按照 SLR(1)方法解決可能的沖突。類似地，完成 SLR(1)分析表的算法也有兩種，而且只需對算法 。 91 SLR分析表的構造 – 從 DFA構造 SLR(1)分析表的算法 ： (1) 修改算法 （ 4）句中 for每個 a ? VT do { ACTION[k, a] = rj}為 for每個 a ? FOLLOW(A) do { ACTION[k, a] = rj} (2) 其它不變。 – 從文法 G的項集規(guī)范族和狀態(tài)轉換函數構造 SLR(1)分析表的算法 ： (1) 把算法 （ 2）條規(guī)則“對于任何終結符 a（包括$），置 ACTION[k, a] = rj”修改為 “對任何屬于 FOLLOW(A)的 a，置 ACTION[k, a] = rj” (2) 其它不變。 92 SLR分析表的構造 狀態(tài) ACTION GOTO i , v $ D L 0 s2 1 1 acc 2 s4 3 3 s5 r1 4 r3 r3 5 s6 6 r2 r2 按照上述算法構造出文法 SLR(1)分析表如表 。其中FOLLOW(D)=FOLLOW(D’)={$}， FOLLOW(L)={,， $}。 表 文法 SLR（ 1）分析表 93 SLR分析法 ? 文法 G – AaA – Aa|b ? 構造 G[A]的拓廣文法 G[S] – (0) SA – (1) AaA – (2) Ab – (3) Aa 94 Ab. A A.aA A.b Aa. SA. S.A A.aA A.b A.a A b a b a AaA. A acc 移進還是歸約？ 95 Ab. (2) A A.aA A.b Aa. (3) SA. (1) S.A A.aA A.b A.a (0) A b a b a AaA. (4) A acc 狀態(tài) a b A 0 s3 s2 1 1 acc 2 r2 r2 r2 3 沖突 s3 r3 s2 r3 r3 4 4 r1 r1 r1 LR(0)分析表 96 問題分析 ? 問題：存在移進 /歸約沖突 ? 分析：實際上， A僅在遇到 FOLLOW(A)中的元素時，才應當進行歸約，否則是出錯的。 – 若 {a}與 FOLLOW(A)不相交，則 – 移進或歸約的動作就可以唯一確定。 ? 解決方法 ——SLR： – b屬于 FOLLOW(A)時， ACTION[A,b]為歸約 97 Ab. (2) A A.aA A.b Aa. (3) SA. (1) S.A A.aA A.b A.a (0) A b a b a AaA. (4) A acc 狀態(tài) a b A 0 s3 s2 1 1 acc 2 r2 r2 r2 3 s3 s2 r3 4 4 r1 r1 r1 SLR分析表 98 小結 ? 自頂向下分析法 – 遞歸下降分析 – 預測分析 – LL(1)分析表構造 ? 自底向上分析法 – 簡單優(yōu)先分析法 – 算符優(yōu)先分析法 – LR(0)分析法 – LR(0)分析表構造 – SLR分析法 99 第四章 語法分析小結 100 語法分析方法 : 自頂向上分析法 Z? S + 自頂向上分析法 S?Z + S∈ L[Z] (一 ) 自頂向下分析 1 概述自頂向下分析的一般過程 存在問題 左遞歸問題 回溯問題 消除左遞歸的方法 無回溯的條件 改寫文法 超前掃描 101 2 兩種常用方法 : (1)遞歸子程序法 a)改寫文法 ,消除作遞歸 ,回溯 b)寫遞歸子程序 (2)LL(1)分析法 LL(1)分析器的邏輯結構及工作過程 LL(1)分析表的構造方法 LL(1)文法的定義以及充分必要條件 First集合的算法 Follow\select集合的算法 102 (二 ) 自底向上分析 規(guī)約過程 : (1)一般過程 : 移進 —規(guī)約過程 (2)算法 : 問題 :如何尋找句柄 i)算符優(yōu)先分析法 : ,分析過程 . 根據算符優(yōu)先關系矩陣來決定 是移進還是規(guī)約 . ii)LR分析法 103 1)邏輯結構 2)分析過程 狀態(tài)棧 分析表 控制程序 GOTO表 分析動作表 LR(0)分析表 1)構造 DFA 2)由 DFA構造分析表 概念、術語 (活前綴、項目 ) 104 除了遞歸子程序法，其他幾種方法邏輯結構很象： 輸入串 符號棧 (狀態(tài)棧 ) 控制程序 分析表 (1)對于 LL(1)分析法 符號棧 αi (自頂向下，保證最左推導 ) LL(1)分析表 αi A A::=αi error 終結符