第5章自頂向下語法分析方法(編輯修改稿)
2024-10-07 09:09 本頁面
【文章內(nèi)容簡介】 LOW(B)= {} FOLLOW(C)= {} FOLLOW(D)= {} 編譯原理 SELECT集 S→AB S→bC A→ ε A→b B→ ε B→aD C→AD C→b D→aS D→c FIRST(S)={a,b,ε} FIRST(A)={b, ε} FIRST(B)={a, ε} FIRST(C)={a,b,c} FIRST(D)={a,c} FIRST(AB)={a,b,ε} FIRST(AD)={a,b,c} SELECT(S→AB)={a, b,ε,} SELECT(S→bC)={ b} SELECT(A→ ε)={a,c,ε} SELECT(A→ b)= SELECT(B→ ε)={,ε} SELECT(B→aD)={a} SELECT(C→AD)={a, b,c} SELECT(C→b)={ b} SELECT(D→aS)={a} SELECT(D→c)={c} FOLLOW(S)= {} FOLLOW(A)= {a,c,} FOLLOW(B)= {} FOLLOW(C)= {} FOLLOW(D)= {} 該文法不是 LL(1)文法。 編譯原理 某些非 LL(1)文法到 LL(1)文法的等價變換 提取左公共因子 消除左遞歸 編譯原理 提取左公共因子 A→ αβ|αγ導(dǎo)致 SELECT(A→ αβ)∩ SELECT(A→ αγ)≠Φ， 因此非 LL(1)文法。 等價變換為 A→ α(β|γ)， 然后： A→ αA39。 A39。 → β|γ A→ αβ1|αβ2|…|αβ n 變換為 A→ α(β1|β2|…|β n) ，然后： A→ αA39。 A39。 → β1|β2|…|β n 編譯原理 ? 例：文法 G1[S] 為 : S→aSb S→aS S→ ε 化為： S→aS(b| ε) S→ ε 進(jìn)一步化為： S→aS A A→b A→ ε S→ ε 結(jié)果仍然不是 LL(1)文法。 因此，文法中不含左公共因子只是 LL(1)文法的必要條件。 w=aabb S=aSA =aaSAA =aaAA =aabA (aaA) 編譯原理 ? 例：文法 G2為 : A→ad A→Bc B→aA B→bB ： A→ad A→ aAc A→ bBc B→aA B→bB ： A→ a(d|Ac) A→ bBc B→aA B→bB ： A→ aA39。 A→ bBc A39?！?d A39?！?Ac B→aA B→bB 結(jié)果是 LL(1)文法。 編譯原理 ? 例：文法 G3[S] 為 : S→aSd S→Ac A→aS A→b ： S→aSd S→aSc S→bc A→aS A→b ： S→aS(d|c) S→bc A→aS A→b ： S→aS A39。 S→bc A39?！?d A39?！?c A→aS A→b 結(jié)果中 A是不可達(dá)到的符號。 編譯原理 ? 例：文法 G4[S] 為 : S→Ap|Bq A→aAp|d B→aBq|e ： S→ aApp|aBqq|dq|eq A→aAp|d B→aBq|e ： S→a(App|Bqq) S→dq|eq A→aAp|d B→aBq|e ： S→aS39。 S→dq|eq S39?！鶤pp|Bqq A→aAp|d B→aBq|e ： S→aS39。 S→dq|eq S39?！?aAppp|aBqqq|dpp|eqq A→aAp|d B→aBq|e 利用提取左公共因子 無法在有限步驟內(nèi) 替換成無左公共因子的文法。 編譯原理 結(jié)論 不一定每個文法的左公共因子都能在有限的步驟內(nèi)替換成無左公共因子的文法。 一個文法提取了左公共因子后，只解決了相同左部產(chǎn)生式右部的 FIRST集不相交問題，當(dāng)改寫后的文法不含空產(chǎn)生式，且無左遞歸時，則改寫后的文法是 LL(1)文法，否則還需用 LL(1)文法的判別方式進(jìn)行判斷才能確定是否為 LL(1)文法。 編譯原理 消除左遞歸 直接左遞歸： A→A β A?VN, β ?V* 間接左遞歸： A→B β B→A α A,B?VN, α,β ?V* 編譯原理 文法 G5含有直
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1