【正文】 if x ∈ T then if x=a then pop(x)。 26 loop x := top^。 出錯：產(chǎn)生式不匹配 end if。 push(YkYk1...Y2Y1)。 出錯：棧頂終結(jié)符不是 a end if。 next(ip)。 分析成功 end loop。 a := ip^。 驅(qū) 動 器輸 入 記 號 流符號棧輸 出t o pi p( b ) 預(yù) 測 分 析 器 模 型預(yù) 測 分 析 表25 3 驅(qū)動器算法 算法 非遞歸的預(yù)測分析 輸入 輸入序列 ω 和文法 G的預(yù)測分析表 M 輸出 若 ω∈L(G) ， 得到 ω 的一個最左推導(dǎo)；否則指出一個錯誤 方法 初始格局為 : （ S， ω ， 分析器的第一個動作 ） 令 ip指向 ω 中的第一個終結(jié)符 ， top指向 S。 2. 分析從某個 初始格局 開始，經(jīng)過一系列的 格局變化 ，最終到達(dá) 接收格局 ，表明分析成功； 3. 或者到達(dá) 出錯格局 ，表明發(fā)現(xiàn)一個語法錯誤。L|ε E→E+T|E T|T T→T*F|T/F|T mod F|F F→(E)|id|num M[A, a]的內(nèi)容： 若當(dāng)前棧頂是非終結(jié)符 A，下一輸入終結(jié)符是 a，則 M[A, a]指示下一步動作。 mod FT39。 ε ε *FT39。 FT39。 ε ε T FT39。 +TE39。 TE39。L ε E TE39。L E。|ε F →(E)|id|num id num + * / mod ( ) 。|/FT39。 T39。| TE39。 E39。 22 預(yù)測分析器 非遞歸預(yù)測分析器的工作模式 預(yù)測分析器的核心概念： 1. 分析方法：格局與格局變換 2. 分析表 +驅(qū)動器（模擬算法） 3. 預(yù)測分析表的構(gòu)造 4. LL（文法、語言、分析器） 驅(qū) 動 器輸 入 記 號 流符號棧輸 出t o pi p( b ) 預(yù) 測 分 析 器 模 型預(yù) 測 分 析 表輸 入 記 號 流有 限 狀 態(tài)轉(zhuǎn) 移 控 制下推棧輸 出t o pi p( a ) 下 推 自 動 機(jī) 模 型23 1 預(yù)測分析表 L →E ?！罙39。 結(jié)束 （ 2022年 4月 3日 ） 21 上次課程內(nèi)容回顧 1. 形式語言與自動機(jī)簡介 2. 自上而下分析的一般方法：自上而下 (用推導(dǎo)的方法建立分析樹 )、從左到右 (掃描輸入序列 )； 3. 自上而下分析對文法的限制：不能有左遞歸和左因子 4. 消除左遞歸： ? 左遞歸與直接左遞歸（ 定義 ） ? 基本公式（替換 A→Aα|β 為 A →βA39。 // 永遠(yuǎn)不執(zhí)行 } void main(){ E()。 match(id)。+39。 E()。 void match(int x){}。 此程序永不停機(jī) 。 match(id)。+39。 20 3 遞歸下降子程序（續(xù)） 再看左遞歸問題： 若存在產(chǎn)生式 E → E + id， 則 E的遞歸下降子程序如下： procedure E is begin E。 end case。 num : match(num)。)。 match(39。)。 : match(39。 procedure F is begin case lookahead is 39。 end loop。 while lookahead∈(+| ) loop match(lookahead)。 end L。)。 match(39。 Lε19 3 遞歸下降子程序 L → { E。 } E → T { (+| ) T } T → F { (*|/|mod) F } F → ( E ) | id | num 1L:E0。 :+ , T εε810E39。 :+ , T E 39。 T E 39。1 09871 21 1E 39。的初態(tài)： 3. 合并 ε 連接的節(jié)點(diǎn)： 4. 將 E39。2 72 62 52 4F :( E )i dn u m17 狀態(tài)圖的化簡： 1. 標(biāo)記為 A的邊可等價為標(biāo)記 ε 的邊轉(zhuǎn)向 A轉(zhuǎn)換圖的初態(tài)； 2. ε 邊連接的兩個狀態(tài)可以合并； 3. 標(biāo)記相同的路徑可以合并； 4. 不可區(qū)分的狀態(tài)可以合并。/ F T 39。1 91 81 71 62 12 0T 39。 T E 39。1 09871 21 1E 39。|ε F →(E)|id|num 文法狀態(tài)轉(zhuǎn)換圖： 0 321L :E 。|/FT39。 T39。| TE39。 E39。 L →E 。 16 文法的狀態(tài)轉(zhuǎn)換圖 ： 每個非終結(jié)符對應(yīng)一個狀態(tài)轉(zhuǎn)換圖： 1. 為非終結(jié)符 A建立一個初態(tài)和一個終態(tài)； 2. 為 A→X 1X2...Xn構(gòu)造從初態(tài)到終態(tài)的路徑 ，邊標(biāo)記為 X1， X2， ...， Xn。| mod FT39?！?FT39。|ε T →FT39?！?TE39。L|ε E →TE39。 15 穩(wěn)妥的笨方法： 遞歸下降分析的文法： L→E ?！?|β2| ...|βn 取代原 A產(chǎn)生式?！鷈S|ε C→b 重排 A產(chǎn)生式 ： A→αβ1|αβ2| ... |αβn|γ ； 并用 A→αA39。 （為什么？） S→iCtSS39?！?1|β 2 它等價于： A →α(β 1|β 2 ) （對照算術(shù)表達(dá)式中的提取公因式） S → cAd A → ab | a 13 提取左因子（續(xù) 1） 算法 提取文法的左因子 輸入 文法 G 輸出 等價的無左因子文法 G39。 公共前綴： A → α β 1|α β 2 將： A → αβ 1|αβ 2 替換為： A →αA39。 | ε 12 提取左因子 ? 當(dāng) 不確定 用 A產(chǎn)生式的哪個候選項(xiàng)替換 A時，可以重寫 A 產(chǎn)生式來推遲這種決定，直到看見足夠的輸入，能正確決定所需選擇為止?！?cA39。 (39。 ① 將 S的右部展開在 A中 ， 得到： A→Ac|Aad|bd|ε ② 消除新產(chǎn)生式中的直接左遞歸 ， 得到： S→ Aa | b A→ bdA39。 用 Aj→ δ1|δ2|...|δk 右部替換 Ai→ Ajγ 中的 Aj 得到 Ai→δ1γ|δ2γ|...|δkγ 。 11 2 消除文法的左遞歸（續(xù) 1） 例 用算法 S→Aa|b A→Ac|Sd|ε 中的左遞歸。 算法 消除左遞歸 輸入 無回路文法 G 輸出 無左遞歸的等價文法 G39。 ■