自頂向下語法分析方法(編輯修改稿)
2025-02-14 21:28 本頁面
【文章內(nèi)容簡介】 = SELECT(D→aS)={a} SELECT(D→c)={c} 5. 判別是否是 LL(1)文法 所以文法 G[S] 不是 LL(1)文法。 某些非 LL(1)文法到 LL(1)文法的等價變換 ? 提取左公共因子 ? 消除左遞歸 1. 提取左公共因子 ? 例 文法 G1[S] : S→aSb S→aS S→ε 化為： S→ aS(b|ε) S→ ε 進一步化為： S→ aSA A→ b A→ ε S→ ε 結(jié)果仍然不是 LL(1)文法。因此，文法中不含左公共因子只是 LL(1)文法的必要條件。 A→αβ 1|αβ2|…|αβ n 變換為 A→α(β 1|β2|…|β n) ，即 A→αA39。 A39。 → β 1|β2|…|β n ? 例 文法 G2[A]: 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?！鷇 A39?！鶤c B→aA B→bB ? 例 文法 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→aSA39。 S→bc A39?！鷇 A39?！鷆 A→aS A→b 結(jié)果中 A是不可達到的符號。 ? 例 文法 G4[S] : S→Ap|Bq A→aAp|d B→aBq|e ： S→ aApp|aBqq|dp|eq A→aAp|d B→aBq|e ： S→a(App|Bqq) S→dp|eq A→aAp|d B→aBq|e ： S→aS39。 S→dq|eq S39?！鶤pp|Bqq A→aAp|d B→aBq|e ： S→aS39。 S→dp|eq S39?！?aAppp|aBqqq|dpp|eqq A→aAp|d B→aBq|e ? 結(jié)論 ? 不一定每個文法的左公共因子都能在有限的步驟內(nèi)替換成無左公共因子的文法。 ? 一個文法提取了左公共因子后，只解決了相同左部產(chǎn)生式右部的 FIRST集不相交問題，當(dāng)改寫后的文法不含空產(chǎn)生式，且無左遞歸時，則改寫后的文法是 LL(1)文法，否則還需用 LL(1)文法的判別方式進行判斷才能確定是否為 LL(1)文法。 2. 消除左遞歸 ? 直接左遞歸 A→
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1