【正文】 替換： A→Aα|β 為： A →βA39?！罙39。F T 39。i d ε F T 39。i d ε 1 消除文法的直接左遞歸 (續(xù) 2) 輸入序列： id+id*id 改寫的代價 E→E+T|T T→T*F|F F→(E)| F|id () E →TE39?！?TE39。 (3) T39。|ε (4) F →(E) | F|id (5)..(7) (39。 end loop。 消除 Ai產生式中的直接左遞歸 。 方法 將非終結符合理排序 ： A1， A2， ...， An。 核心思想： 將不是直接左遞歸的符號用其右部展開到其他產生式 關鍵步驟： 合理排序非終結符 ： A1， A2， ...， An。 消除 Ai產生式中的直接左遞歸 。 | A39。) A39。 | adA39。 ? 這一過程被稱為提取左因子，它類似于有限自動機的 確定化 。 A39。 方法 重復下述過程 ， 直到所有 A產生式候選項中不再有公共前綴 例 考察懸空 else文法 ： S→iCtS|iCtSeS|a C→b 用算法 ，得到如下文法： 既有左遞歸又含左因子？ 先消除左遞歸。|a S39。|γ 和 A39。 ■ 14 遞歸下降分析 1. 直接以程序的方式模擬產生式產生語言的過程； 2. 每個產生式對應一個子程序 ， 產生式右邊的非終結符對應子程序調用 ， 終結符則與輸入序列匹配； 3. 它對文法的限制是不能有公共左因子和左遞歸； 4. 它是一種非形式化的方法 ， 只要能寫出子程序 ， 用什么樣的方法和步驟均可 。L|ε E→E+T|E T|T T→T*F|T/F|T mod F|F F→(E)|id|num 消除左遞歸后的等價文法 : L →E 。 E39。| TE39。 T39。|/FT39。|ε F →(E)|id|num 1 構造狀態(tài)轉換圖且化簡 1. 構造文法的狀態(tài)轉換圖并且化簡； 2. 將轉換圖轉化為 EBNF表示； 3. 從 EBNF構造子程序。 3. 根據識別同一集合的原則，化簡轉換圖。L|ε E →TE39?！?TE39。|ε T →FT39?！?FT39。 |mod FT39。 Lε4 65E :T E 39。 :+ T E 39。ε1 3 1 51 4T :F T 39。 :* F T 39。ε2 32 2m o d F T 39。 化簡 E產生式： 1. 合并路徑： 2. 轉向 E39。的轉換圖代入 E ： ε 連接的節(jié)點： ： 4 65E :T E 39。 :+ T E 39。ε1 0987E 39。ε1 0987E 39。:+, T81 0E :T ε + , T4 581 0E :T + , T41 0E :T 4+ , 18 狀態(tài)圖的化簡（續(xù) 1） 最終全部化簡的轉換圖： 2 文法的擴展 BNF（ EBNF） 表示 ① { }： 重復 0或若干次 （ while） ② [ ]： 可選擇 （ if或 while） ③ |： 括弧 ( )之內的或關系 （ case） ④ ( )： 改變運算的優(yōu)先級和結合性 EBNF表示 ： （ F無需化簡，為什么？） L → { E。3E:T 2+,9876F :( E )i dn u m5T:F4*,/,mode0 321L :E 。 } E → T { (+| ) T } T → F { (*|/|mod) F } F → ( E ) | id | num procedure L is begin lookahead := lexan； while (lookahead/=eof)loop E。39。 end loop。 procedure E is begin T。 T。 end E。(39。(39。 E。)39。 id : match(id)。 others : error(syntax error2)。 end F。 match(39。)。 end E。 include const int id=0。 void E() { cout match E endl。 match(39。)。 cout match + and id endl。} 同樣，文法中的公共左因子也會給遞歸下降分析造成困難。 A39。|ε ） ? 消除直接左遞歸（ 算法 ）和消除左遞歸（ 算法 ） 5. 提取左因子：合并公共前綴（ 算法 ） 6. 遞歸下降分析（一個非終結符是一個子程序） ? 構造文法的狀態(tài)轉換圖并且化簡； ? 將轉換圖轉化為 EBNF表示； ? 從 EBNF構造子程序。L|ε E →TE39?！?TE39。|ε T →FT39?！?FT39。|mod FT39。 L E。L E。 TE39。 E39。 TE39。 FT39。 T39。 /FT39。 ε ε F id num (E) 文法： L→E 。 構造 分析表 (M[A, a])： 24 2 工作方式 放幻燈的方式： 1. 每張 “ 幻燈片 ” 稱為一個 格局 。 格局： 格局是一個三元組 （ 棧內容 ， 當前剩余輸入 ， 改變格局的動作 ） ^top ^ip 改變格局的動作： ① 匹配終結符： 若 ^top=^ip(但 ≠ )， 則 pop且 next(ip)； ② 展開非終結符： 若 ^top= X且 M[X, a]=α(X→α) ， 則 pop且 push(α) ； ③ 報告分析成功： 若 ^top=^ip=， 則分析成功并結束 ； ④ 報告出錯： 其它情況，調用錯誤恢復例程。 loop x := top^。 exit when x=。 ■ if x ∈ T then if x=a then pop(x)。 匹配終結符 else error(1)。 else if M[x, a] = X→Y 1Y2...Yk then pop(X)。展開產生式 else error(2)。 end if。 a := ip^。 next(ip)。 出錯：棧頂終結符不是 a end if。 push(YkYk1...Y2Y1)。 出錯：