消除左递归（4分） （1）消除下列文法的左递归（2分） E→E×T|E/T|T T→0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 （2）基于消除左递归的文法，构建如下表达式的语法树（2分） 1×2/3

在文法中，E和T的规则中含有左递归，所以首先消除左递归。依据前面介绍的消除左递归方法，很容易得到不含左递归的等价文法： E→TA A→+TA|ε T→FB B→*FB|ε F→(E)|i 由于文法中不含公共左因子，所以不需要提取。 下面计算FIRST集合和FOLLOW集合。 对于E→TA，计算其惟一候选TA的FIRST集合。根据FIRST集合的定义，得到FIRST(TA)=FIRST(T)=FIRST(F)={(,i}。 A→+TA|ε，两个候选的FIRST集合分别为FIRST(+TA)={+}，FIRST(ε)={ε}。 T→FB，候选FB的FIRST集合为FIRST(FB)=FIRST(F)={(,i}。 B→*FB|ε，两个候选的FIRST集合分别为：FIRST(*FB)={*}，FIRST(ε)={ε)。 F→(E)|i，两个候选的FIRST集合分别为：FIRST((E))={(}，FIRST(i)={i}。 下面计算每个非终结符的FOLLOW集合。 首先，由于E为文法起始符号，所以#∈FOLLOW(E)。下面考察每个产生式规则，利用前面FOLLOW的计算规则，来计算非终结符的FOLLOW集合。 E→TA有：FOLLOW(E) FOLLOW(A)，FOLLOW(E) FOLLOW(T)(由于A可以推导出空串)，FIRST(A)-{ε} FOLLOW(T)； A→+TA|ε，不可能得出新的结论(得出的结论与根据前一个规则得出的结论相同)； T→FB有：FOLLOW(T) FOLLOW(B)，FOLLOW(T) FOLLOW(F)(由于B可以推导出空串)，FIRST(B)-{ε} FOLLOW(F)； B→*FB|ε，不可能得出新的结论(得出的结论与根据前一条规则得出的结论相同)； F→(E)|i有：)∈FOLLOW(E)。 由于FIRST(A)=(+,ε}，FIRST(B)={*,ε}，根据前面得出的这些关系，计算出文法非终结符的FOLLOW集合如下： FOLLOW(E)={#,)} FOLLOW(A)={#,)} FOLLOW(B)={#,+,)} FOLLOW(T)=(#,+,)} FOLLOW(F)={#,+,),*} 下面构造预测分析表： E→TA，FIRST(TA)={(,i}，所以应该在E行(列与E行i列放置规则E→TA； A→+TA|ε，FIRST(+TA)={+}，所以应该在A行+列放置A→+TA，由于第2个候选的FIRST集合包含空串，所以需要用到FOLLOW(A)，由于FOLLOW(A)={#,}}，所以应在A行#列和A行)列放置第2个候选A→ε。 另外几个规则进行相同的考察，得出：T行(列和T行i列放置T→FB；B行*列放置B→*FB，B行#列，+列和)列放置B→ε；F行(列放置F→(E)，i列放置F→i。这样，就得到如表4-2所示的预测分析表。 表4—2 预测分析表 i + ( ) * # E E→TA E→TA A A→+TA A→ε A→ε T T→FB T→FB B B→ε B→ε B→*FB B→ε F F→i F→(E) 表中的空白位置表示出错标志。 由于构造出的预测分析表不含多重入口，因此，给定文法经过消除左递归后，是LL(1)文法。$该文法中不含左递归，没有公共左因子。 下面计算FIRST集合。 对于S→ABBA，由于A和B都可以推导出空串ε，所以FIRST(ABBA)=(FIRST(A)-{ε})∪(FIRST(B)-{ε})∪(FIRST(B)-{ε})∪(FIRST(A)-{ε})∪{ε}={a,b,ε}； 对于A→a|ε，第1个候选的FIRST集合为FIRST(a)={a}，第2个候选的FIRST集合为FIRST(e)={ε)； 同样，对于B→b|ε，两个候选的FIRST集合分别为FIRST(b)={b)，FIRST(ε)={ε}。 下面计算非终结符的FOLLOW集合。 首先，由于s为文法起始符号，所以#∈FOLLOW(S)； 对于S→ABBA，有下面的结论：FOLLOW(S) FOLLOW(A)，FOLLOW(S) FOLLOW(B)(由于A可以推出空串来)，HRST(BBA)-{ε} FOLLOW(A)，FIRST(BA)-{ε) FOLLOW(B)，FIRST(A)-{ε) FOLLOW(B)； 对于A→a|ε和B→b|ε，由于规则右侧没有任何文法非终结符，因此无法得出有关FOLLOW集合的任何信息。 综合起来，有FOLLOW(S)={#}，FOLLOW(A)={#,b,a}，FOLLOW(B)={#,b,a}。 计算了FIRST集合后，可以构造预测分析表。对于S→ABBA，由于FIRST(ABBA)={a,b,ε}，因此，应该在S行a列和b列放置S→ABBA，同时该候选的FIRST集合中含有空串，因此需要考察FOLLOW(S)，由于该集合中只含有#，因此，应在#列放置S→ABBA；对于A→a|ε，第1个候选的HRST集合为{a}，因此应在A行a列放置第1个候选A→a，同时，第2个候选的HRST集合为{ε}，因此，应该在A行FOLLOW(A)={#,a,b)中每一元素所对应的列上放置第2个候选A→ε；类似地，需要在B行b列放置B→b，在#,a,b列上放置B→ε。得到了如表4—3的预测分析表： 表4—3 预测分析表 a b # S S→ABBA S→ABBA S→ABBA A A→a A→ε A→ε A→ε B B→ε B→b B→ε B→ε 构造出的预测分析表含有多重入口(A行a列含有两个不同的候选，B行b列含有两个不同的候选)，即存在矛盾和冲突，因此给定文法不是LL(1)文法。$给定文法既含有直接左递归，又含有间接左递归。消除其中的直接左递归，结果如下： A→BaP|cP P→aP|ε B→AbQ|dQ Q→bQ|ε 经过消除直接左递归后，文法中还含有间接左递归，主要是在A和B的规则中，对于A→BaP，如果用B→AbQ来替换，则会出现左递归；或者对于B→AbQ，用A→BaP来替换，也会出现左递归。消除这里的间接左递归，可以如下进行： A→BaP|cP B→BaPbQ|cPbQ|dQ(将产生式B→AbQ|dQ中的A用A→BaP|cP的右部替换) B的规则中新出现的直接左递归进行消除，得到： B→cPbQR|dQR R→aPbQR|ε 整个文法经过消除左递归后，变成如下的形式： A→BaP|cP P→aP|ε B→cPbQR|dQR R→aPbQR|ε Q→bQ|ε 此文法不需要提取公共左因子。 针对该文法，计算FIRST集合和FOLLOW集合，然后构造预测分析表。这里不再详细说明计算过程和造表过程，只给出结果如下： A的每个候选的FIRST集合如下： FIRST(BaP)=FIRST(B)={c,d}； FIRST(cP)={c}； P的每个候选的FIRST集合如下： FIRST(aP)={a}； FIRST(e)={ε}； B的每个候选的FIRST集合如下： FIRST(cPbQR)={c}； FIRST(dQR)={d} R的每个候选的FIRST集合如下： FIRST(aPbQR)={a}； FIRST(ε)={ε}； Q的每个候选的HRST集合如下： FIRST(bQ)={b)： FIRST(ε)={ε}。 每个文法非终结符的FOLLOW集如下(其中A为文法起始符号)： FOLLOW(A)={#)； FOLLOW(P)={b,#)； FOLLOW(B)={a}； FOLLOW(R)={a}； FOLLOW(Q)={a}。 得到如下的预测分析表，如表4-4所示。 表4—4 预测分析表 a b c d # A A→BaP A→cP A→BaP P P→aP P→ε P→ε B B→cPbQR B→dQR R R→aPbQR R→ε Q Q→ε Q→bQ 由于预测分析表中含有多重入口，因此，经过消除左递归后的文法仍然不是LL(1)文法。$该文法是描述条件语句语法结构的。在该文法中，不存在左递归，也不需要提取公共左因子。 下面计算FIRST集合。 S规则每个候选的FIRST集合分别为： FIRST(I)={i}； FIRST(o)={o}； I规则每个候选的FIRST集合分别为： FIRST(i(B)S E)={i}； E规则每个候选的FIRST集合分别为： FIRST(e S)={e}； FIRST(ε)={ε}； B规则每个候选的FIRST集合分别为： FIRST(t)={t}； FIRST(f)={f}。 下面给出每个文法非终结符的FOLLOW集合如下： FOLLOW(S)={#,e)； FOLLOW(I)={#,e}； FOLLOW(E)={#,e}； FOLLOW(B)={}}。 构造出如下的预测分析表，如表4-5所示。 表4—5 构造出的预测分析表 o i ( ) e t f # S S→o S→I I I→i(B)S E E E→eS E→ε E→ε B B→t B→f 由于构造出的预测分析表含有多重入口，因此，给定文法不是LL(1)文法。$该文法存在左递归，所以先要消除左递归，得到文法为： E→TE' E'→T+E'|ε T→FT' T'→F*T'|ε F→E|i 求解FIRST、FOLLOW集合： FIRST(E)={i} FOLLOW(E)={#,i,*,+} FIRST(E')={i,ε} FOLLOW(E')={#,i,*,+} FIRST(T)={i} FOLLOW(T)={#,i,*,+} FIRST(T')={i,ε} FOLLOW(T')={#,i,*,+} FIRST(F)={i} FOLLOW(F)={#,i,*,+} 构造预测分析表，如表4-6所示。 表4-6 构造预测分析表 + * i # E E→TE' E' E'→ε E'→ε E'→T+E' E'→ε E'→E T T→FT' T' T'→ε T'→ε T'→FOT' T'→ε T'→ε F F→E F→i 由以上预测分析表可知：该预测分析表含有重定义，所以该文法不是LL(1)文法。