-
编译原理
作业参考答案
第
1
章
引
言
1
、解释下列各词
< br>源语言
:
编写源程序的语言（基本符号，关键字）
，各种程序设计语言都可以作为源语言。
源程序
:
用接近自然语言（数学语言
）的源语言（基本符号，关键字）编写的程序，它是翻译
程序处理的对象。
目标程序
:
目标程序是源程序经过翻译程序加工最后得到的程序。目标程序
（结果程序）一般可由计算机直接执行。
低级语言：机器语言和汇编语言。
高
级语言：是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言（接近数学
语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的
组合规则。
翻译程序
:
能够把某一种语言程序（源语言程序）改变成另一种语言程序（目
标语言程序）
，后者与前者在逻辑上是等价的。其中包括：
编译程序，解释程序，汇编程序。
编译程序
:
把输入的源程序翻译成等
价的目标程序（汇编语言或机器语言）
，
然后再执行目标程序（先编译后执行）
，执行翻译工作的程序称为编译程序。
解释程序
:
以该
语言写的源程序作为输入，但不产生目标程序。按源程序中语句动态顺序逐句
的边解释边
执行的过程，完成翻译工作的程序称为解释程序。
2
、什么叫“遍”？
指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加工处
理，称为一遍。
3
、简述编译程序的基本过程的任务。
编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整个过程可以划
分
5
个阶段。
词法分析：输入源程序，进行词法分析，输出单词符号。
语法分析：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位，并
判断输入串是否构成语法正确的“程序”
。
中间代码生成：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一
定形式的中
间代码。
优化：对中间代码进行优化处理。
目标代码生成：把中间代码翻译成目标语言程序。
4
、编译程序与解释程序的区别？
<
/p>
编译程序生成目标程序后，再执行目标程序；然而解释程序不生成目标程序，边解释边执行
。
5
、有人认为编译程序的五个组成
部分缺一不可，这种看法正确吗？
编译程序的
5
个阶段中，词法分析，语法分析，语义分析和代码生成生成是必须完成的。而
中
间代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量，没
有这一部分
工作，仍然能够得到目标代码。
6
、编译程序的分类
目前基本分为：诊断编译程序，优化编译程序，交叉编
译程序，可变目标编译程序。
1
编译原理
作业参考答案
第
2
章
高级语言及其语法描述
1
（
P36
）令文法为
N
?
D
?
ND
D
?
0
?
1<
/p>
?
2
???
9
（
1
）
文法描述的语言
L
（
G
）是什么？
（
2
）给出句子
34
，
568
的最左推导和最右推导。
答：
（
1
）
L
（
G
）
={
???
为可带前导
0
的正整数
}
+
或
L
（
G
）
={
（
0
?
1
?
2
???
9
）
}
或
L
（
G<
/p>
）
={
???
为
数字串
}
（
2
）
最左推导：
N
?
N
D
?
DD
?
3
D
?
34
N
?
ND
?
NDD
?
DDD
?
5DD
< br>?
56D
?
568
最右推导：
N
?
ND
?
N4
?
D4
?
34
N
?
ND
?
N8
?
ND8
?
N68
?
D68
?
568
2*
．写出一个文法，使其语言是奇
数集，且每个奇数是不以
0
开头。
答：
S
?
CAB|B
（考虑了正负号）
A
?
1 | 2 | 3 | 4 | 5 | 6 | 7
| 8 | 9 | AA | A0 |
?
B
?
1|3|5|7|9
C
?
+|-|
?
S
?
B | AB
B
?
1 | 3 | 5 | 7 | 9
A
?
AD | N
N
?
2 | 4 | 6 | 8
| B
D
?
0 | N
S
?
C | ABC
C
?
1 | 3 | 5 | 7
| 9
A
?
1 | 2 | 3
| 4 | 5 | 6 | 7 | 8 | 9
或：
（未考虑正负号）
或：
（未考虑正负号）
B
?
BA | B0 |
?
2.
（
P36,
8
）令文法为
E
?
T
?
E+
T
?
E-T
T
?
F
?
T*
F
?
T/F
F
?
（
E
）
?
i
（
1
）给出该文法的
V
N
、
V
T
和<
/p>
S
。
<
/p>
（
2
）给出
i+
i*i
，
i*
（
i+i
）的最左推导和最右推导。
（
3
）给出
i+i+i
，
i+i*i
的语法树。
<
/p>
答：
（
1
）
V
N
= {
E, T, F }
V
T
= {
+, -, *, /, (, ), i }
2
编译原理
作业参考答案
S = E
（
2
）
最左推导
E
?
E<
/p>
+T
?
T
+T<
/p>
?
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)
< br>?
i*(
F
+T)
?
i*(i+
T
)
?
i*(i+
F
)<
/p>
?
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
< br>)
?
T*(E+
F
)
?
T*(
E
+i)
?
T*
(
T
+i)
?
T*(
F
+i)
?
T
*(i+i)
?
F
*(i+i)
?
i*(i+i)
⑵构造语法树
E
最左推导构造语法树
E
+ T
E + T i
T i
i
3.
（
P36,
9
）
证明下面的文法是二义的：
S
?
iSeS | iS
?
i
答：<
/p>
对于句子
iiiei
有两棵不同的语法树
。因此该文法是二义的。
S
?
iSeS
?
iiSeS
?
iiieS
?
iiiei
S
?
iS
?
iiSeS
?
iiieS
?
iiiei
3
编译原理
作业参考答案
第
3
章
词法分析
1
．设
M=
（
{x
，
y}
，
{a
，
b}
，
?
，
x
，
{y}
）为一个非确定有限自动机
NFA M
，其中
< br>?
定义
如下：
?
（
x
，
a
）
={x
，
y}
?
（
x
，
b
）
={y}
?
（
y
，
a
）
=
?
?
（
y
，
b
）
={x
，
y}
试构造其相应的最小化的确定有限自动机
DFA
M
’
。
答：
由
?
定义可知
?
（
x
，
a<
/p>
）
，
?
（
y
，
b
）均为多值函
数，所以是一个非确定有限自动机。
（
1
）根据
?
函数值，先构造
NFA M
（
2<
/p>
）确定化：
①
构造
DFA
M
’
的转换矩阵
:
I
{x}
①
{x
，
y}
②
{y}
③
②
确定
DFA
M
’的初始状态和终态：
（
a
）转换矩阵中
I
列的
第一个状态①为
DFA
M
’的初始状态结点。
（
b
）含有
y
状态的子集均
为
DFA M
’的终态结点
(
②、③为终态结点
)
。
③
根据
DFA
M
’的转换矩阵画出对应的状态转换图：
I
a
{x
，
y}
②
{x
，
y}
②
I
b
{y}
③
{x
，
y}
②
{x
，
y}
②
（
3
）最小
化：
①
首先将其划分成终态集
{2
，
3}
和非终态集
{1}
②
{2
，<
/p>
3}a=
｛
2
｝
?
{2
，
3}
，
{2
，
3}b=
｛
2
｝
?
{2
，
3}
因此
{2
，
3}
已是不可再区分的
,
所以该
DFA
M
’
已是最小化的。
2.
（
P64
，
7(1)
）构造正规式
1(0
?
1)
*
101<
/p>
相应的
DFA
M
。
答：
（
1
）构造
NFA
M
。
1
（
0
?
1
）
101
Y
X
4
*
编译原理
作业参考答案
1
（
0
?
1
）
X
1
*
3
1
0 1
Y
4
5
1
?
?
1 0 1
Y
X
1
2
3
4
5
0
?
1
0
1
?
?
1 0 1
X
1
2
3
4
5
Y
1
（
2
）构造转换矩阵
I
I
0
I
1
{X}
①
{1,
2, 3}
②
{1, 2, 3}
②
{2, 3}
③
{2,
3, 4}
④
{2, 3}
③
{2,
3}
③
{2,
3, 4}
④
{2, 3, 4}
④
{2, 3, 5}
⑤
{2, 3, 4}
④
{2,
3, 5}
⑤
{2, 3}
③
{2, 3, 4, Y}
⑥
{2, 3, 4, Y }
⑥
{2, 3, 5}
⑤
{2,
3, 4}
④
（
3
）由转
换矩阵构造
DFA M
0
0
3
1
0
1
1
6
0
1
< br>1
2
1
1
4
5
3
．
（
P64
，
1
2(a)
）将下图所示的
NFA
M
转换为等价的
DFA M
’
，并将该
DFA
’
最小
化。
答：
该有限自动机状态
0
输入同一字符
a<
/p>
时到达两个不同的结点
,
所以是
NFA
。
（
1
）构造转换矩阵
I
I
a
I
b
{0}
①
{0
，
1}
②
{1}
③
{0
，
1}
②
{0
，
1}
②
{1}
③
{1}
③
{0}
①
5
编译原理
作业参考答案
（
2
）由转换矩阵构造
DFA M
a
2
a
b
1
a
b
3
（
3
）将
DFA
M
最小化
①
将
DFA M
的状态划分为非终态集<
/p>
{3}
和终态集
{1
，
2}
②
对每一个子集及每一个
a
??
进行
考察；
{1
，
2}a = {2}
?
{1
，
2}
{1
，
2}b = {3}
?
{3}
因此
{1
，
2}
是不可区分的，所以最
终状态为：
{1
，
2}
，
{3}
构造最小化的
DFA
M
：
a
b
1
2
，
3
a
4.
（
P
64
，
12
（
b
）
）将下图所示的
NFA
M
转换为等价的
DFA
M
’
，并进行最小化。
b
b
a
a
< br>0
a
2
b
b
3
a
1
a
b
4
b
5
a
答：
从图上可知该图已经是
DFA
M
，先只需将其最小化。
首先划分为
两个集合：
{0,1}
和
{2,3,4
,5}
{2,3,4,5}a = {1,3,0,5}
，划
分为：
{2,4}
和｛
3,5
｝
{2,4}a =
{1,0}
，
{2,4}b =
{3,5}
，无需划分
{3,5}a
= {3,5}
，
{3,5}b =
{2,4}
，无需划分
{0,1}a
= {1}
，
{0,1}b =
{2,4}
，无需划分
因此，
最终的划分为：
{0,1}
、
{2,4
}
和｛
3,5
｝
，化简后的结果：
b
0,1
a
a
a
2,4
b
b
3,5
a
5
．
（
P65
，
14
）构造一个
DFA
M
，它接受
< br>?
={0
，
1}
上所有满足如下条件的字符串：每个
1
都有
0
直接跟在右边。
答：
6
编译原理
作业参考答案
（
1
）根据题意，得到正规式：
(0|10)*
（
2
）构造对应的
NFA
M
：
0
x<
/p>
?
1
1
0
?
Y
2
（
3
）将
NFA
M
确定化为
DFA
M
。相应的
DFA
M
的状态转换矩阵如下：
I
I
0
I
1
{X,
1,Y}
①
{1; Y}
②
{2}
③
{1, Y }
②
{1; Y }
②
{2}
③
{2}
③
{1; Y}
②
1
0
3
1
0
1
2
0
DFA
M
转换图：
（
4
）将
DFA
M
最小化：
①
将
DFA M
的状态划分为非终态集<
/p>
{3}
和终态集
{1, 2}
②
对每一个子集进行考察；
{1,
2}
0
= {2}
?
{1, 2}
{1, 2}
1
=
{3
，
3}
?
{3}
因此
{0,
1}
是不可划分的。
因此最终划分结果为：
{1,
2}
和
{3}
最小化后的
DFA
M
：
0
<
/p>
1,2
1
0
3<
/p>
7
编译原理
作业参考答案
第
4
章
语法分析
-
自上而下
1.
（
P81
，
1
）考虑下面文法
G
S
?
a
?<
/p>
^
?
(T)
T
?
T,S
?
S
（
1
）消除文法的左递归。
（
2
）经改写后的
文法是否是
LL(1)
的？给出它的预测分析表。
答：
（
1
）
消除左递归：
S
?
a
?
^<
/p>
?
(T)
T
?
ST
’
T
’
?
,ST
’
|
?
（
2
）
证明改写后的文法是否是
LL(1)
的。<
/p>
FIRST(S) = { a, ^, ( }
FOLLOW(S) =
{
，
, ), # }
FIRST(T) = { a, ^, ( }
FOLLOW(T) = { ) }
FIRST(T
’
) = {
，
,
?
}
FOLLOW(T
’
) = { )
}
①
证明
S
?
a
?
^
?
（
T
）各侯选式的
FIRST
是否两两相交。
FIRST
（
a
）
?
< br> FIRST
（
^
）
=
?
FIRST
（
a
）
?
FIRST
（
（）
=
?
FIRST
（
^
）
?
FIRST
（
（）
=
?
②
证明
T
’
?
，
ST
’
??
的
FIRST
（
T<
/p>
’
）和
FOLLOW
（
T
’
）是否相交。
FIRST
（
T
’
）
?
FOLLOW
（
T
’
）
={
，
，
?
}
?
{
?
}=
?
∴
该文法是
LL
（
1
）的。
所以，改造后的文法是
LL(1)
文法
③
预测分析表：
a
^
(
)
T
’
??
T
’
?
,ST
’
，
#
S
S
?
a
S
?
^
S
?
(T)
T
T
?
< br>ST
’
T
?
ST
’
T
?
ST
’
T
’
2.
利用
P76
表
4.1
的
LL(1)
分析表写出表达式
(i+i)*i
的预测分析过程。
步骤
符号栈
输入串
所用的产生式
0 #E
（
i+i
）
*i#
1
#E
’
T
（
i+i
）
*i#
E
?
TE
’
2
#E
’
T
’
F
（
i+i
）
*
i#
T
?
FT
’
3 #E
’
T
’
）
E
< br>（
（
i+i
）
*i# F
?
（
E
）
4 #E
’
T
’
）
E
i+i
）
*i#
5 #E
’
T
’
）
E`T
i+i
）
*i#
E
?
TE
’
6 #E
’
T
’
）
E
< br>’
T
’
F
i+i
）
*i#
T
?
FT
’
7 #E
’
T
’
）
E
< br>’
T
’
i
i+i
）
*i#
F
?
i
8
#E
’
T
’
）
E
’
T
’
+i
）
*i#
9 #E
’
T
’
）
E
< br>’
+i
）
*i#
T
’
??
8
编译原理
作业参考答案
10 #E
’
T
’
）
E
’
T+
+i
）
*i# E
’
?
+TE
’
11 #E
’
T
’
）
E
< br>’
T i
）
*i#
12 #E
’
T
’
）
E
< br>’
T
’
F
i
）
*i#
T
?
FT
’
13 #E
’
T
’
）
E
< br>’
T
’
i
i
）
*i#
F
?
i
14
#E
’
T
’
）
E
’
T
’
）
*i#
15 #E
’
T
’
）
E
< br>’
）
*i#
T
’
??
16 #E
’
T
’
）
）
*i#
E
’
??
18
#E
’
T
’
*i#
19 #E
’<
/p>
T
’
F*
*i# T
’
?
*FT
’
20
#E
’
T
’
F
i#
21
#E
’
T
’
i
i# F
?
i
22
#E
’
T
’
#
23
#E
’
#
T
’
??
24 # #
E
’
??
3.
（
P81
，
2
）对下面的文法
G
E
?
TE
’
E
’
?
+E
??
T
?
FT
’
T
’
?
T
??
F
?
PF
’
F
’
?
*F
’
??
P
?
(E)
?
^
?
a
?
b
（
1
）计
算这个文法的每个非终结符的
FIRST
和
FOLLOW
。
（
2
）证明这个文法是
LL(1)
的。
（
3
）构造它的预测分析表。
答：
（<
/p>
1
）计算每个非终结符的
FIRST
和
FOLLOW
。
FIRST(E)={(, a, b, ^ }
FIRST(E
’
)={ +,
?
}
FIRST(T)={(, a, b, ^ }
FIRST(T
’
)={(, a,
b, ^ ,
?
}
FIRST(F)={(, a, b, ^ }
FIRST(F
’
)={ * ,
?
}
FIRST(P)={(, a, b, ^ }
FOLLOW(E)={ ) ,# }
FOLLOW(E
’
)={ ), #
}
FOLLOW(T)={ +, ), # }
FOLLOW(T
’
)={ +,
), # }
FOLLOW(F)={ +,(, a,
b, ^, ), # }
FOLLOW(F
’
)={ +,(,
a, b, ^, ), # }
FOLLOW(P)={ *,+,(, a,
b, ^, ), # }
（求解过程：
< br>因为
E`
?
+E
??
，所以
FIRST
（
E`
）
={+
，<
/p>
?
}
因为<
/p>
F`
?
*F`
?
?
，所以
FIRST
（
F`
）
={*
，
?
}
因为
P
?
（
E
< br>）
?
^
?
a
?
b
，所以
FIRST
（
P
）
< br>={
（，
^
，
a
，
b
?
因为
F
?
PF`
，所以
FIRST
（
F
）
= FIRST
（
P
）
因为
T
?
FT`
，所以
FIRST
（
T
）
={FIRST
（
F
）
因为
E
?
T
E`
，所以
FIRST
（
E
）
= FIRST
（
T
）
因为
T`
?
T
??
，所以
FIRST
（
T`
）
= FIRST
（
T
）
?
{
?
}
={
（，
^
，
a
，
b
，
??
9