第1页 / 共15页
第2页 / 共15页
第3页 / 共15页
第4页 / 共15页
第5页 / 共15页
第6页 / 共15页
第7页 / 共15页
第8页 / 共15页
编译原理课后答案（第三版）.doc
作业参考答案
第二章 高级语言及其语法描述
6、（1）L（G6）={0,1,2,......,9}+
（2）最左推导：
N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127
N=>ND=>DD=>3D=>34
N=>ND=>NDD=>DDD=>5DD=>56D=>568
最右推导：
N=>ND =>N7=>ND7=>N27=>ND27=>N127=>D127=>0127
N=>ND=>N4=>D4=>34
N=>ND=>N8=>ND8=>N68=>D68=>568
7、Ｇ：S→ABC | AC | C
A→1|2|3|4|5|6|7|8|9
B→BB|0|1|2|3|4|5|6|7|8|9
C→1|3|5|7|9
8、（1）最左推导：
E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i
E=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=>i*
(i+i)
最右推导：
E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*i
E=>T=>T*F=>T*(E)=>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=>T*(i+i)=>F*(
i+i)=>i*(i+i)
(2)
E
+
T
F
i
E
+
T
F
i
E
T
F
i
E
+
T
F
i
E
T
F
i
T
*
F
i
E
-
T
F
i
E
-
T
F
i
E
T
F
i
9、证明：该文法存在一个句子 iiiei 有两棵不同语法分析树，如下所示，因此该文法
是二义的。
i
S
i
S
S
i
e
S
i
S
i
i
S
e
S
i
S
i
1
11、
G1:
S→AB
A→aAb|ab
B→cB|ε
G2:
S→AB
A→aA|ε
B→bBc|bc
G3:
S→AA
A→aAb|ε
G4:
S→1S0|A
A→0A1|ε
第 3 章 词法分析
7、构造下列正规式相应的 DFA：1(0|1)*101
解：
（1）构造 NFA：
0,1
1
1
1
X
0
2
1
3
Y
（2）确定化：
构造状态转换矩阵如下：
I
{X}
{1}
{1,2}
{1,3}
I0
_
{1}
{1,3}
{1}
I1
{1}
{1,2}
{1,2}
{1,2,Y}
{1,2,Y}
{1,3}
{1,2}
画出状态转换图：
0
1
1
1
0
0
1
0
2
（注：已是最简）
8、（1）（0|1）*01
1
1
2
2
4
2
重命名：
S
0
1
2
3
4
3
0
1
3
1
3
1
4
1
0
（2）（0|1|2|3|4|5|6|7|8|9）(1|2|3|4|5|6|7|8|9)*(0|5)|0|5
（3）（10*1|0）*10*|（01*0|1）*01*
（4）a*b*c*......z*
9、（1）
正规式（0|1）*（010）（0|1）*
NFA:
0,1
X
0
1
0
1
0
0,1
Y
2
构造状态转换矩阵：
重命名：
I
{X}
{X,0}
{X,1}
{X,0,Y}
{X,1,Y}
{X,Y}
I0
{X,0}
{X,0}
{X,0,Y}
{X,0,Y}
{X,0,Y}
{X,0,Y}
画出 DFA：
I1
{X}
{X,1}
{X}
{X,1,Y|
{X,Y}
{X,Y}
S
0
1
2
3
4
5
0
1
1
3
3
3
3
1
0
2
0
4
5
5
1
5
1
4
0
1
0
最少化后：
1
0
0
0
1
1
0
0
1
1
1
1
0
2
0
3
1
0
0，1
0
2
3
12、（a）构造状态转换矩阵：
重命名：
I
{0}
{0，1}
{1}
Ia
{0，1}
{0，1}
{0}
Ib
{1}
{1}
——
重命名：
画出确定化后的有限自动机：
S
0
1
2
a
1
1
0
b
2
2
_
a
0
a
b
2
1
a
b
（b）最少化：首先分为终态集和非终态集：
{0，1}{2，3，4，5}
{0，1}a={1}
{0，1}b={2，4}
3
{2，3，4，5}a={1，3，0，5} 可分为{2，4}和{3，5}
{2，4}b={3，5}
{3，5}b={2，4}
形成划分：{0，1}{2，4}{3，5}
最少化后的 DFA：
b
b
a
2
a
0
b
a
1
14、每个 1 都有 0 直接跟在右边：
（10|0）*
0
0
1
0
1
A
1
F
0
B
0,1
1
0
0,1
C
15、画出 NFA：
0,1
S
1
0
等价的左线性正规文法：
F→A1|B0|C0|C1
S→0|1|S0|S1
A→1|S1
B→0|S0
C→A1|B0|C0|C1
4
第 4 章 语法分析——自上而下分析
1、S→a|^|(T)
T→T,S|S
(1)消除左递归
S→a|^|(T)
T→ST’
T’ →,ST’|ε
递归下降子程序：
void S()
{
if (sym==’a’) advanced();
else if (sym==’^’) advanced();
else if (sym==’(‘)
{advanced();
T();
if (sym==’)’) advanced();
else error();
}
void T()
{
S(); T’();
}
void T’()
{
if (sym==’,’)
{advanced(); S(); T’();}
else if (sym in follow(T’))
else error();
else error();
}
}
(2)
S
T
FIRST
{a,^,( }
{a,^,( }
FOLLOW
{#,,,）}
{）}
{）}
T’ {,,ε}
该文法是 LL(1)的：
方法一（利用概念）：
a. 不含左递归；
b. 候选终结首符集没有交集；
c. ε∈first(T’),follow(T’)∩first(T’)={}
方法二（指出预测分析表没有多重入口）
预测分析表如下：
a
S→a
T→ST’
^
S→^
T→ST’
(
S→(T)
T→ST’
)
,
#
T’→ε
T’→,ST’
S
T
T’
2、文法：
E→TE’
E’→+E|ε
T→FT’
T’→T|ε
F→PF’
5
F’→*F’|ε
P→(E)|a|b|^
(1)求每个非终结符号的 FIRST 和 FOLLOW 集合：
FIRST
{（，a，b，^ }
{+，ε}
{（，a，b，^ }
{ε，（，a，b，^ }
{（，a，b，^ }
{*，ε}
{（，a，b，^ }
E
E’
T
T’
F
F’
P
(2)略
(3)构造预测分析表
*
+
FOLLOW
{#,)}
{#,)}
{+,#,)}
{+,#,)}
{(,a,b,^, +,#,)}
{(,a,b,^, +,#,)}
{*,(,a,b,^, +,#,)}
（
）
E→TE’
E’→ε
^
E→TE’ E→TE’ E→TE’
b
a
#
E’→ε
T→FT’
T’→ε T’→T
F→PF’
T→FT’
T’→T
F→PF’
F’→ε F’→ε F’→ε F’→ε F’→ε F’→ε
P→(E)
T→FT’
T’→T
F→PF’
T→FT’
T’→T
F→PF’
P→b
T’→ε
P→^
P→a
E’→+E
T’→ε
E
E’
T
T’
F
F’
P
(4)略
4、文法：
F’→ε F’→*F’
Expr→-Expr|(Expr)|Var ExprTail
ExprTail→-Expr|ε
Var→id VarTail
VarTail→(Expr)|ε
(1)构造 LL(1)分析表：
FIRST 和 FOLLOW 集合如下：
FIRST
{-, ( , id }
{-,ε}
{id}
{(,ε)
Expr
ExprTail
Var
VarTail
LL(1)分析表：
-
Expr→-Expr
Expr
FOLLOW
{#, )}
{#, )}
{-,#, )}
{-,#, )}
(
Expr→(Expr)
)
#
id
Expr → Var
ExprTail
ExprTail
ExprTail→-Expr
Var
ExprTail →
ε
ExprTail →
ε
Var → id
VarTail
6
VarTail
VarTail→ε
VarTail→(Expr) VarTail→ε
VarTail→ε
所用产生式（略）
(2) 句子 id—id((id))的分析过程：
步骤
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
分析栈
#Expr
#ExprTail Var
#ExprTail VarTail id
#ExprTail VarTail
#ExprTail
#Expr -
#Expr
#Expr -
#Expr
#ExprTail Var
#ExprTail VarTail id
#ExprTail VarTail
#ExprTail )Expr(
#ExprTail )Expr
#ExprTail ))Expr(
#ExprTail ))Expr
#ExprTail ))ExprTail Var
#ExprTail ))ExprTail VarTail id
#ExprTail ))ExprTail VarTail
#ExprTail ))ExprTail
#ExprTail ))
#ExprTail )
#ExprTail
#
输入串
id--id((id))#
id--id((id))#
id--id((id))#
--id((id))#
--id((id))#
--id((id))#
-id((id))#
-id((id))#
id((id))#
id((id))#
id((id))#
((id))#
((id))#
(id))#
(id))#
id))#
id))#
id))#
))#
))#
))#
)#
#
#
7
第 5 章 语法分析——自下而上分析
1、文法：
E→E+T|T
T→T*F|F
F→(E)|i
证明 E+T*F 是它的一个句型，并指出该句型所有短语、直接短语和句柄。
解：E+T*F 是它的一个句型，因为存在下面语法树：
E
E
+
T
T
*
F
短语：T*F, E+T*F
直接短语：T*F
句柄：T*F
2、文法：
S→a|^|(T)
T→T,S|S
(1)给出(a,(a,a))和(((a,a),^,(a)),a)的最左和最右推导；
(2)指出(((a,a),^,(a)),a)的规范归约以及每一步的句柄，根据这个规范归约，给出“移进-归约”
过程，并给出它的语法树自下而上构造过程。
解：
(1)略
(2)①规范句型及每一步的句柄（用下划线标示）：
10）((T,( S )),a)
11）((T, (T) ),a)
12）(( T,S ),a)
13）( (T) ,a)
14）( S ,a)
15）( T ,a)
16）( T ,S )
17）(T)
18）S
1）((( a,a),^,(a)),a)
2）((( S,a),^,(a)),a)
3）(((T，a ),^,(a)),a)
4）((( T,S ),^,(a)),a)
5）(( (T) ,^,(a)),a)
6）(( S ,^,(a)),a)
7）(( T ,^ ,(a)),a)
8）(( T ,S ,(a)),a)
9）((T,( a )),a)
②“移进-规约”过程：
步骤
（1）
（2）
（3）
（4）
（5）
（6）
（7）
分析栈
#
#(
#((
#(((
#(((a
#(((S
#(((T
输入串
动作
(((a,a),^,(a)),a)# 预备
((a,a),^,(a)),a)# 移进
(a,a),^,(a)),a)# 移进
a,a),^,(a)),a)# 移进
,a),^,(a)),a)# 移进
,a),^,(a)),a)# 归约
,a),^,(a)),a)# 归约
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
