下面答案仅供参考！
目前修改了第三题的部分问题。
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)={-，∣，#}
构造其预测分析表如下：
| - | id | ( | ) | # | |
| Expr | Expr→- Expr | Expr→Var ExprTail | Expr→-( Expr) | ||
| ExprTail | ExprTail→-Expr | ExprTail→ε | ExprTail→ε | ||
| Var | Var→id VarTail | ||||
| VarTail | VarTail→ε | VarTail→(Expr) | VarTail→ε | 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’)={)}文章来源：https://www.toymoban.com/news/detail-438535.html
显然，改造后的文法是 LL(1)的。文章来源地址https://www.toymoban.com/news/detail-438535.html
到了这里，关于编译原理陈火旺版第四章课后题答案的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
