编译原理陈火旺版第四章课后题答案

下面答案仅供参考！

1.考虑下面文法G1:

 

(1) 消去 Q 的左递归。然后，对每个非终结符，写岀不带回溯的递归子程序。

(2) 经改写后的文法是否是LL(1)的？给出它的预测分析表。

 

2.对下面的文法G:

P→(E)lalblΛ

(1)计算这个文法的每个非终结符的FIRST和FOLIOW.

(2)证明这个文法是LL(1)的。

 

(3)构造它的预测分析表。

(4)构造它的递归下降分析程序。

 

 

 

3.下面文法中,哪些是LL(1)的,说明理由。

 

 

 

  

 

4. 对下面文法：

 

(1) 构造 LL(1)分析表。

(2) 给出对句子 id - -id((id))的分析过程。

构造文法的预测分析表,通常应当按下列步骤进行： (1) 消除文法的左递归(包括所有直接左递归和间接左递归）； (2) 对消除左递归后的文法，提取左公因子； (3) 对经过上述改造后的文法，计算它的每个非终结符的 FIRST 集合和 FOLLOW 集合 ⑷ 根据 FIRST 集合和 FOLLOW 集合构造预测分析表：

 

 

5. 把下面文法改写为 LL(1)的：

       本题目主要考査学生理解和运用消除文法的左递归、提取左公共因子等算法的能力， 为判断文法是否是 LL(1)文法，还要计算文法的 FIRST 集合和 FOLLOW 集合。

     消除文法的左递归的基本思想是，将文法规则中的左递归结构变换成等价的右递归结构。

     提取左公因子的算法，是对包含公共左因子的产生式候选，反复提取左因子，就能够 把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。

     消除文法的左递归、提取左公共因子后，再计算文法的各非终结符00的首符集 FIRST( X)和随符集 FOLLOW( X)，然后根据 LL(1)文法的充分必要条件（即 LL(1)文法 的定义)来判断文法是否是 LL(1)文法。

 

显然，改造后的文法是 LL(1)的。