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

目前修改了第三题的部分问题。

1.考虑下面文法G1:

S→a∣∧∣(T)

T→T，S∣S

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

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

2.对下面的文法G:

P→(E)lalblΛ

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

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

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

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

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

（1）S→Abc

         A→a∣ε

         B→b∣ε

这里是不是写错了，应该是S→ABc？，下图答案是以S→ABc为准。

     看了一下网上流传的答案，基本上都是first(S)={a,b,c}和下图结果一样，如果是S->Abc的话，那么first(S)={a,b}。

下图答案是以S→Abc为准

（2）S→Ab

         A→a∣B∣ε

         B→b∣ε

（3）S→ABBA

         A→a∣ε

         B→b∣ε

 （4)S→aSe∣B

       B→bBe∣C

       C→cCe∣d

4. 对下面文法：

              Expr→-Expr

              Expr→(Expr)∣Var

              ExprTail→-Expr∣ε

              Var→id VarTail

              VarTail→(Expr)∣ε

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

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

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

第1步对文法G的每个产生式A→α执行第1步和第3步；

第2步对每个终结符a∈FIRST(α)，把A→α加至M[A，a]中；

第3步若ε∈FIRST(α)，则对任何b∈FOLLOW(A)把A→α加至M[A，b]中；

第4步把所有无定义的M[A，a]标上“出错标志”。

解答：

（1）计算每个非终结符的FIRST集合和FOLLOW集合如下：

              FIRST(Expr)={-，(，id}

              FIRST(ExprTail)={-，ε}

              FIRST(Var)={id}

              FIRST(VarTail)={(，ε}

              FOLLOW(Expr)={)，#}

              FOLLOW(ExprTail)={)，#}

              FOLLOW(Var)={-，)，#}

              FOLLOW(VarTail)={-，∣，#}

构造其预测分析表如下：    

（2）句子id--id((id))的分析过程如下：    

步骤

符号栈

输入串

所用产生式

0

# Expr

id--id((id)) #

1

# ExprTail Var

id--id((id)) #

Expr→Var ExprTail

2

# ExprTail VarTail id

id--id((id)) #

Var→id VarTail

3

# ExprTail VarTail

--id((id)) #

4

# ExprTail

--id((id)) #

VarTail→ε

5

# Expr -

--id((id)) #

ExprTail→-Expr

6

# Expr

-id((id)) #

7

# Expr -

-id((id)) #

Expr→-Expr

8

# Expr

id((id)) #

9

# ExprTail Var

id((id)) #

Expr→Var ExprTail

10

# ExprTail VarTail id

id((id)) #

Var→id VarTail

11

# ExprTail VarTail

((id)) #

12

# ExprTail ) Expr (

((id)) #

VarTail→(Expr)

13

# ExprTail ) Expr

(id)) #

14

# ExprTail ) ) Expr (

(id)) #

15

# ExprTail ) ) Expr

id)) #

16

# ExprTail ) ) ExprTal Var

id)) #

Expr→Var ExprTail

17

# ExprTail ) ) ExprTail VarTail id

id)) #

Var→id VarTail

18

# ExprTail ) ) ExprTail VarTail

)) #

19

# ExprTail ) ) ExprTail

)) #

VarTail→ε

20

# ExprTail ) )

)) #

ExprTail→ε

21

# ExprTail )

) #

22

# ExprTail

#

23

#

#

ExprTail→ε

suc

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

       Declist→Declist；Decl∣Decl

       Decl→IdList：Type

       IdList→IdList，id∣id

       Type→ScalarType∣array(ScalarTypeList) of Type

       ScalarType→id∣Bound..Bound

       Bound→Sign IntLiteral∣id

       Sign→+∣-∣ε

       ScalarTypeList→ScalarTypeList，ScalarType∣ScalarType

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

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

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

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

首先消除左递归，得到文法G(Declist)：

                     Declist→Decl Declist’

                     Declist’→；Decl Declist’∣ε

                     Decl→IdList：Type

                     IdList→id IdList’

                     IdList’→，id List’∣ε

                     Type→ScalarType∣array(ScalarTypeList) of Type

                     ScalarType→id∣Bound..Bound

                     Bound→Sign IntLiteral∣id

                     Sign→+∣-∣ε

                     ScalarTypeList→ScalarType ScalarTypeList’

                     ScalarTypeList’→，ScalarType ScalarTypeList’∣ε

  显然，改造后的文法没有左公共因子，计算每个非终结符的FIRST集合和FOLLOW集合如下：

                     FIRST(Declist)={id}

                     FIRST(Declist’)={；，ε}

                     FIRST(Decl)={id}

                     FIRST(IdList)={id}

                     FIRST(IdList’)={；，ε}

                     FIRST(Type)={id，+，-，IntLiteral，array}

                     FIRST(ScalarType)={id，+，-，IntLiteral}

                     FIRST(Bound)={id，+，-，InLiteral}

                     FIRST(Sign)={+，-，ε}

                     FIRST(ScalarTypeList)={id，+，-，IntLiteral }

                     FIRST(ScalarTypeList’)={，，ε}

                     FOLLOW(Declist)={#}

                     FOLLOW(Declist’)={#}

                     FOLLOW(Decl)={id，；}

                     FOLLOW(IdList)={：}

                     FOLLOW(IdList’)={：}

                     FOLLOW(Type)={id，；}

                     FOLLOW(ScalarType)={id，；，），，}

                     FOLLOW(Bound)={id，；，）’，’..}

                     FOLLOW(Sign)={IntLiteral}

                     FOLLOW(ScalarTypeList)={)}

                     FOLLOW(ScalarTypeList’)={)}

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