【正文】 jaj…N iaiNi+1ai+1 其中 aj1aj aj=aj+1, aj+1= aj+2 ,…, a i2= ai1, ai1= ai ai ai+1 . . . . . . 35 根據(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 36 可以看出 : 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 . . . . . . . . . . . . . . 37 算符優(yōu)先分析法的實現(xiàn)： 詳見講義，基本部分是找句型的最左子串（最左素短語） 并進行規(guī)約。 END OF WHILE。 WHILE ST棧非空 DO BEGIN 把 ST棧的棧頂彈出 ,記為 (B,a)。 30 BEGIN FOR 每個非終結符號 A和終結符號 a DO B[A,a]:=FALSE。把 (A,a)推進 ST棧 。 22 （ 2）構造優(yōu)先關系矩陣 FIRSTVT( B )={b|B?b… 或 B?Cb…,b ∈ Vt, B∈ Vn} + + LASTVT( B )={a|B?…a 或 B?…aC,a ∈ Vt, B∈ Vn} + + ?求 “ = ” 檢查每一條規(guī)則，若有 A::=… ab… 或 A::=… aBb…, 則 a=b . . ?求“ ”、“ ”復雜一些，需定義兩個集合 . . 23 ?求“ ”、“ ”: . . 若文法有規(guī)則 A→...aB... ，對任何 b, b∈ FIRSTVT(B) 則有： a b . 若文法有規(guī)則 A→...Bb... ，對任何 a, a∈ LASTVT(B) 則有： a b . 例 : 文法 G[E] E::=E+T|T T::=T*F|F F::=(E)|i 求每個非終結符號的 FIRSTVT及 LASTVT FIRSTVT LASTVT E {+,*,(,i} {+.*,),i} T {*,(,i } {*,),i} F {(,i} {),i} 求 =關系： (=) 求 關系： +FIRSTVT(T),*FITSTVT(F),(FIRSTVT(E) 求 關系：LASTVT(E)+,LASTVT(T)*,LASTVT(E)) ) = ( i * + ) ( i * + b(右棧外 ) a(右棧內(nèi) ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 構造優(yōu)先關系表： 26 構造 FIRSTBT(A)的算法 1)若有規(guī)則 A→b… 或 A→Bb…( 存在 A?b… 或 A?Bb…) 則 b∈ FIRSTVT(A) + + 2)若有規(guī)則 A→B… 且 b∈ FIRSTVT(B), 則 b∈ FIRSTVT(A) 說明 :因為 B?b… 或 B?Cb…, 所以有 A?B… ?b… 或 A?B… ?Cb… + + + + 27 設一個棧 S和一個二維布爾數(shù)組 F F[A,b]=TRAE iff b∈ FIRSTVT(A) PROCEDBRE INSERT(A,b) IF NOT F[A,b] THEN BEGIN F[A,b]:=TRAE 把 (A,b)推進 S棧 /* b∈ FIRSTVT(A) */ END BEGIN {main} FOR 每個非終結符號 A和終結符 b DO F[A,b]:=FALSE /*賦值符 */ FOR 每個形如 A::=b… 或 A::=Bb… 的規(guī)則 DO INSERT(A,b) 具體方法如下 : 28 WHILE S棧非空 DO BEIGN 把 S棧的頂項彈出 ,記為 (B,b)/* b∈ FIRSTVT(A)*/ FOR 每條形如 A::=B… 的規(guī)則 DO INSTER(A,b)。 aC 。 a或 B? 的規(guī)則 , 其中 B? Bb 3) ab if 文法中有形如 A→168。168。168。 168。 的規(guī)則。 aBb 或 A→ ab 若 G是一 OG文法， a,b∈ VT, A,B,C∈ VN 分別有以下三種情況 : G中不含 ε的產(chǎn)生式 19 1) a=b if文法中有形如 A→168。 168。 直觀算符優(yōu)先文法 14 例 : G[E] E→E+E | E*E | (E) | i Vt={+, *, (, ), i} 這是一個二義文法，要用算符優(yōu)先法分析有該文法所確定的 語言句子。 運算法則 : 的優(yōu)先大于 加減 左 大于 右 內(nèi) 的優(yōu)先級大于括號 外 于是： 4+86/2*3 運算過程和結果唯一。 X或 D?Y 。 的規(guī)則 , 其中 B? BD 3) XY if 文法中有形如 A→168。168。 168。168。 168。 舉例的分析過程可以說是一種巧合。 分析過程如下表 : 7 步驟 符號棧 輸入符號串 動作 1 2 3 4 5 6 7 8 9 10 11 12 a ab aAb aA aAc aAcd aAcB aAcBe S S aA abbcde bbcde bcde bcde cde cde de e e 準備 .初始化 移進 移進 規(guī)約 (A→b ) 移進 規(guī)約 (A→Ab ) 移進 移進 規(guī)約 (B→d ) 移進 規(guī)約 (S→aAcBe ) 成功 例： G[S]: S→aAcBe A→b A→Ab B→d 8 這一方法簡單明了 ,不斷地進行移進規(guī)約 , 關鍵是確定當前句型的 句柄 . 說明 :(1)例子的分析過程是一步步地規(guī)約當前句型的句柄 該句子的唯一語法樹為 : a A c B e A b b d S 注意兩點： （ a）棧內(nèi)符號串 + 未處理輸入符號串 = 當前句型 （ b）句柄都在棧頂 實際上，以上分析過程并未真正解決句柄的識別問題 9 (2)未真正解決句柄的識別 . 上述分析過程的怎樣 識別句柄 的，主要看棧頂符號串 是否形成規(guī)則的右部。先設立一個符號棧，我們統(tǒng)一符號“ ”作為待分析的符號串的左右分界符。 符號棧 輸入串 6 例： G[S]: S→aAcBe A→b A→Ab B→d 輸入串為 abbcde，檢查是否是該文法的合法句子。分析一直進行到讀到輸入串的右界符為止。 移進 — 規(guī)約分析（ Shiftreduce parsing) 4 符號棧 輸入串 要點 ：建立符號棧，用來紀錄分析的歷史和現(xiàn)狀，并根據(jù)所面臨的狀態(tài)，確定下一步動作是 移進 還是 規(guī)約 。6 自底向上分析 1 移進 歸約分析 (自底向上分析的一般過程 ) 算符優(yōu)先分析法 自底向上分析 2 若采用自左向右的描述和分析輸入串 ,那么自 底向上的基本算法是： 從輸入符號串開始，通過重復查找當前句型的 句柄 (最左簡單短語 )，并利用有關規(guī)則進行規(guī)約， 若能規(guī)約為文法的識別符號，則表示分析成功，輸 入符號串是文法的合法句子，否則有語法錯誤。 基本算法思想 : 3 分析過程是重復一下步驟： 找出當前句型的句柄 x （或句柄的變形） 找出以 x 為右部的規(guī)則 X::= x 把 x 規(guī)約為 X， 產(chǎn)生語法樹的一枝 關鍵 ：找出當前句型的句柄 x (或其變形），這不是很容易 。 5 分析過程：把輸入符號串按描述順序一一地移進符號棧（一次移一個），檢查棧中符號，當在棧頂?shù)娜舾煞栃纬僧斍熬湫偷木浔鷷r，就根據(jù)規(guī)則進行規(guī)約，將句柄從符號棧中彈出，并將相應的非終結符號壓入棧內(nèi)（即規(guī)則的左部符號），然后再檢查棧內(nèi)符號串是否形成新的句柄，若有就再進行規(guī)約，否則移進符號。最后，若棧中僅含有左界符號和識別符號，則表示分析成功，否則失敗。 若采用自底向上分析，即能否一步步規(guī)約 當前句型的句柄 ，最終 規(guī)約到 識別符號 S。 作為初始狀態(tài)，先將符號串的分界符推進符號棧，作為棧底符號。 這種做法形式上是正確的，但在實際上不一定正確。 因為不能