编译原理试题汇总+编译原理期末试题(8套含答案+大题集)

由于预测分析表中无多重入口，所以可判定文法是 LL(1)的。 4. 对下面的文法 G ： E ->TE' E'->+E| ε T ->FT' T' ->T| ε F-> PF' F'-> *F'| ε P->(E)|a|b|^

(1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。 (4 分) (2) 证明这个方法是 LL(1) 的。(4 分) (3) 构造它的预测分析表。(2 分)

解：（1）计算这个文法的每个非终结符的 FIRST 集和 FOLLOW集。 FIRST 集合有：

FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(E')={+,ε }

FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(T')=FIRST(T)U{ε}={(,a,b,^, ε}; FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(F')=FIRST(P)={*, ε}; FIRST(P)={(,a,b,^}; FOLLOW 集合有： FOLLOW(E)={),#};

FOLLOW(E')=FOLLOW(E)={),#}; FOLLOW(T)=FIRST(E')UFOLLOW(E)={+,),#};//不包含ε FOLLOW(T')=FOLLOW(T)=FIRST(E')UFOLLOW(E)={+,),#}; FOLLOW(F)=FIRST(T')UFOLLOW(T)={(,a,b,^,+,),#};//不包含ε FOLLOW(F')=FOLLOW(F)=FIRST(T')UFOLLOW(T)={(,a,b,^,+,),#}; FOLLOW(P)=FIRST(F')UFOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε (2)证明这个方法是 LL(1)的。 各产生式的 SELECT 集合有： SELECT(E->TE')=FIRST(T)={(,a,b,^}; SELECT(E'->+E)={+};

SELECT(E'->ε)=FOLLOW(E/)={),#} SELECT(T->FT')=FIRST(F)={(,a,b,^}; SELECT(T'->T)=FIRST(T)={(,a,b,^}; SELECT(T'->ε)=FOLLOW(T/)={+,),#}; SELECT(F->PF')=FIRST(P)={(,a,b,^}; SELECT(F'->*F')={*};

SELECT(F'->ε )=FOLLOW(F')={(,a,b,^,+,),#}; SELECT(P->(E))={(} SELECT(P->a)={a} SELECT(P->b)={b} SELECT(P->^)={^}

第9页共6页

可见，相同左部产生式的 SELECT 集的交集均为空，所以文法 G[E]是 LL(1)文法。 (3)构造它的预测分析表。 文法 G[E]的预测分析表如下：

5.已知文法 G[S] 为： S->a|^|(T) T-> T,S|S

(1) 计算 G[S] 的 FIRSTVT 和 LASTVT 。

(2) 构造 G[S] 的算符优先关系表并说明 G[S] 是否未算符优先文法。 (3) 给出输入串 (a,a)# 的算符优先分析过程。 解：（1）各符号的 FIRSTVT 和 LASTVT：

（2）算符优先关系表：

（3）句子(a,a)#分析过程如下：

第10页共6页

6.已知文法为：

S->a|^|(T) T->T,S|S

构造它的 LR(0)分析表。

解：加入非终结符 S' ，方法的增广文法为： S'->S S->a S->^ S->(T) T ->T,S

T ->S 下面构造它的 LR(0)项目集规范族为：

从上表可看出,不存在移进- 归约冲突以及归约归约冲突，该文法是 LR(0)文法。 从而有下面的 LR(0)分析表：

7.已知文法为： A ->aAd|aAb| ε

第11页共6页

判断该文法是否是 SLR(1) 文法，若是构造相应分析表，并对输入串 ab# 给出分析过程。 解：增加一个非终结符 S/后，产生原文法的增广文法有： S'->A A ->aAd|aAb|ε 下面构造它的 LR(0)项目集规范族为：

从上表可看出, 状态 I0 和 I2 存在移进- 归约冲突，该文法不是 LR(0)文法。对于 I0 来说有：

FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ ，所以在 I0 状态下面临输入符号为 a 时移进，为 b,d,#时

归约，为其他时报错。对于 I2 来说有也有与 I0 完全相同的结论。这就是说，以上的移进 - 归约冲突是可以解决的，因此该文法是 SLR(1)文法。

其 SLR(1)分析表为：

对输入串 ab#给出分析过程为：

《编译原理》历年试题及答案

第12页共6页