第5章自顶向下的语法分析方法

第5章自顶向下的语法分析方法内容摘要：

OW(D)={} 判断它是否是 LL(1)文法 文法 G [S]为： S→AB S→bC A→ε A→b B→ε B→aD C→AD C→b D→aS D→c 每个产生式的 SELECT集合计算为： SELECT(S→AB)= （ FIRST(AB){ε })∪ FOLLOW(S)={b,a,} SELECT(S→bC)=FIRST(bC)={b} SELECT(A→ε)=(FIRST(ε) {ε }) ∪ FOLLOW(A)={a,c,} SELECT(A→b)=FIRST(b)={b} SELECT(B→ε)=(FIRST(ε) {ε }) ∪ FOLLOW(B)={} SELECT(B→aD)=FIRST(aD)={a} SELECT(C→AD)=FIRST(AD)={a,b,c} SELECT(C→b)=FIRST(b)={b} SELECT(D→aS)=FIRST(aS)={a} SELECT(D→c)=FIRST(c)={c} 文法 G [S]为： S→AB S→bC A→ε A→b B→ε B→aD C→AD C→b D→aS D→c 由以上计算结果可得相同左部产生式的 SELECT交集为： SELECT(S→AB)∩SELECT(S→bC)={b,a,}∩{b}={b}≠ SELECT(A→ε)∩SELECT(A→b)={a,c,}∩{b}= SELECT(B→ε)∩SELECT(B→aD)={}∩{a}= SELECT(C→AD)∩SELECT(C→b) ＝ {b,a,c}∩{b}＝ {b}≠ SELECT(D→aS)∩SELECT(D→c)={a}∩{c} ＝ 由 LL(1)文法定义知该文法不是 LL(1)文法，因为关于 S和 C的相同左部其产生式的 SELECT集的交集不为空。 非 LL(1)文法到 LL(1)文法的等价转换 由前面可知：确定的自顶向下分析要求对给 定语言的文法必须是 LL(1)形式。 然而，不 一定每个语言都有 LL(1)文法。 对一个语言 的非 LL(1)文法是否能变换为等价的 LL(1)形 式以及如何变换是本节讨论的主要问题。 若文法中含有直接或间接左递归，或含有左公共因子则该文法肯定不是 LL(1)文法。 因而，我们设法消除文法中的左递归，提取左公共因子对文法进行等价变换，在某些特殊情况下可能使其变为 LL(1)文法。 1．提取左公共因子 若文法中含有形如： A→αβ|αγ 的产生式，这导致了对相同左部的产生式其右部的 FIRST集相交，也就是SELECT(A→αβ)∩SELECT(A→αγ) ≠ ， 不满足 LL(1)文法的充分必要条件。 现将产生式 A→αβ|αγ 进行等价变换为： A→α （ β|γ） 使产生式变换为： A→αA′ A′→β|γ 写成一般形式为： A→αβ1|αβ2|…|αβn ，提取左公共因子后变为： A→α （ β1|β2|…|βn ），再引进非终结符 A′，变为： A→αA′ A′→β1|β2|…|βn 若在 βi、 βj、 βk … ( 其中 1≤i， j， k≤n)中仍含有左公共因子，这时可再次提取，这样反复进行提取直到引进新非终结符的有关产生式再无左公共因子为止。 例 1：若文法 G的产生式为： (1) S→aSb (2) S→aS (3) S→ε 请提取文法中的左公因子 对产生式 (1)、 (2)提取左公因子后得： S→ aS(b|ε) S→ε 进一步变换为文法 G′： S→aSA A→b A→ε S→ε 例 2：若文法 G的产生式为： (1) A→ad (2) A→Bc (3) B→aA (4) B→bB 请提取文法中的隐式左公因子。 产生式 (2)的右部以非终结符开始，因此左公共因子可能是隐式的，所以这种情况下对右部以非终结符开始的产生式，用其相同左部而右部以终结符开始的产生式进行相应替换，对文法 G2分别用 (3)、 (4)的右部替换 (2)中的 B，可得： (1) A→ad (2) A→aAc (3) A→bBc (4) B→aA (5) B→bB 提取产生式 (1)、 (2)的左公共因子得： A→a(d|Ac) A→bBc B→aA B→bB 引进新非终结符 A′，去掉 39。 (39。 ， 39。 )39。 后得 G′为： (1) A→aA′ (2) A→bBc (3) A′→d (4) A′→Ac (5) B→aA (6) B→bB 不难验证经提取左公共因子后文法例 1中的 G′仍不是 LL(1)文法。 而文法例 2中的 G′变成 LL(1)文法，因此文法中不含左公共因子只是 LL(1)文法的必要条件。 值得注意的是对文法进行提取左公共因子变换后，有时会使某些产生式变成无用产生式，在这种情况下必须对文法重新压缩 (或化简 例 3：若有文法 G的产生式为： (1) S→aSd (2) S→Ac (3) A→aS (4) A→b 用产生式 (3)、 (4)中右部替换产生式 (2)中右部的A，文法变为： (1) S→aSd (2) S→aSc (3) S→bc (4) A→aS (5) A→b 对 (1)、 (2)提取左公共因子得： S→aS(d|c) 引入新非终结符 A′后变为： (1) S→aSA′ (2) S→bc (3) A′→d|c (4) A→aS (5) A→b 显然，原文法 G3中非终结符 A变成不可到达的符号，产生式 (4)、 (5)也就变为无用产生式，所以应删除。 此外也存在某些文法不能在有限步骤内提取完左公共因子。 例：若有文法 G4的产生式为： (1) S→Ap|Bq (2) A→aAp|d (3) B→aBq|e 用 (2)、 (3)产生式的右部替换 (1)中产生式的 A、 B使文法变为： (1) S→aApp|aBqq (2) S→dp|eq (3) A→aAp|d (4) B→aBq|e 对 (1)提取左公共因子则得： S→a(App|Bqq) 再引入新非终符 S′结果得等价文法为： (1) S→aS′ (2) S→dp|eq (3) S′→App|Bqq (4) A→aAp|d (5) B→aBq|e 同样分别用 (4)、 (5)产生式的右部替换 (3)中右部的 A、 B再提取左公共因子最后结果得： (1) S→aS′ (2) S→dp|eq (3) S′→aS″ (4) S′→dpp|eqq (5) S″→Appp|Bqqq (6) A→aAp|d (7) B→aBq|e 可以看出若对 (5)中产生式 A、 B继续用 (6)、 (7)产生式的右部替换，只能使文法的产生式愈来愈多无限增加下去，但不能得到提取左公共因子的预期结果。 由上面所举例子可以说明以下问题： ① 不一定每个文法的左公共因子都能在有限的步骤内 替换成无左公共因子的文法，上面文法 G4就是如 此。