2024年4月15日发(作者：)
《编译原理》课后习题答案第一章
第 4 题
对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、
代码生成）报告的。
（1） else 没有匹配的if
（2） 数组下标越界
（3） 使用的函数没有定义
（4） 在数中出现非数字字符
答案：
（1） 语法分析
（2） 语义分析
（3） 语法分析
（4） 词法分析
《编译原理》课后习题答案第三章
第1 题
文法G＝({A,B,S},{a,b,c},P,S)其中P 为：
S→Ac|aB
A→ab
B→bc
写出L(G[S])的全部元素。
答案：
L(G[S])={abc}
第2 题
文法G[N]为：
N→D|ND
D→0|1|2|3|4|5|6|7|8|9
G[N]的语言是什么？
答案:
G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9}
N=>ND=> =>D=>D......D
或者：允许0 开头的非负整数？
第３题
为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。
答案：
G[S]:
S->S+D|S-D|D
D->0|1|2|3|4|5|6|7|8|9
第4 题
已知文法G[Z]：
Z→aZb|ab
写出L(G[Z])的全部元素。
答案：
Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb
L(G[Z])={anbn|n>=1}
第5 题
写一文法，使其语言是偶正整数的集合。 要求：
(1) 允许0 打头；
(2)不允许0 打头。
答案：
(1)允许0 开头的偶正整数集合的文法
E→NT|D
T→NT|D
N→D|1|3|5|7|9
D→0|2|4|6|8
(2)不允许0 开头的偶正整数集合的文法
E→NT|D
T→FT|G
N→D|1|3|5|7|9
D→2|4|6|8
F→N|0
G→D|0
第6 题
已知文法G：
<表达式>::=<项>｜<表达式>＋<项>
<项>::=<因子>｜<项>*<因子>
<因子>::=（<表达式>）｜i
试给出下述表达式的推导及语法树。
（５）i+(i+i)
（６）i+i*i
答案：
<表达式>
<表达式> + <项>
<因子>
<表达式>
<表达式> + <项>
<因子>
i
<项>
<因子>
i
<项>
<因子>
i
（ )
(5) <表达式>
=><表达式>＋<项>
=><表达式>＋<因子>
=><表达式>＋（<表达式>）
=><表达式>＋（<表达式>＋<项>）
=><表达式>＋（<表达式>＋<因子>）
=><表达式>＋（<表达式>＋i）
=><表达式>＋（<项>＋i）
=><表达式>＋（<因子>＋i）
=><表达式>＋（i＋i）
=><项>＋（i＋i）
=><因子>＋（i＋i）
=>i＋（i＋i）
<表达式>
<表达式> + <项>
<项> * <因子>
<因子> i
<项>
<因子>
i
i
(6) <表达式>
=><表达式>＋<项>
=><表达式>＋<项>*<因子>
=><表达式>＋<项>*i
=><表达式>＋<因子>*i
=><表达式>＋i*i
=><项>＋i*i
=><因子>＋i*i
=>i＋i*i
第7 题
证明下述文法G[〈表达式〉]是二义的。
〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉
〈运算符〉∷=+|-|*|/
答案：
可为句子a+a*a 构造两个不同的最右推导:
最右推导1 〈表达式〉〈表达式〉〈运算符〉〈表达式〉
〈表达式〉〈运算符〉a
〈表达式〉* a
〈表达式〉〈运算符〉〈表达式〉* a
〈表达式〉〈运算符〉a * a
〈表达式〉+ a * a
a + a * a
最右推导2 〈表达式〉〈表达式〉〈运算符〉〈表达式〉
〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉
〈表达式〉〈运算符〉〈表达式〉〈运算符〉 a
〈表达式〉〈运算符〉〈表达式〉 * a
〈表达式〉〈运算符〉a * a
〈表达式〉+ a * a
a + a * a
第8 题
文法G[S]为：
S→Ac|aB
A→ab
B→bc
该文法是否为二义的？为什么？
答案：
对于串abc
(1)S=>Ac=>abc (2)S=>aB=>abc
即存在两不同的最右推导。所以，该文法是二义的。
或者：
对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。
S
a B
b c
S
A c
a b
第9 题
考虑下面上下文无关文法：
S→SS*|SS+|a
(1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。
S
S S *
S S + a
a a
(2)G[S]的语言是什么？
答案：
(1)此文法生成串aa+a*的最右推导如下
S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*
(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。
第10 题
文法S→S(S)S|ε
(1) 生成的语言是什么？
(2) 该文法是二义的吗？说明理由。
答案：
（１） 嵌套的括号
（２） 是二义的，因为对于（）（）可以构造两棵不同的语法树。
第11 题
令文法G[E]为：
E→T|E+T|E-T
T→F|T*F|T/F
F→(E)|i
证明E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。
答案：
此句型对应语法树如右，故为此文法一个句型。
或者：因为存在推导序列: E=>E+T=>E+T*F，所
以 E+T*F 句型
此句型相对于E 的短语有:E+T*F；相对于T 的短语
有T*F
直接短语为：T*F
句柄为：T*F
第13 题
一个上下文无关文法生成句子abbaa 的推导树如下：
(1)给出串abbaa 最左推导、最右推导。
(2)该文法的产生式集合P 可能有哪些元素？
(3)找出该句子的所有短语、直接短语、句柄。
B
a
S
A B S
a
S B A
ε b b a
答案：
(1)串abbaa 最左推导:
S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa
最右推导：
S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa
(2)产生式有：S→ABS |Aa|ε A→a B→SBB|b
可能元素有：ε aa ab abbaa aaabbaa ……
(3)该句子的短语有：
a 是相对A 的短语
ε 是相对S 的短语
b 是相对B 的短语
εbb 是相对B 的短语
aa 是相对S 的短语
aεbbaa 是相对S 的短语
直接短语有：a ε b
句柄是：a
《编译原理》课后习题答案第四章
第1 题
构造下列正规式相应的DFA.
（１） 1(0|1) *101
（２） １(1010*|1(010)*1）*0
（３） a((a|b)*|ab*a)*b
（４） b((ab)*|bb)*ab
答案：
(1) 先构造NFA：
用子集法将NFA 确定化
. 0 1
X . A
A A AB
AB AC AB
AC A ABY
ABY AC AB
除X，A 外，重新命名其他状态，令AB 为B、AC 为C、ABY 为D，因为D 含有Y（NFA
的终态），所以D 为终态。
. 0 1
X . A
A A B
B C B
C A D
D C B
DFA 的状态图：:
(2)先构造NFA：
X 1 A
ε B
1 C 0 D 1 E
0
ε
F 1 G 0 H 1 I 0 J 1 K
L
ε ε
0
Y
ε
ε
ε
ε
用子集法将NFA 确定化
ε 0 1
X X
T0=X A
A ABFL
T1= ABFL Y CG
Y Y
CG CGJ
T2= Y
T3= CGJ DH K
DH DH
K ABFKL
T4= DH EI
EI ABEFIL
T5= ABFKL Y CG
T6= ABEFIL EJY CG
EJY ABEFGJLY
T7= ABEFGJLY EHY CGK
EHY ABEFHLY
CGK ABCFGJKL
T8= ABEFHLY EY CGI
EY ABEFLY
CGI CGJI
T9= ABCFGJKL DHY CGK
DHY DHY
T10= ABEFLY EY CG
T11= CGJI DHJ K
DHJ DHJ
T12= DHY EI
T13= DHJ EIK
EIK ABEFIKL
T14= ABEFIKL EJY CG
将T0、T1、T2、T3、T4、T5、T6、T7、T8、T9、T10、T11、T12、T13、T14重新命名，分别
用0、
1、2、3、4、5、6、7、8、9、10、11、12、13、14 表示。因为2、7、8、10、12 中含有Y，
所以它们都为终态。
0 1
0 1
1 2 3
2
3 4 5
4 6
5 2 3
6 7 3
7 8 9
8 10 11
9 12 9
10 10 3
11 13 5
12 6
13 14
14 7 3
0 1 0
12
1 2
7
10 8
3
4
5
6
9
11 13 14
1
1
0
1
0
1
0
1
1
0
1
1
0
1
0
1
0 1
0
1
0
1
(3) 先构造NFA：
先构造NFA：
X a A
ε B
a,b
ε
D a E a F
C
ε
Y
ε
ε
b
ε
b
用子集法将NFA 确定化
ε a b
X X
T0=X A
A ABCD
T1=ABCD BE BY
BE ABCDE
BY ABCDY
T2=ABCDE BEF BEY
BEF ABCDEF
BEY ABCDEY
T3=ABCDY BE BY
T4=ABCDEF BEF BEY
T5=ABCDEY BEF BEY
将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5 表示。因为3、5 中含有
Y，
所以它们都为终态。
a b
0 1
1 2 3
2 4 5
3 2 3
4 4 5
5 4 5
0 a 1 b 3
2
a
5
a 4
b
a
b
a
b
a
b
(4) 先构造NFA：
X A
b
ε B
a
F b G b H
E
ε
Y
a
ε
C D b ε
I b
ε
ε
ε
ε
用子集法将NFA 确定化：
ε a b
X X
T0=X A
A ABDEF
T1=ABDEF CI G
CI CI
G G
T2=CI DY
DY ABDEFY
T3=G H
H ABEFH
T4=ABDEFY CI G
T5=ABEFH CI G
将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5 表示。因为4 中含有Y，
所以它为终态。
a b
0 1
1 2 3
2 4
3 5
4 2 3
5 2 3
DFA 的状态图：
0 b 1 b
2
a
4
5
3
b
b
a
b
a
b
第２题
已知NFA＝（｛x,y,z｝,{0,1},M,{x},{z}），其中：M(x,0)={z}，M(y,0)={x,y}，,M(z,0)={x,z}，
M(x,1)={x}，M(y,1)=φ，M(z,1)={y}，构造相应的DFA。
答案：
先构造其矩阵
0 1
x z x
y x,y
z x,z y
用子集法将NFA 确定化：
0 1
x z x
z xz y
xz xz xy
y xy
xy xyz x
xyz xyz xy
将x、z、xz、y、xy、xyz 重新命名，分别用A、B、C、D、E、F 表示。因为B、C、F
中含有z，所以它为终态。
0 1
A B A
B C D
C C E
D E
E F A
F F E
DFA 的状态图：
A
0 1
0
F
E
D
0
B
1
0
1
0
1
0
1
C
第3 题
将下图确定化：
答案：
用子集法将NFA 确定化：
. 0 1
S VQ QU
VQ VZ QU
QU V QUZ
VZ Z Z
V Z .
QUZ VZ QUZ
Z Z Z
重新命名状态子集，令VQ 为A、QU 为B、VZ 为C、V 为D、QUZ 为E、Z 为F。
. 0 1
S A B
A C B
B D E
C F F
D F .
E C E
F F F
DFA 的状态图：
第4 题
将下图的（a）和（b）分别确定化和最小化：
答案：
初始分划得
Π0：终态组{0}，非终态组{1,2,3,4,5}
对非终态组进行审查：
{1,2,3,4,5}a {0,1,3,5}
而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5}
∵{4} a {0}，所以得到新分划
Π1：{0}，{4}，{1,2,3,5}
对{1,2,3,5}进行审查：
∵{1,5} b {4}
{2,3} b {1,2,3,5}，故得到新分划
Π2：{0}，{4}，{1, 5}，{2,3}
{1, 5} a {1, 5}
{2,3} a {1,3}，故状态2 和状态3 不等价，得到新分划
Π3：{0}，{2}，{3}，{4}，{1, 5}
这是最后分划了
最小DFA：
第5 题
构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1 都有0 直接跟在
右边。并给出该语言的正规式。
答案：
按题意相应的正规表达式是(0*10)*0*，或0*(0 | 10)*0* 构造相应的DFA，首先构造NFA 为
用子集法确定化：
I I0 I1
{X,0,1,3,Y}
{0,1,3,Y}
{2}
{1,3,Y}
{0,1,3,Y}
{0,1,3,Y}
{1,3,Y}
{1,3,Y}
{2}
{2}
{2}
重新命名状态集：
S 0 1
1
2
3
4
2
2
4
4
3
3
3
DFA 的状态图：
可将该DFA 最小化：
终态组为{1,2,4}，非终态组为{3}，{1,2,4}0 {1,2,4}，{1,2,4}1 {3}，所以1,2,4 为等价状
态，可合并。
第６题
设无符号数的正规式为θ：
θ=dd*|dd*.dd*|.dd*|dd*10(s|ε)dd*
|10(s|ε)dd*|.dd*10(s|ε)dd*
|dd*.dd*10(s|ε)dd*
化简θ，画出θ的DFA，其中d={0,1,2,…,9}，s={＋，－}
答案：
先构造NFA：
X
d
. B
d
F G
d
H
10
d
A
ε
C
10
d
D
s
ε
E d
Y
d
s
ε
d
用子集法将NFA 确定化：
ε • s 10 d
X XA
T0=XA B F A
B B
F FG
A A
T1=B C
C C
T2=FG G H
G G
H H
T3=A B F A
T4=C D C
D DE
T5=G H
T6=H H
T7=DE E Y
E E
Y Y
T8=E Y
T9=Y Y
将XA、B、FG、A、C、G、H、DE、E、Y 重新命名，分别用0、1、2、3、4、5、6、
7、8、9 表示。终态有0、3、4、6、9。
• s 10 d
0 1 2 3
1 4
2 5 6
3 1 2 3
4 7 4
5 6
6 6
7 8 9
8 9
9 9
DFA 的状态图：
•
d
6
2 5
d
3
d
d
4 7
8
9
0
1
10
d
s
•
10
10
d
d
s
d
d
d
第7 题
给文法G[S]：
S→aA|bQ
A→aA|bB|b
B→bD|aQ
Q→aQ|bD|b
D→bB|aA
E→aB|bF
F→bD|aE|b
构造相应的最小的DFA。
答案：
先构造其NFA：
S
a
A
a
Z
Q
b
B
D
a
E
b
F
b
b
a
b
a
a
b
b b
b
a
b
用子集法将NFA 确定化：
a b
S A Q
A A BZ
Q Q DZ
BZ Q D
DZ A B
D A B
B Q D
将S、A、Q、BZ、DZ、D、B 重新命名，分别用0、1、2、3、4、5、6 表示。因为3、
4 中含有z，所以它们为终态。
a b
0 1 2
1 1 3
2 2 4
3 2 5
4 1 6
5 1 6
6 2 5
DFA 的状态图：
0
a
a
5
2
b
3
a
a
b
4
1
6
b
a
a
b
b
b
a
b
令P0＝（｛0,1,2,5,6｝,｛3,4｝）用b进行分割：
P1＝（｛0,5, 6｝,｛1,2｝,｛3,4｝）再用b进行分割：
P2＝（｛0｝,｛5, 6｝,｛1,2｝,｛3,4｝）再用a、b 进行分割，仍不变。
再令｛０｝为A，｛1，2｝为B，｛3，4｝为C，｛5，6｝为D。
最小化为：
A
a , b
D C
a
a
B
b
a
b
b
第８题
给出下述文法所对应的正规式：
S→0A|1B
A→1S|1
B→0S|0
答案：
解方程组S 的解：
S=0A|1B
A=1S|1
B=0S|0
将A、B 产生式的右部代入S 中
S=01S|01|10S|10=（01|10）S|（01|10）
所以：S= (01|10)*(01|10)
第9 题
将下图的DFA 最小化，并用正规式描述它所识别的语言。
1
a
2
6
c
3
c
b
5
4 7
b
b
a b
b
b
d
d
a
答案：
令P0＝（｛1,2,3,4,5｝,｛6,7｝）用b进行分割：
P1＝（｛1,2｝,｛3,4｝,｛5｝,｛6,7｝）再用a、b、c、d进行分割，仍不变。
再令｛1,2｝为A，｛3，4｝为B，｛5｝为C，｛6，7｝为D。
最小化为：
A
a
C D
b
d
B
b
c
a
b
r=b*a(c|da)*bb*=b*a(c|da)*b+
《编译原理》课后习题答案第五章
第1 题
对文法G[S]
S→a|∧|(T)
T→T,S|S
(1) 给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。
(2) 对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。
(3) 经改写后的文法是否是LL(1)的?给出它的预测分析表。
(4) 给出输入串(a,a)#的分析过程，并说明该串是否为G 的句子。
答案：
(1) 对(a,(a,a)的最左推导为：
S (T)
(T,S)
(S,S)
(a,S)
(a,(T))
(a,(T,S))
(a,(S,S))
(a,(a,S))
(a,(a,a))
对(((a,a),∧,(a)),a) 的最左推导为：
S (T)
(T,S)
(S,S)
((T),S)
((T,S),S)
((T,S,S),S)
((S,S,S),S)
(((T),S,S),S)
(((T,S),S,S),S)
(((S,S),S,S),S)
(((a,S),S,S),S)
(((a,a),S,S),S)
(((a,a),∧,S),S)
(((a,a),∧,(T)),S)
(((a,a),∧,(S)),S)
(((a,a),∧,(a)),S)
(((a,a),∧,(a)),a)
(2) 改写文法为：
0) S→a
1) S→∧
2) S→( T )
3) T→S N
4) N→, S N
5) N→ε
非终结符 FIRST 集 FOLLOW 集
S {a,∧,(} {#,,,)}
T {a,∧,(} {)}....
N {,,ε}. {)}....
对左部为N 的产生式可知：
FIRST （→, S N）={，}
FIRST （→ε）={ε}
FOLLOW （N）={)}
由于SELECT(N →, S N)∩SELECT(N →ε) ={，}∩ { )}=
所以文法是LL(1)的。
预测分析表（Predicting Analysis Table）
a ∧ ( ) , #
S →a →∧ →(T)
T →S N →S N →S N
N →ε →, S N
也可由预测分析表中无多重入口判定文法是LL(1)的。
(3) 对输入串（a,a）#的分析过程为：
栈（STACK）
当前输入符
（CUR_CHAR）
剩余输入符
（INOUT_STRING）
所用产生式
（OPERATION）
#S
#)T(
#)T
#)NS
#)Na
#)N
#)NS,
#)NS
#)Na
#)N
#)
#
(
(
a
a
a
,
,
a
a
)
)
#
a,a)#...
a,a)#...
,a)#...
,a)#...
,a)#...
a)#...
a)#...
)#...
)#...
#...
#...
S→(T)
.
T→SN
S→a
.
N→,SN
.
S→a
.
N→ε
可见输入串（a,a）#是文法的句子。
第3 题
已知文法G[S]：
S→MH|a
H→LSo|ε
K→dML|ε
L→eHf
M→K|bLM
判断G 是否是LL(1)文法，如果是，构造LL(1)分析表。
答案：
文法展开为：
0） S→M H
1） S→a
2） H→L S o
3） H→ε
4） K→d M L
5） K→ε
6） L→e H f
7） M→K
8） M→b L M
非终结符 FIRST 集 FOLLOW 集
S {a,d,b,ε,e} {#,o}........
M {d,ε,b}.... {e,#,o}......
H {ε,e}...... {#,f,o}......
L {e}......... {a,d,b,e,o,#}
K {d,ε}...... {e,#,o}......
对相同左部的产生式可知：
SELECT(S→M H)∩SELECT(S→a) ={ d,b ,e，#,o }∩ { a }=
SELECT(H→L S o)∩SELECT(H→ε) ={ e }∩ { #,f,o }=
SELECT(K→d M L)∩SELECT(K→ε) ={ d }∩ { e,#,o }=
SELECT(M→K)∩SELECT(M→b L M) ={ d，e,#,o }∩ { b }=
所以文法是LL(1)的。
预测分析表：
a o d e f b #
S →a →MH →MH →MH →MH →MH
M →K →K →K →bLM →K
H →ε →LSo →ε →ε
L →eHf
K →ε →dML →ε →ε
由预测分析表中无多重入口也可判定文法是LL(1)的。
第7 题
对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法?试对下面
文法进行改写，并对改写后的文法进行判断。
(１)A→baB|ε
B→Abb|a
(2) A→aABe|a
B→Bb|d
(3) S→Aa|b
A→SB
B→ab
答案：
(１)先改写文法为：
0) A→baB
1) A→ε
2) B→baBbb
3) B→bb
4) B→a
再改写文法为：
0) A→baB
1) A→ε
2) B→bN
3) B→a
4) N→aBbb
5) N→b
FIRST FOLLOW
A {b} {#}
B {b,a} {#,b}
N {b,a} {#,b }
预测分析表：
a b #
A →baB →ε
B →a →bN
N →aBbb →b
由预测分析表中无多重入口判定文法是LL(1)的。
（2） 文法：
A→aABe|a
B→Bb|d
提取左公共因子和消除左递归后文法变为：
0) A→a N
1) N→A B e
2) N→ε
3) B→d N1
4) N1→b N1
5) N1→ε
非终结符 FIRST 集 FOLLOW 集
A {a}... {#,d}
B {d}... {e}..
N {a,ε} {#,d}
N1 {b,ε} {e}..
对相同左部的产生式可知：
SELECT(N→A B e)∩SELECT(N→ε) ={ a }∩ {#,d }=
SELECT(N1→b N1)∩SELECT(N1→ε) ={ b }∩ { e }=
所以文法是LL(1)的。
预测分析表（Predicting Analysis Table）
a e b d #
A →a N
B →d N1
N1 →ε →b N1
N →ABe →ε →ε
也可由预测分析表中无多重入口判定文法是LL(1)的。
（3）文法：
S→Aa|b
A→SB
B→ab
第1 种改写：
用A 的产生式右部代替S 的产生式右部的A 得：
S→SBa|b
B→ab
消除左递归后文法变为：
0) S→b N
1) N→B a N
2) N→ε
3) B→a b
非终结符 FIRST 集 FOLLOW 集
S {b}... {#}
B {a}... {a}
N {ε,a} {#}
对相同左部的产生式可知：
SELECT(N→B a N)∩SELECT(N→ε) ={ a }∩ {# }=
所以文法是LL(1)的。
预测分析表（Predicting Analysis Table）
a b #
S →b N
B →a b
N →B a N →ε
也可由预测分析表中无多重入口判定文法是LL(1)的。
第2 种改写：
用S 的产生式右部代替A 的产生式右部的S 得：
S→Aa|b
A→AaB|bB
B→ab
消除左递归后文法变为：
0) S→A a
1) S→b
2) A→b B N
3) N→a B N
4) N→ε
5) B→a b
非终结符 FIRST 集 FOLLOW 集
S {b}... {#}
A {b}... {a}
B {a}... {a}
N {a,ε} {a}
SELECT(S→A a)∩SELECT(S→b) ={ b }∩ { b }={ b }≠
SELECT(N→a B N)∩SELECT(N→ε) ={ a }∩ { a }={ a }≠
所以文法不是LL(1)的。
预测分析表：
a b #
S →A a..
→b....
A →b B N
B →a b..
N →a B N
→ε...
也可由预测分析表中含有多重入口判定文法不是LL(1)的。
发布评论