【正文】 認為 : 對句型 xuY 而言 若有 A→u ，即 A?u 就斷定 u是簡單短語， u 就是句柄， 而是要同時滿足 S? xAY * 簡單優(yōu)先分析 例 : G[S] S→bAb A→(B | a B →Aa) (1) 先確定符號之間的優(yōu)先關(guān)系 優(yōu)先關(guān)系的定義 : 設(shè) X, Y 為可能相鄰的符號 定義 : X = Y X的優(yōu)先級等于 Y X Y X的優(yōu)先級小于 Y X Y X的優(yōu)先級大于 Y . . . 1) X=Y if文法中有形如 A→ XY 2) XY if 文法中有形如 A→ XB 的規(guī)則，其中 B? Y 。 168。168。168。 + . . . + * + 例 : G[S] S→bAb b=A, A=b ,b(,ba,)b,ab,Bb A→(B | a (=B, (A, ((,(a B →Aa) A=a,a=),Ba,aa,)a S→bAb b=A, A=b ,b(,ba,)b,ab,Bb A→(B | a (=B, (A, ((,(a B →Aa) A=a,a=),Ba,aa,)a S b A ( B a ) S b = A = = ( = B a = ) = 算符優(yōu)先分析 (OperatorPrecedence Parsing) 13 1) 這是一種 經(jīng)典 的自底向上分析法，簡單直觀，并被廣泛使 用。 2) 稱為算符優(yōu)先分析是因為這種方法是 仿效 算術(shù)式的四則運算 而建立起來的，作算術(shù)式的四則運算時，為了保證 計算結(jié)果 和過程的 唯一性 ，規(guī)定了一個統(tǒng)一的 四則運算法則 ，規(guī)定運 算符之間的 優(yōu)先關(guān)系 。 如： i+i*i (1) 先確定終結(jié)符之間的優(yōu)先關(guān)系 優(yōu)先關(guān)系的定義 : 設(shè) a, b 為可能相鄰的終結(jié)符 定義 : a = b a的優(yōu)先級等于 b a b a的優(yōu)先級小于 b a b a的優(yōu)先級大于 b . . . 15 2)例中文法終結(jié)符之間的優(yōu)先關(guān)系可以用一個矩陣 M來表示 ) = ( i * + ) ( i * + b(右棧外 ) a(右棧內(nèi) ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3)矩陣元素空白處表示這兩個終結(jié)符不能相鄰 ,故沒有優(yōu)先關(guān)系 16 步驟 符號棧 輸入串 優(yōu)先關(guān)系 動作 1 2 3 4 5 6 7 8 9 10 11 i E E+ E+i E+E E+E* E+E*i E+E*E E+E E i *i *i i*i +i*i +i*i i+i*i i i+ + +i i* +* *i i * + 移進 移進 移進 移進 移進 規(guī)約 規(guī)約 規(guī)約 規(guī)約 規(guī)約 接受 ) = ( i * + ) ( i * + b a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E→E+E | E*E | (E) | i 算法 : 當棧頂項 (或次棧頂項 )終結(jié)符 的優(yōu)先級大于棧外的 終結(jié)符 的優(yōu)先級則進行規(guī)約，否則移進 . (2) 分析過程 i+i*i 算符優(yōu)先文法的定義 17 (1)算符優(yōu)先文法 (OPG) (2)構(gòu)造優(yōu)先關(guān)系矩陣 (3)算符優(yōu)先分析算法的設(shè)計 18 （ 1）算符優(yōu)先文法（ OPG） 算符文法（ OG）的定義 優(yōu)先關(guān)系的定義 若文法中無形如 A→ BC 的規(guī)則，這里B,C∈ VN 則稱 G為 OG文法，也就是 算符文法 。 168。168。 168。168。 2) ab if 文法中有形如 A→ aB 的規(guī)則，其中 B? b 或 B? Bb 。 168。168。168。168。 + + . . . + + + 算符優(yōu)先文法（ OPG）的定義 設(shè)有一 OG文法，如果在任意兩個終結(jié)符之間，至多只有 上述關(guān)系中的一種，則稱該文法為算符優(yōu)先文法 (OPG) 21 對于 OG算法的幾點說明 : 1) 運算是以中綴形式出現(xiàn)的 3) 算法語言中的表達式以及大部分語言成分的文法均是 OG文法 2) 可以證明，若文法為 OG文法，則不會出現(xiàn)兩個非終結(jié)符相鄰的句型。 /* 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) 設(shè)一個棧 ST,和一個布爾數(shù)組 B PROCEDARE INSERT(A,a) IF NOT B[A,a] THEN BEGIN B[A,a]::=TRAE。 END。 FOR 每個形如 A::=…a 或 A::=…aB 的規(guī)則 DO INSERT (A,a)。 FOR 每條形如 A::=…B 的規(guī)則 DO INSERT(A,a)。 END。 分析程序 優(yōu)先關(guān)系矩陣 符號棧 輸入串 當棧內(nèi)終結(jié)符的優(yōu)先級＜＝棧外的終結(jié)符的優(yōu)先級時，移進；棧內(nèi)終結(jié)符的優(yōu)先級＞棧外的終結(jié)符的優(yōu)先級時，移進。 優(yōu)先函數(shù) 為了節(jié)約存儲空間和便于執(zhí)行比較運算 ?，用兩個優(yōu)先函數(shù) f和 g，它們是從終結(jié)符號映射到整數(shù)的函數(shù)。 2 .當 a＜ 3. 當 a 于是 a和 b之間的優(yōu)先關(guān)系可以由比較 f(a)與g(b)的大小來決定。 a = b, 從 fa至 gb畫一條弧；也從 gb至 fa畫 一條弧 ， b ∈ VT， 若 ab ，則從 gb至 fa畫一條弧 。 id + * f 6 6 4 2 g 7 5 3 2 41 注意特點 : (a) 優(yōu)先函數(shù)值不唯一 (b) 優(yōu)點： ? 節(jié)省內(nèi)存空間 ? 若文法有 n個終結(jié)符，則關(guān)系矩陣為 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) 適合文法類足夠大 ,適用于所有上下文無關(guān)文法 2) 分析效率高 3) 報錯及時 4) 可以自動生成 5) 手工實現(xiàn)工作量大 45 狀態(tài)棧：放置分析 器狀態(tài)和文法符號 . 分析表：由兩個矩陣組成，其功能是指示分析器的動作， 是 移進 還是 規(guī)約 ，根據(jù)不同的文法類要采用不同 的構(gòu)造方法 . 控制程序：執(zhí)行分析表所規(guī)定的動作，對棧進行操作。 使用 SLR分析表進行語法分析的分析器 叫 SLR分析器 適用文法類最大 ,n個所有上下文無關(guān)文法都能 構(gòu)造出 LR分析表 ,但其分析表體積太大 .暫時實 用價值不大 . 47 c) LALR分析表 (超前 LR分析表 ) 這種表適用的文法類及其實現(xiàn)上 難易在上面 兩種之間 ,在實用上很吸引人 . 使用 LALR分析表進行語法分析的分析器叫 LALR分析器。 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 通過對有窮自動機的了解 ,我們可以看出 : 狀