【正文】 0(S10) R3 R3 R3 R3 11(S11) R5 R5 R5 R5 62 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表 ACTION表 文法符號 狀態(tài) 狀態(tài) 若移入： i為狀態(tài) 若規(guī)約： i為產(chǎn)生式編號 文法 G[E] ： (1)E::=E+T (2)E::=T (3)T ::=T*F (4)T::=F (5)F::=(E) (6)F::=i Bn Bt 63 i + * ( ) E T F 0 S5 S4 1 2 3 1 S6 A CC EPT 2 R2 S7 R2 R2 3 R4 R4 R4 R4 4 S5 S4 8 2 3 5 R6 R6 R6 R6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S 1 1 9 R1 S7 R1 R1 10 R3 R3 R3 R3 1 1 R5 R5 R5 R5 ACTION 表 GOTO 表 輸入符號 狀態(tài) 文法 G[E] (1)E::=E+T (2)E::=T (3)T ::=T*F (4)T::=F (5)F::=(E) (6)F::=i Si：移入， i為狀態(tài) Ri：規(guī)約， i為產(chǎn)生式編號 64 分析過程 ： i*i+i 步驟 狀態(tài)棧 符號 輸入串 動作 1 ＃ 0 ＃ i*i+i 初始化 2 ＃ 0i5 ＃ i *i+i S 3 ＃ 0F3 ＃ F *i+i R6 4 ＃ 0T2 ＃ T *i+i R4 5 ＃ 0T2*7 ＃ T* i+i S 6 ＃ 0T2*7i5 ＃ T*i +i S 7 ＃ 0T2*7F10 ＃ T*F +i R6 GOTO表 ACTION表 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 文法符號 狀態(tài) 11 ＃ 0E1+6i5 E+i S 12 ＃ 0E1+6F3 E+F R6 13 ＃ 0E1+6T9 E+T R4 14 ＃ 0E1 E R1 15 E Accept 9 ＃ 0E1 E +i R2 10 ＃ 0E1+6 E+ i S 8 ＃ 0T2 T +i R3 GOTO表 ACTION表 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 文法符號 狀態(tài) 66 由分析過程可以看到 : (1) 每次規(guī)約總是 規(guī)約 當(dāng)前句型的句柄 ，是規(guī)范規(guī)約，可以看到語法樹 (算符優(yōu)先是規(guī)約最左素短語 ) E E T + T T * F F i i F i 8 7 5 6 4 3 2 1 (2) 分析的每一步棧內(nèi)符號串均是規(guī)范句型的活前綴 ，與輸入串的剩余部分構(gòu)成規(guī)范句型 . 構(gòu)造 SLR分析表 67 構(gòu)造 LR分析器的關(guān)鍵時構(gòu)造其分析表 構(gòu)造 LR分析表的方法是 : （ 1）根據(jù)文法構(gòu)造識別 規(guī)范句型活前綴 的有窮自動機(jī) DFA （ 2）由 DFA構(gòu)造 SLR分析表 68 1. 構(gòu)造 DFA (1) DFA是一個五元式 M=(S, B, GOTO, S0, Z) S：有窮狀態(tài)集 在此具體情況下， S=LR(0)項目集規(guī)范族 LR(0)。 例： ANIXYACC 文法規(guī)則文件 YACC源文件 YACC 某語言的 LALR分析器 48 (4)幾點(diǎn)說明 SLR文法必定是 LALR文法和 LR文法 SLR分析表的構(gòu)造方法 LR分析 （ 1）邏輯結(jié)構(gòu) （ 2） LR分析過程 50 （ 1）邏輯結(jié)構(gòu) 分析動作表 狀態(tài)轉(zhuǎn)移表 控制程序 輸入串： a1 a2 ... ai ... an S0x1S1x2...... xmSm LR分析器 狀態(tài)棧 51 ☆ 狀態(tài)棧 : S0,S1,…,S m 狀態(tài) S0初始狀態(tài) Sm棧頂狀態(tài) 棧頂狀態(tài)概括了從分析開始到該狀態(tài)的 全部分析歷史和展望資料 . ☆ 符號串 : X1X2..... Xm 為從開始狀態(tài) (S0)到當(dāng)前狀態(tài) (Sm)所識別的規(guī)范句型的活前綴 . S0x1S1x2...... xmSm S0S1...... Sm x1x2..... xm 52 規(guī)范句型： 通過規(guī)范規(guī)約得到的句型 . 規(guī)范句型前綴： 將輸入串的剩余部分與 其 連結(jié)起來就構(gòu)成了規(guī)范句型 . 如： x1x2..... xmai ... an為規(guī)范句型 x1x2..... xm 為規(guī)范句型前綴 ai ... an為輸入串的剩余部分 活前綴： 若分析過程能夠保證 棧中符號 均是 規(guī)范句型的前綴 ，則表示輸入串已分析過的部分沒有語法錯誤，所以稱為規(guī)范句型的活前綴 . 規(guī)范句型的活前綴 : 對于句型 αβt， β表示句柄 ,如果 αβ=u1u2…u r 那么符號串 u1u2…u i(1≤i≤r)即是句型 αβt的活前綴 例：有文法 E→T | E+T | E T T→i | (E) 拓廣文法 G’： S→E E→T | E+T | E T T→i | (E) 已知句型 E(i) ，求 活前綴 ? E, E, E(, E(i 是句型 E(i+i) 的活前綴。 (2)LR分析器有三部分 : 狀態(tài)棧、分析表、控制程序 控制程序 分析表 狀態(tài)棧 輸入串 46 (3)分析表的種類 a) SLR分析表 (簡單 LR分析表 ) b) LR分析表 (規(guī)范 LR分析表 ) 構(gòu)造簡單 ,最易實現(xiàn) ,大多數(shù)上下文無關(guān)文法都 可以構(gòu)造出 SLR分析表 ,所以具有 較高的實用 價值。 ，則存在優(yōu)先函數(shù)， f(a)和 g(b)等于從 fa 和 gb出發(fā)所能到達(dá)的結(jié)點(diǎn)個數(shù)（包括該結(jié)點(diǎn)自身）。＞ b，則從 fa至 gb畫一條??； 若 a＜ 算法 : 從優(yōu)先關(guān)系構(gòu)造優(yōu)先函數(shù) 方法： ∈ VT∪ {},建立兩個符號 fa和 ga。＞ b時 , f(a)＞ g(b)。b 時 , f(a)＜ g(b)。對于終結(jié)符號 a和 b選擇 f和 g,使之滿足： 1. 當(dāng) a=b時 , f(a)= g(b)。表明找到了素短語的尾，再往前找其頭，并進(jìn)行規(guī)約。 31 構(gòu)造優(yōu)先關(guān)系矩陣的算法 FOR 每條規(guī)則 A::=x1x2…x n DO FOR i:=1 TO n1 DO BEGIN IF xi和 xi+1均為終結(jié)符 ,THEN 置 xi=xi+1 IF i≤n2，且 xi和 xi+2都為終結(jié)符號但 xi+1為非終結(jié)符號 THEN 置 xi=xi+2 IF xi為終結(jié)符號 xi+1為非終結(jié)符號 THEN FOR FIRSTVT(xi+1)中的每個 b DO 置 xib IF xi為非終結(jié)符號 xi+1為終結(jié)符號 THEN FOR LASTVT(xi)中的每個 a DO 置 axi+1 END . . . . 32 （ 3）算符優(yōu)先分析算法的實現(xiàn) . 先定義優(yōu)先級，在分析過程中通過比較相鄰運(yùn)算符之間的優(yōu)先級來確定句型的“句柄”并進(jìn)行歸約 . [定義 ] 素短語：文法 G的句型的素短語是一個短語，它至少包含有一個終結(jié)符號，并且除它自身以外不再包含其他素短語 . 最左素短語 ？ 33 文法的語法樹 : E T E + T + T T F * F i E 短語 :T+T*F+i, T+T*F T(最左 ), T*F, i 其中 T不包含終結(jié)符 ,T是句型 而 T+T*F+i和 T+T*F包含其他 素短語 . 只有 T*F和 i為素短語 ,其中 T*F為最左素短語 ,而該句型句柄為 T. 例 : 文法 G[E] E::=E+T|T T::=T*F|F F::=(E)|i 求句型 T+T*F+i 的素短語 34 于是算符優(yōu)先分析法：如何確定當(dāng)前句型的最左素短語？ 設(shè)有 OPG文法句型為 : N1a1N2a2…N nanNn+1 其中 Ni為非終結(jié)符 (可以為空 ), ai為終結(jié)符 定理 ：一個 OPG句型的最左素短語是滿足下列條件的 最左子串： aj1N