【正文】 (A)。 ① 從 sj（棧頂符）開始，往棧內查找，找到第一個使 si1si的 si（句柄的頭） ② 用 sisi+1… sj去查文法產(chǎn)生式，若有 A?sisi+1… sj，則： Xk：棧頂 符 ； 歸約 移進 簡單優(yōu)先控制器 y ? y n ※ 只考慮算符（終結符）之間的優(yōu)先關系 （ 1）算符文法 設有一文法 G，如果 G中沒有形如 A?… QR…的產(chǎn)生式，其中 Q和 R為非終結符，則稱該文法為算符文法（ OG文法）。 算符優(yōu)先分析 (2)頭符號集合和尾符號集合 設 a∈V T， P,R∈V N， 則 : FIRSTVT(P)={a| P a…… 或 P Ra…… }, = + LASTVT(P) ={a| P …… a 或 P …… aR}。 = + = + = + 設 a,b∈V T， P,Q,R∈V N， ① a b ， 當且僅當有 P?… ab… 或 P?… aQb… ； (3) 算符優(yōu)先關系定義 ② ab ， 當且僅當有 P?… aR… ，且 R b… 或 R Qb… ； = + ③ ab ， 當且僅當有 P?… Rb… ，且 R … a 或 R … aQ； = + (4)算符優(yōu)先文法 如果算符文法 G中的任何一對終結符 a和 b之間，僅滿足上述一種關系，則 G就是一個算符優(yōu)先文法（ OPG）。 = + = + 語法分析方法綜合示例 G(Z)： Z dAZ | bAc A aA | c |ε 【 例 】 給定文法如下： Ⅰ. 遞歸子程序法； Ⅱ. LL(1) 分析法； ※ 試分別用下述分析法，對給定的 符號串 進行語法分析： Ⅲ. LR(0)( 或 SLR（ 1） )分析法； 設 給定的符號串為： α = bac ∵ Z = bAc = baAc = ba ε c = bac ∴ bac 是文法 G(Z) 的一個句子。 注 G(Z)： ZdAZ① | bAc② AaA③ | e④ |ε ⑤ Ⅰ. 構造遞歸子程序法： ⒈ 證明 G(Z)是 LL(1)文法： select(① )= first(dAZ)={ d } ※ 求選擇集合： select(② )= first(bAc)={ b } select(③ )= first(aA)={ a } select(④ )= first(c) ={ e } select(⑤ )= follow(A)= { d ,b ， c } ? ? ∵ 兩組選擇集合 ? , ? 皆不相交， ∴ G（ Z）是 LL(1) 文法！ 即 遞歸子程序法可用！！ Z子程序 主程序 ⒉ 構造遞歸子程序 (框圖 )： G(Z)： ZdAZ① | bAc② AaA③ | e④ |ε ⑤ 入口 a NEXT(w) 出口 遇?時 n y A A子程序 e NEXT(w) y n NEXT(w) 結束 n y Z 開始 err0 入口 出口 d err3 NEXT(w) A n n y Z A c NEXT(w) y b err2 n y NEXT(w) ⒊ 分析過程示意 ： 入口 a NEXT(w) 出口 遇?時 n y A A子程序 e NEXT(w) y n 主程序 NEXT(w) 結束 n y Z 開始 err0 bac 設 待分析的符號串： 入口 出口 d err3 NEXT(w) A Z子程序 n n y Z A c NEXT(w) y b err2 n y NEXT(w) b b a a c c c c ▼ ■ G(Z)： ZdAZ① | bAc② AaA③ | e④ |ε ⑤ Ⅱ . LL(1)分析法： ⒈ 證明 G(Z)是 LL(1)文法： select(① )= first(dAZ)={ d } ※ 求選擇集合： select(② )= first(bAc)={ b } select(③ )= first(aA)={ a } select(④ )= first(c) ={ e } select(⑤ )= follow(A)= { d ,b ， c } ? ? ∵ 兩組選擇集合 ? , ? 皆不相交， ∴ G（ Z）是 LL(1) 文法！ 即 遞歸子程序法可用??！ 2. 構造 LL(1)分析表： LL(1) 分析表： G(Z)： ZdAZ{ d }① | bAc{ b }② AaA{ a }③ | e{ e }④ |ε {b,c,d}⑤ ※ 帶有 選擇集合 的文法： d A Z e c b a ⑤ ① ④ ⑤ ⑤ ③ ② 棧 當前符號 剩余序列 棧操作 逆序壓棧 c A c c A c c A b A a b a c pop,push(cAb) b a c pop,next a c pop,push(Aa) a c pop,next c c Z ※ 對符號串： ? = bac 的分析過程： ⒊ 分析過程示意 ： G(Z)： ZdAZ{ d }① | bAc{ b }② AaA{ a }③ | e{ e }④ |ε {b,c,d}⑤ d A Z e c b a ⑤ ① ④ ⑤ ⑤ ③ ② pop,push(?) pop,next 正確結束 查分析表 Ⅲ . LR(0)(SLR(1))分析法： ⒈ 擴展 文法，編碼： G(Z)： Z` Z1 0 Z d2A3Z4 ① | b5A6c7 ② A a8A9 ③ | e10 ④ |ε 11 ⑤ ⒉ 直接構造 SLR(1)分析表： 9 10 Z 1 5 0 4 8 d e 6 7 3 2 A c b a r(3) r(3) r(3) r(3) r(3) r(3) r(4) r(4) r(4) r(4) r(4) r(4) r(2) r? A3 Z1 OK A6 d2 b5 r? r? r? r? A9 e10 a8 r(2) d2 r(5) r(2) e10 c7 r(2) r(2) r(2) Z4 b5 r(5) a8 r(5) r? a8 e10 r(5) r(5) r(5) r(5) r(5) r(5) Follow(A)={ b,c,d } ⒊ 分析過程示意 ： 剩余串 操 作 w 分析棧 ※ 符號串： bac 0 b5 A6 REDUCE(2) 0 b5 A6 OK 0 c ac RUDUCE(5) c 0 b5 PUSH(b5),NEXT(w) b 0 PUSH(c7),NEXT(w) c REDUCE(3) c 0 b5 a8 PUSH(a8),NEXT(w) a 0 b5 a8 c7 Z1 A9 LR()分析表 例 【 】 G(E): E E + T | T T ( E ) | i E` E1 (0) E E2 +3 T4 (1)| T5(2) T (6 E7 )8(3)| i9(4) G`(E`) 1. 構造句柄識別器： T i 0 E ① OK E ② + ③ T ④ r(1) T ⑤ r(2) ( ⑥ E ⑦ ) ⑧ r(3) i ⑨ r(4) E ( ( i 【 解 】 + r(4) r(4) r(4) r(4) r(4) r(3) r(3) r(3) r(3) r(3) )8 +3 T5 (6 i9 r(2) r(2) r(2) r(2) r(2) r(1) r(1) r(1) T4 (6 i9 T5 E1 (6 i9 OK +3 r(1) r(1) ,2 【 習題 】 G(E): E E + T | T T ( E ) | i T E ) ( + i E` E1 (0) E E2 +3 T4 (1)| T5(2) T (6 E7 )8(3)| i9(4) G`(E`) 令 {1,2},{2,7} 分別用 2， 7 代之； ∴ 是 SLR(1)分析表！ 有限自動機確定化 方法，直接構造 SLR(1) 分析表： 0 E 7 9 8 2,7 6 5 4 3 1,2 注 2. T E ) ( + i 3. 用SLR(1) 分析表，構造 確定的有限自動機 ： E2,7 T5 T4 T5 E1,2 r(3) r(3) r(4) r(2) OK r(1) r(4) r(3) )8 r(2) r(1) r(4) r(3) (6 r(2) r(1) (6 (6 r(4) +3 r(2) r(1) +3 r(4) r(3) i9 r(2) r(1) i9 i9 0 9 8 2,7 6 5 4 3 1,2 0 OK E ② + ③ T ④ r(1) T ⑤ r(2) ( ⑥ E ⑦ ) ⑧ r(3) i ⑨ r(4) + ( ( i ＃ T i {1,2},{2,7}分別用 2， 7代之 構造項目集合的 方法，構造 可規(guī)約前綴圖 ： E’E EE+T ET T(E) Ti E E’E EE+T EE+T T(E) Ti + EE+T T OK r(1) I0 T ET r(2) I1 I2 I3 I4 T(E) EE+T ET T(E) Ti ( I5 T(E) EE+T E I6 ) T(E) I7 r(3) i Ti I8 r(3) T ( i + ( i … E … E+ … E+T … T … ( … (E … (E) … i 文法 a * ( b + c ) F T T E F F T E T F E a b c + ( )*