【正文】 FOR 每個形如 A::=b… 或 A::=Bb… 的規(guī)則 DO INSERT(A,b) 具體方法如下 : 84 WHILE S棧非空 DO BEIGN 把 S棧的頂項彈出 ,記為 (B,b)/* b∈ FIRSTVT(A)*/ FOR 每條形如 A::=B… 的規(guī)則 DO INSTER(A,b)。 /* b∈ FIRSTVT(A)*/ END OF WHILE END 上述算法的工作結果是得到一個二維的布爾數(shù)組 F,從 F 可以得到任何非終結符號 A的 FIRSTVT FIRSTVT(A)={b|F[A,b]=TRAE} 85 構造 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。把 (A,a)推進 ST棧 。 END。 86 BEGIN FOR 每個非終結符號 A和終結符號 a DO B[A,a]:=FALSE。 FOR 每個形如 A::=…a 或 A::=…aB 的規(guī)則 DO INSERT (A,a)。 WHILE ST棧非空 DO BEGIN 把 ST棧的棧頂彈出 ,記為 (B,a)。 FOR 每條形如 A::=…B 的規(guī)則 DO INSERT(A,a)。 END OF WHILE。 END。 87 構造優(yōu)先關系矩陣的算法 FOR 每條規(guī)則 A::=x1x2…x n DO FOR i:=1 TO n1 DO BEGIN IF xi和 xi+1均為終結符 ,THEN 置 xi=xi+1 IF i≤n2，且 xi和 xi+2都為終結符號但 xi+1為非終結符號 THEN 置 xi=xi+2 IF xi為終結符號 xi+1為非終結符號 THEN FOR FIRSTVT(xi+1)中的每個 b DO 置 xib IF xi為非終結符號 xi+1為終結符號 THEN FOR LASTVT(xi)中的每個 a DO 置 axi+1 END . . . . 88 （ 3）算符優(yōu)先分析算法的實現(xiàn) . 先定義優(yōu)先級，在分析過程中通過比較相鄰運算符之間的優(yōu)先級來確定句型的“句柄”并進行歸約 . [定義 ] 素短語：文法 G的句型的素短語是一個短語，它至少包含有一個終結符號，并且除它自身以外不再包含其他素短語 . 最左素短語 ？ 89 文法的語法樹 : E T E + T + T T F * F i E 短語 :T+T*F+i, T+T*F T(最左 ), T*F, i 其中 T不包含終結符 ,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 的素短語 90 于是算符優(yōu)先分析法：如何確定當前句型的最左素短語？ 設有 OPG文法句型為 : N1a1N2a2…N nanNn+1 其中 Ni為非終結符 (可以為空 ), ai為終結符 定理 ：一個 OPG句型的最左素短語是滿足下列條件的 最左子串： aj1Njaj…N iaiNi+1ai+1 其中 aj1aj aj=aj+1, aj+1= aj+2 ,…, a i2= ai1, ai1= ai ai ai+1 . . . . . . 91 根據(jù)該定理 ,要找句型的最左素短語就是要找滿足 上述條件的最左子串 . 注意 :出現(xiàn)在 aj左端和 a i右端的非終結符號一定屬于這個素短語 ,因為我們的運算是中綴形式給出的(OPG文法的特點 )NaNaNaN ?NaWaN 例 : 文法 G[E] E::=E+T|T T::=T*F|F F::=(E)|i 分析文法的句型 T+T*F+i 92 可以看出 : 1. 每次 規(guī)約 最左子串 ,確實是當前句型的 最左素短語(語法樹） 2. 規(guī)約的不都是真句柄（僅 i規(guī)約為 F是句柄，但它是最左短語 ) 3. 沒有完全按規(guī)則進行規(guī)約 ,因為 素短語不一定是簡單短語 步驟 句型 關系 最左子串 規(guī)約符號 1 2 3 4 T+T*F+i T+T+i E+i E+F +*+i ++i +i + T*F T+T i E+F T E E F . . . . . . . . . . . . . . 93 算符優(yōu)先分析法的實現(xiàn)： 詳見講義，基本部分是找句型的最左子串（最左素短語） 并進行規(guī)約。 分析程序 優(yōu)先關系矩陣 符號棧 輸入串 當棧內終結符的優(yōu)先級＜＝棧外的終結符的優(yōu)先級時，移進；棧內終結符的優(yōu)先級＞棧外的終結符的優(yōu)先級時，移進。表明找到了素短語的尾，再往前找其頭，并進行規(guī)約。 7 LR分析法 94 什么是 LR分析：從左到右掃描 (L)自底向上進行規(guī)約 (R) (是規(guī)范規(guī)約） 是自底向上分析方法的高度概括和集中 LR分析法的概述 LR分析法的概述 95 (1)LR分析法的優(yōu)缺點 (2)LR分析器有三部分 : 狀態(tài)棧、分析表、控制程序 (3)分析表的種類 (4)補充說明 (1) LR分析法的優(yōu)缺點 : 1) 適合文法類足夠大 ,適用于所有上下文無關文法 2) 分析效率高 3) 報錯及時 4) 可以自動生成 5) 手工實現(xiàn)工作量大 97 狀態(tài)棧：放置分析 器狀態(tài)和文法符號 . 分析表：由兩個矩陣組成，其功能是指示分析器的動作， 是 移進 還是 規(guī)約 ，根據(jù)不同的文法類要采用不同 的構造方法 . 控制程序：執(zhí)行分析表所規(guī)定的動作，對棧進行操作。 (2)LR分析器有三部分 : 狀態(tài)棧、分析表、控制程序 控制程序 分析表 狀態(tài)棧 輸入串 98 (3)分析表的種類 a) SLR分析表 (簡單 LR分析表 ) b) LR分析表 (規(guī)范 LR分析表 ) 構造簡單 ,最易實現(xiàn) ,大多數(shù)上下文無關文法都 可以構造出 SLR分析表 ,所以具有 較高的實用 價值。 使用 SLR分析表進行語法分析的分析器 叫 SLR分析器 適用文法類最大 ,n個所有上下文無關文法都能 構造出 LR分析表 ,但其分析表體積太大 .暫時實 用價值不大 . 99 c) LALR分析表 (超前 LR分析表 ) 這種表適用的文法類及其實現(xiàn)上 難易在上面 兩種之間 ,在實用上很吸引人 . 使用 LALR分析表進行語法分析的分析器叫 LALR分析器。 例： ANIXYACC 文法規(guī)則文件 YACC源文件 YACC 某語言的 LALR分析器 100 (4)幾點說明 SLR文法必定是 LALR文法和 LR文法 SLR分析表的構造方法 LR分析 （ 1）邏輯結構 （ 2） LR分析過程 102 （ 1）邏輯結構 分析動作表 狀態(tài)轉移表 控制程序 輸入串： a1 a2 ... ai ... an S0x1S1x2...... xmSm LR分析器 狀態(tài)棧 103 ☆ 狀態(tài)棧 : S0,S1,…,S m 狀態(tài) S0初始狀態(tài) Sm棧頂狀態(tài) 棧頂狀態(tài)概括了從分析開始到該狀態(tài)的 全部分析歷史和展望資料 . ☆ 符號串 : X1X2..... Xm 為從開始狀態(tài) (S0)到當前狀態(tài) (Sm)所識別的規(guī)范句型的活前綴 . S0x1S1x2...... xmSm S0S1...... Sm x1x2..... xm 104 規(guī)范句型： 通過規(guī)范規(guī)約得到的句型 . 規(guī)范句型前綴： 將輸入串的剩余部分與 其 連結起來就構成了規(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) 的活前綴。 105 S E E T ( ) E T i 106 ☆ 分析表 是一個矩陣： 行 分析器的狀態(tài) 列 文法符號 狀態(tài) 符號 E T F S0 S1 S2 : Sn GOTO表 a. 狀態(tài)轉移表 (GOTO表 ) 107 GOTO[Si1, xi]=Si Si1 當前狀態(tài) (棧頂狀態(tài) ) xi 新的棧頂符號 Si 新的棧頂狀態(tài) (狀態(tài)轉移 ) 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表 108 通過對有窮自動機的了解 ,我們可以看出 : 狀態(tài)轉移函數(shù) GOTO是定義了一個以文法符號集為字母表的有窮自動機，該自動機識別文法 所有 規(guī)范句型的活前綴 。 M=(S, B, GOTO, S0,