第5章自顶向下语法分析方法(编辑修改稿)

第5章自顶向下语法分析方法(编辑修改稿)内容摘要：

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)={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→ αβ|αγ导致 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→ ε 进一步化为： S→aS A A→b A→ ε S→ ε 结果仍然不是 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 结果是 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 结果中 A是不可达到的符号。 编译原理 • 例：文法 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。 →App|Bqq A→aAp|d B→aBq|e ： S→aS39。 S→dq|eq S39。 → aAppp|aBqqq|dpp|eqq A→aAp|d B→aBq|e 利用提取左公共因子 无法在有限步骤内 替换成无左公共因子的文法。 编译原理 结论 不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法。 一个文法提取了左公共因子后，只解决了相同左部产生式右部的 FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是 LL(1)文法，否则还需用 LL(1)文法的判别方式进行判断才能确定是否为 LL(1)文法。 编译原理 消除左递归 直接左递归： A→A β AVN, β V* 间接左递归： A→B β B→A α A,BVN, α,β V* 编译原理 文法 G5含有直。