-
第一章
1
．典型的编
译程序在逻辑功能上由哪几部分组成？
答：编译程序主要由以
下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、
中间代码优化、目标
代码生成、错误处理、表格管理。
2.
实现编译程序的主要方法有哪些？
答：主要有：转换法、移植法、自展法、自动生成法。
3.
将用户使用高级语言编写的程序翻译为可直接执行的机器
语言程序有哪几种主要的方
式？
答：编译法、解释法。
4.
编译方式和解释方式的根本区别是什么？
答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执
行，所以编译方式的效率高，执行速度快；
解释方式：在
执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文
件，效率低，
执行速度慢。
1
第二章
1.
乔姆
斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关
系如何？
答：
1
）<
/p>
0
型文法、
1
型
文法、
2
型文法、
3
< br>型文法。
2
）
2.
写一个文法，使其语言是偶整数的集合，每个偶整数不以
0
为前导。
答：
Z
?
SME | B
S
?
1|2|3|4|5|6|7|8|9
M
?
?
|
D | MD
D
?
0|S
B
?
2|4|6|8
E
?
0|B
N
?
D|ND
D
?
0|1|2|3|4|5|6|7|8|9
请给出句子
123
、
301
和
7
5431
的最右推导和最左推导。
答
：
N
?
ND
?
N3
?
ND3
?
N23
?
D23
?
123
N
?
ND
?
NDD<
/p>
?
DDD
?
1D
D
?
12D
?
123
N
?
ND
?
N1
?
ND1
< br>?
N01
?
D01
?
301
N
?
ND
?
NDD
?
DDD
?
3DD
?
30D
?
301
N
?
ND
?
N
1
?
ND1
?
N31
?
ND31
?
< br>N431
?
ND431
?
N5431
?
D5431
?
75431
N
?
ND
?
NDD
?
NDDD
?
NDDDD
?
DDDDD
?
7DDDD
?
75DDD
?
754DD
?
7543D
?
75431
3.
设文法
G
为：
4.
证明文法
S
?
iSeS|iS|
i
是二义性文法。
答：对于句型
iiSeS
存在两个不同的最左推导：
S
?
iSeS
?
ii
Ses
S
?
iS
?
iiSeS
所以该文法是二义性文法。
（
1
）
L1={a
n
b
n
c
i
|n>=1,i>=0 }
（
2
）
L2={a
i
b
j
|j>=i>=1}
（
3
）
L3={a
n
b
m
c
m
d
n
|m,n>=0}
答：
（
1
）
S
?
AB
A
?
aAb | ab
B
?
cB |
?
（
2
）
S
?
ASb |ab
2
5.
给出描述下面语言的上下文无关文法。
A
?
a |
?
（
3
）
S
?
aSd | A |
?
A
?
bAc |
?
6.
设计一个最简的
DFA M,
使其能够
识别所有的被
3
整除的无符号十进制整数。
答：
2|5|8
0|3|6|9
1|4|7
0|3|6|9
0
1
1|4|7
2
0|3|6|9
2|5|8
2|5|8
1|4|7
7.
设计一个
DFA,
使其能够接受被
4
整除的二进制数。
答：
0
< br>0
1
1
1
0
1
0
2
1
0
3
8.
写出表达下列各项的正则表达式。
（
1
）二进制数且为
5
< br>的倍数。
（
2
）
Σ
={a,b,c},
第一
个
a
位于第一个
b
之前的字符串。
（
3
）
Σ
={a,b,c},
包含偶数个
a
的字符串。
（
4
）
Σ
={0
，
1},
不包含
11
子串的字符串。
答：
（
1
）
可以先画出相应的有限自动机
: <
/p>
1
0
1
1
0
1
A
B
1
0
C
D
0
0
E
添加新的开始状态
S
和终止状态
T:
3
1
0
1
1
0
1
S
?
A
?
B
1
< br>0
C
D
0
0
E
T
根据以上自动机，列出以下方程：
①
S=A
②
A=0A+1B+T
③
B=0C+1D
④
C=0E+1A
⑤
D=0B+1C
⑥
E=0D+1E
解以上方程组：
⑥
?
E=1
*
0D
②
?
A=
0
*
1B+0
*
T
⑥代入④
?
C=01
*
0D+1A
*
*
⑤代入④
?
C=01
00B+01
01C+1A
?
C=xB+yA
其中
x=(01
*
01)
*
01
*
00
y=(01
*
01)
*
1
⑤代入③
?
B=0C+10B+11C
?
B=(0|11)C+10B
?
B=(10)
*
(0|11)C
将<
/p>
C=xB+yA
代入上式
?
B=uB+vA
?
B=u
*
vA
其中
u=(10)
< br>*
(0|11)x
v=(10)
*
(0|11)y
将<
/p>
B=u
*
vA
代
入②
?
A=0
*
1u
*
vA+0
*
T
*
*
*
< br>*
?
A=(0
1u
v)
0
T
将
A
代入①
?
S=(0
*
1u
*
v)
*
0
*
T
串
(0
*
1u
*
v)
*
0
*
即为所求。
<
/p>
（
2
）该题目理解为：至少有一个
a
和一个
b
，且
a
出现在
b
的前面
（可以有间
隔），则答案为：
c*a(a|c)*b(a|b|c)*
（
< br>3
）
((b|c)*a(b|c)*a)*(b|c)*
(a(b|c)*a | b | c)*
（
4
）
(0|10)*(1|
?
)
4
第三章
1.
词法分析器的功能是什么？
答：读源
程序的字符序列，逐个拼出单词，并构造相应的内部表示
TOKEN
；同时检查源程
序中的词法错误。
2.
试分析分隔符（空格、跳格及回车等）对词法分析的影响。
<
/p>
答：空格、跳格、回车等分隔符号对词法分析不起作用，可以删除。但是回车符号可以用<
/p>
于错误定位，所以在删除回车符号前需要统计回车的个数。
3.
给出识别
C
语言全部实型常数的自动机。
答
：
(+|-|
?
)([1-9][0-
9]*|0)(.[0-9][0-9]*|
?
)
(E(+|-|
?
)[0-9][0-9]*)
4.
写出识别
C
语言中所有单词的
LEX
程序。
答：
L=[A-Z] | [a-z]
D=[0-9]
D1=[1-9]
%%
(L|_)(L|D|_)* {return (1);}
D1D*
{return (2);}
+
{return (3);}
……
5
第四章
1.
设有如下文法
G[S]:
S
?
aABbcd |
?
A
?
ASd |
?
B
?
SAh | eC |
?
C
?
Sf | Cg |
?
(1)
求每个产生式的
Predict
集。<
/p>
(2)
该文
法是否为
LL(1)
文法？为什么？
答：
(1)
Predict(S
?
aABbcd)={a}
Predict(S
?
?
)={#,d,f,a,h }
P
redict(A
?
ASd)={a,d}
Predict(A
?
?
)={h,a,d,b,e}
Pr
edict(B
?
SAh)={a,d,h}
Predict(B
?
eC)={e}
Predict(B
?
?
)={b}
Predict(C<
/p>
?
Sf)={a,f}
Predict(C
?
Cg)={a,f,g}
Predict(C
?
?
)={g,b}
(2)
由于
Predict(A
?
ASd)
?
Predict(A
?
?
)
??
，所以该文法不是
LL(1)
文法。
(1)
S
?
(SS’ |
?
S’
?
) |
?
(2)
S
?
(S)S |
?
(3)
S
?
S(S)S |
?
(4)
S
?
(S |
S’
S’
?
(S’) |
?
答：
(1
)
不是，
(2)
是，
< br>(3)
不是，
(4)
不是
3.
已知文法
G[E]:
E
?
E+T | T
T
?
T*F | F
F
?
i | (E)
请按递归下降法构造该文法的语法分析程序。
答：求产生式的
predict
集合：
2.
下
列描述括号匹配的文法中，哪些是
LL(1)
文法？
predict(E
?
E+T)={i,(}
predict(E
?
T)={i,(}
predict(T
?
T*F)={i,(}
predict(T
?<
/p>
F)={i,(}
6
由于文
法中非终极符号
E
和
T
对应的产生式的
predict
集合的交集都不为空，
所以该文
E
?
TE’
E’
?
+TE’ |
?
T
?
FT’
T’
?
*FT’ |
?
F
?
i
F
?
(E)
求新文法的
predict
集合：
<
/p>
Predict(E
?
TE’)={(,
i}
Predict(E’
?
+TE’)={+}
Predict(E’
?
?
)={#,)}
Predict(T
?
FT’)={i,(}
Predict(T’
?
*FT’)={*}
Predict(T’
?
?
)={+,),#}
Predict(F
?
i)={i}
Predict(F
?
(E))={(
}
由于以上文法中任意非终极符号对应的产生式的
predi
ct
集合的交集都为空，
所以满足
Vo
id E()
{
if(token
?
{
(,i})
{T();E’();}
else
Error();}
void E’()
{
if(token
?
{
+})
{Match(‘+’);T();E’();}
else
if(token
?
{#,)}) {;}
else Error();}
void T()
{
if(token
?
{
i,(})
{F();T’();}
else
Error();}
void T’()
{
if(token
?
{
*})
{Match(‘*’);F();T’();}
else
if(token
?
{+,),#}) {;}
else Error();}
void F()
{
if(token
?
{
i})
{Match(‘i’);}
else
if(token
?
{
(})
{Match(‘(‘);E();Match(‘)’);}
else Error();}
L={
?
|
?
为字母表
?
上不包括两个相邻的<
/p>
1
的非空串
}
，
其中
?
={0
，
1}
。
法不满足自顶向下分析的条
件，现对文法进行等价变换得到如下文法：
自顶向下分析的条
件，所以可以写出如下的递归下降语法分析伪代码：
4. <
/p>
构造一个
LL(1)
文法
G
，它能识别语言
L:
并证
明你所构造的文法是
LL(1)
文法。
7
答：
A
?
0E
| 1F
B
?
0E | 1F
C
?
0E
E
?
B |
?
F
?
C |
?
Predict(A
?
0E)={0}
Predict(A
?
1F)={1}
Predict(B
?
0E)={0}
Predict(B
?
1F)={1}
Predict(E
?
B)={0,1
}
Predict(E
?
?
)={#}
Predict(F
?
C)={0}
Predict(F
?
?
)={#}
对任意非终极符号对应的产生式的
pr
edict
集合的交集都为空，所以该文法是
LL(1)
文
法。
5.
已知文法
G[A]
为：
A
?
aABe | a
B
?
Bb | d
(1)
试给出与
G[A]
等价的
LL(1)
文法<
/p>
G’[A]
。
(2)
构造
G’[A]
的
LL(1)
分析表并给出
输入串
aade#
的分析过程。
答：
(1)
所求
G
’[A]
为：
A
?
aA’
A’
?
ABe
A’
?
?
B
?
dB’
B’
?
bB’
B’
?
?
(1)
(2)
(3)
(4)
(5)
(6)
Predict(A
?
aA’)={a}
Predict(A’
?
ABe)={a}
Predict(A’
?
?
)={#,d}
Predict(B
?
< br>dB’)={d}
Predict(B’
?
bB’)={b}
Pr
edict(B’
?
?
)={e} <
/p>
对任意非终极符号对应的产生式的
predict
集合的交集都为空，所以该文法是
LL(1)
文
(3)
分析表如下：
法。
A
A’
a
(1)
(2)
b
d
(3)
e
#
(3)
8
B
B’
(5)
(4)
(6)
aade#
的分析过程如下
分析栈
A#
aA’ #
A’
#
ABe#
aA’Be#
A’Be#
Be#
dB’e#
B’e#
e#
#
输入流
aade#
aade#
ade#
ade#
ade#
de#
de#
de#
e#
e#
#
动作
替换
(1)
匹配
替换
(2)
替换
(1)
匹配
替换
(3)
替换
(4)
匹配
替换
匹配
成功
9
第五章（这章答案是错的）
1.
设有下列文法：
(1)
S
?
aA
A
?
Ab
A
?
b
S
?
aSSS
S
?
c
S
?
b
A
?
SA
A
?
a
S
?
ccB
B
?
ccB
B
?
b
A
?
cA
A
?
a
(2)
S
?
aSSb
(3)
S
?
AS
(4)
S
?
cA
构
造上述文法的
LR(0)
归约活前缀状态机，并给出
LR(0)
分析表。
答：
(1)
Ch05-1-(1)
0
Z→
.S
S→
.a
A
A
→
.Ab
A
→
.b
3
A
→
b.
(2)
有移入、规约冲突
1
S
a
Z→S
.
2
S→a
.A
A
→
.Ab
A
→
.b
b
A
4
S→a
A.
A
→
A.b
b
5
A
→
Ab.
10
Ch05-1-(2)
1
Z
→
S.
S
0
Z→
.S
S→
.aSSb
S→
.aSSS
< br>S→
.c
c
5
< br>S→c
.
c
2
< br>S→a
.SSb
S→a
.SSS
S→
.c
S→
.aSSb
S→
.aSSS
a
c
a
S
3
S→aS
.Sb
S→aS
.
SS
S→
.c
S→
.aSSb
S→
.aSSS
a
4
S→aSS
.b
S→aSS
.S
S→
.c
S→
.aSSb
S→
.aS
SS
c
b
S
6
S→aSSb
.
7
S→aSS
S.
a
S
action
a
S0
Z→
.S
(1)
S→
.aSSb
(2)
S→
.aSSS
(3)
S→
.c (4)
S1
S2
S3
S4
S5
S6
S7
(3)
goto
c
< br>s5
Acc
s5
s5
#
S
1
3
4
7
R4
R2
R3
b
s2
s2
s2
s2
R4
R2
R3
s6
R4
R2
R3
s5
R4<
/p>
R2
R3
11
Ch05-1-(3)
有移入、规约冲突
2
A
→
SA.
1
Z→S
.
A
→
S.A
A
→
.SA
A
→
.a
S
a
4
a
A
→
a.
5
b
S
→
b.
b<
/p>
S
7
S→
AS.
A
S
3
A
→
S.A
A
→
.a
A
→
.SA<
/p>
S→
.AS
S
→
.b
b
8
A<
/p>
→
SA.
S→
A
.S
S→
.AS
S
→
.b
A
9
S
S→
AS.
S
10
A
S→
.AS
S→
A.S
S
→
.b
A
S
b
b
0
Z→
.S
S→
.AS
S
→
.b
A
→
.SA
A
→
.a
A
6
S→
A.S
S
→
.b
a
(4)
Ch05-1-(4)
0
Z→
.S
S→<
/p>
.cA
S
→
.c
cB
2
Z→S
.
S
4
S→
cA.
A
1
S→
c.A
< br>c
S
→
c
A
→
.cA
A
→
.a
a
a
3
A
→
a.<
/p>
6
S
→
ccB.
B
5
S
→
cc.B
B
→
.c
cB
B
→
.b
A
→
c.A
A
→
.cA
A
→
.a
8
B
→
<
/p>
A
→
c.A
A<
/p>
→
.cA
A
→<
/p>
.a
c
A
7
A
A
→
cA.
b
9
B
→
b.
c
c
11
B
→
ccB.
B
10
B
→
cc.B<
/p>
B
→
.ccB
B
→
.b
A
→<
/p>
c.A
A
→
.c
A
A
→
.a
A
b
a
a
12
Z→S
(1)
S→
cA
(2)
S
→
ccB
(3)
B
→
ccB
(4)
B
→
b
(5)
A
→
cA
(6)
A
→
a (7)
a
S0
S1
S2
S3
S4
S5
S6
S7
S8
S9
S1
0
S11
s3
R7
R6
s3
R3
R2
s3
R5
s3
R4
action
b
c
s1<
/p>
s5
R7
R6
s
8
R3
R2
s10
R5
s8
R4
#
< br>A
4
goto
B
S
2
R7
R6
s9
R3
R2
R5
s9
R4
Acc
R7
R6
7
R3
R2<
/p>
7
R5
7
R4<
/p>
11
6
2.
设有下列文法：
(1)
S
?
SaS | b
(2)
S
?
bSb | cSc | b |
c
(3)
S
?
bSb | bSc | d
(4)
S
?
aSb | bSa | ab
(5)
S
?
Sab | bR
R
?
S | a
B
?
b
A
?
aA | B
B
?
?
A
?
?
B
?
dB |
?
(6)
S
?
SAB | BA
(7)
S
?
AaAb | BbBa
(8)
A
?
aABe | Ba
说明上述文法是否为
SLR(1)
文法。若是，请
构造
SLR(1)
分析表；若不是，请说明理由。
答：
(1)
Ch05-2-(1)
不是<
/p>
SLR
（
1
）<
/p>
Follow(S)={#,a}
0
Z→
.S
S→
.SaS
S
→
.b
b
1
S
→
b.
2
S
Z→S
.
S→
3
S→
S
a.S
a
S→
.SaS
S
→
.b
b
< br>S
a
4
S→
SaS.
S→
13
(2)
Ch05-2-(2)
不是<
/p>
SLR
（
1
）<
/p>
Follow(S)={#,b,c}
0
1
S→
S
→<
/p>
b.
S→
.bSb
S
→
.cSc
S
→
.b
S
→
.c
Z
→
.S
S→
.bSb
S
→
< br>.cSc
S
→
.b
S
→
.c
(3)
b
Ch05-2-(3)
Z
→
.S
S→
.bSb
S
→<
/p>
.bSc
S
→
.
d
S
1
Z
→<
/p>
S.
0
是
SLR
（
1
）
3
d
S
→
d.
5
S→
bSb.
b<
/p>
4
S→
bS.b
S→
bS.c
c
6
S→
bSc.
d
2
S→
b
S→
< br>
S→
.bSb
b
S
→
.bSc
S
→
.d
S
Z
→
.S
(1)
S→
.bSb (2)
S
→
.bSc
(3)
S
→
.d (4)
S0
S1
S2
S3<
/p>
S4
S5
S6
b
s2
s2
R4
s5
R2
R3
action
c
d
s3
s3
#
goto
S
1
R4
s6
R2
R3
Acc
Ch05-2-7
4
R4
R2
R3
(4)
14