编译原理第4章作业答案.docx
《编译原理第4章作业答案.docx》由会员分享，可在线阅读，更多相关《编译原理第4章作业答案.docx（16页珍藏版）》请在冰点文库上搜索。
编译原理第4章作业答案
编译原理第4章作业答案
第四章
习题4.2.1：
考虑上下文无关文法：
S->SS+|SS*|a以及串aa+a*
（1）给出这个串的一个最左推导
S->SS*
->SS+S*
->aS+S*
->aa+S*
->aa+a*
（3）给出这个串的一棵语法分析树
习题4.3.1：
下面是一个只包含符号a和b的正则表达式的文法。
它使用+替代表示并运算的符号|，以避免和文法中作为元符号使用的竖线相混淆：
rexpr→rexpr+rterm|rterm
rterm→rtermrfactor|rfactor
rfactor→rfactor*|rprimary
rprimary→a|b
1）对这个文法提取公因子
2）提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？
3）提取公因子之后，原文法中消除左递归
4）得到的文法适用于自顶向下的语法分析吗？
解
1）提取左公因子之后的文法变为
rexpr→rexpr+rterm|rterm
rterm→rtermrfactor|rfactor
rfactor→rfactor*|rprimary
rprimary→a|b
2）不可以，文法中存在左递归，而自顶向下技术不适合左递归文法
3）消除左递归后的文法
rexpr->rtermrexpr’
rexpr’->+rtermrexpr’|
rterm->rfactorrterm’
rterm’->rfactorrterm’|
rfactor->rprimayrfactor’
rfactor’->*rfactor’|
rprimary->a|b
4）该文法无左递归，适合于自顶向下的语法分析
习题4.4.1：
为下面的每一个文法设计一个预测分析器，并给出预测分析表。
可能要先对文法进行提取左公因子或消除左递归
（3）S->S（S）S|
（5）S->（L）|aL->L,S|S
解
（3）
消除该文法的左递归后得到文法
S->S’
S’->（S）SS’|
用类Pascal语言构造的一个预测分析器：
PROCEDURES BEGIN S; WHILE（lookahead==’（'） THENBEGIN match（'（'）; S; match（'）'）; END; ELSEIF（lookahead=='a'） THENmatch（'a'） ELSEerror END;
计算FIRST和FOLLOW集合
FIRST（S）={（,
}FOLLOW（S）={）,$}
FIRST（S’）={（,
}FOLLOW（S’）={）,$}
构建预测分析表
非终结符号
输入符号
（
）
$
S
S->S’
S->S’
S->S’
S’
S’->（S）SS’
S’->
S’->
（5）
消除该文法的左递归得到文法
S->（L）|a
L->SL’
L’->,SL’|
用类Pascal语言的一个预测分析器：
PROCEDURES BEGIN if（lookahead==’（'） THENBEGIN match（'（'）; L; match（'）'）; END; ELSEIF（lookahead=='a'） THENmatch（'a'） ELSEerror END; PROCEDUREL; BEGIN S; WHILE（lookahead=='，'）; BEGIN match（'，'）; S; END; END;
计算FIRST与FOLLOW集合
FIRST（S）={（,a}FOLLOW（S）={）,,,$}
FIRST（L）={（,a}FOLLOW（L）={）}
FIRST（L’）={,,
}FOLLOW（L’）={）}
构建预测分析表
非终结符号
输入符号
（
）
a
$
S
S->（L）
S->a
L
L->SL’
L->SL’
L’
L’->
L’->,SL’
习题4.4.4计算练习4.2.2的文法的FIRST和FOLLOW集合
3）S→S（S）S|
5）S→（L）|a,L→L,S|S
解：
3）FIRST（S）={
（}FOLLOW（S）={（,）,$}
5）FIRST（S）={（,a}FOLLOW（S）={）,,,$}
FIRST（L）={（,a}FOLLOW（L）={）,,}
习题4.6.2为练习4.2.1中的增广文法构造SLR项集，计算这些项集的GOTO函数，给出这个文法的语法分析表。
这个文法是SLR文法吗？
S→SS+|SS*|a
解：
构造该文法的增广文法如下
S’->S
S->SS+
S->SS*
S->a
构造该文法的LR（0）项集如下
GOTO函数如下
GOTO（I0，S）=I1GOTO（I0，a）=I2
GOTO（I1，S）=I3GOTO（I1，a）=I2GOTO（I1,$）=acc
GOTO（I3，S）=I3GOTO（I3，+）=I4GOTO（I3，*）=I5GOTO（I3，a）=I2
构造该文法的语法分析表
状态
ACTION
GOTO
+
*
a
$
S
0
S2
1
1
S2
acc
3
2
R3
R3
R3
R3
3
S4
S5
S2
3
4
R1
R1
R1
R1
5
R2
R2
R2
R2
注：
FOLLOW（S’）=FOLLOW（S）={+,*,a,$}
这个文法是SLR文法，因为语法分析表中没有重复的条目
习题4.6.6说明下面文法
S→SA|A
A→a
是SLR
（1）的，而不是LL
（1）的。
证明：
1）可以求得FIRST（SA）=FIRST（A）={a}，故该文法不是LL
（1）文法
2）构造该文法的增广文法的语法分析表如下
构造增广文法
S’->S
S->SA
S->A
A->a
构造LR（0）项集族
GOTO函数如下
GOTO（I0，S）=I1GOTO（I0，A）=I2GOTO（I0,a）=I3
GOTO（I1，A）=I4GOTO（I1，a）=I3GOTO（I1,$）=acc
构建语法分析表如下（FOLLOW（A）=FOLLOW（S）={a,$}）
状态
ACTION
GOTO
a
$
S
A
0
S3
1
2
1
S3
acc
4
2
R2
R2
3
R3
R3
4
R1
R1
可以看到该语法分析表中没有重复的条目故该文法是SLR
（1）文法
习题4.7.4说明下面的文法
S->Aa|bAc|dc|bda
A->d
是LALR
（1）的，但不是SLR
（1）的
证明：
1、构造该文法的SLR
（1）语法分析表
构造增广文法
S’->S
S->Aa
S->bAc
S->dc
S->bda
A->d
构造LR（0）项集族
GOTO函数
GOTO（I0，S）=I1GOTO（I0，A）=I2GOTO（I0，b）=I3GOTO（I0，d）=I4
GOTO（I1,$）=accGOTO（I2，a）=I5GOTO（I3，A）=I6GOTO（I3，d）=I7
GOTO（I4，c）=I8GOTO（I6，c）=I9GOTO（I7，a）=I10
构建SLR语法分析表如下（FOLLOW（A）={a,c}）
状态
ACTION
GOTO
a
b
c
d
$
S
A
0
S3
S4
1
2
1
acc
2
S5
3
S7
6
4
R5
S8|R5
5
R1
6
S9
7
S10|R5
R5
8
R3
9
R2
10
R4
可以看到在图中存在二义性的条目，故该文法不是SLR
（1）文法
2、构造该文法的LALR
（1）语法分析表
构造该增广文法的LR
（1）项集族如下
项集合并：
没有可以合并的项集
GOTO函数
GOTO（I0，S）=I1GOTO（I0，A）=I2GOTO（I0，b）=I3GOTO（I0，d）=I4
GOTO（I1,$）=accGOTO（I2，a）=I5GOTO（I3，A）=I6GOTO（I3，d）=I7
GOTO（I4，c）=I8GOTO（I6，c）=I9GOTO（I7，a）=I10
构造LALR
（1）分析表如下
状态
ACTION
GOTO
a
b
c
d
$
S
A
0
S3
S4
1
2
1
acc
2
S5
3
S7
6
4
R5
S8
R5
5
R1
6
S9
7
S10
R5
8
R3
9
R2
10
R4
可见该分析表中不存在二义性的条目，故该文法是LALR
（1）文法
习题4.7.5说明下面的文法
S->Aa|bAc|Bc|bBa
A->d
B->d
是LR
（1）的，但不是LALR
（1）的
证明：
1、构造该文法的LR
（1）语法分析表
构造该文法的增广文法
S’->S
S->Aa
S->bAc
S->Bc
S->bBa
A->d
B->d
构造该增广文法的LR
（1）项集族如下
项集合并：
没有可以合并的项集
GOTO函数
GOTO（I0，S）=I1GOTO（I0，A）=I2GOTO（I0，b）=I3GOTO（I0，B）=I4GOTO（I0，d）=I5
GOTO（I1,$）=accGOTO（I2，a）=I6GOTO（I3，A）=I7GOTO（I3，B）=I8GOTO（I3，d）=I9
GOTO（I4，c）=I10GOTO（I7，c）=I11GOTO（I8，a）=I12
构造LR
（1）分析表如下
状态
ACTION
GOTO
a
b
c
d
$
S
A
B
0
S3
S5
1
2
4
1
acc
2
S6
3
S9
7
8
4
S10
5
R5
R6
6
R1
7
S11
8
S12
9
R6
R5
10
R3
11
R2
12
R4
可见该分析表中不存在二义性的条目，故该文法是LR
（1）文法
2、构造该文法的LALR
（1）语法分析表
I59
A->d.,a/c
B->d.,c/c
合并LR
（1）项集族
I5和I9可以合并为I59
构造LALR
（1）语法分析表如下
状态
ACTION
GOTO
a
b
c
d
$
S
A
B
0
S3
S59
1
2
4
1
acc
2
S6
3
S9
7
8
4
S9
59
R5|R6
R6|R6
6
R1
7
S10
8
S11
9
R3
10
R2
11
R4
可见该语法分析表中存在有二义性的条目，故该文法不是LALR
（1）文法
升级会员 