第1页 / 共28页
第2页 / 共28页
第3页 / 共28页
第4页 / 共28页
第5页 / 共28页
第6页 / 共28页
第7页 / 共28页
第8页 / 共28页
《编译原理》陈火旺第三版课后习题答案.pdf
第二章
P-36-6
（1）L（G）是 0~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
P-36-7
G（S）：（没有考虑正负符号问题）
S→P|AP
P→1|3|5|7|9
A→AD|N
N→2|4|6|8|P
D→0|N
或者：（１）S→ＡＢＣ｜C
Ａ→１｜２｜３｜４｜５｜６｜７｜８｜９
Ｂ→ＢＡ｜Ｂ０｜ε
Ｃ→1｜3｜5｜7｜9
P-36-8
G（E）：E→T|E+T|E-T
T→F|T*F|T/F
F→（E）|i
最左推导：
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）
1
课后答案网 www.khdaw.com
T
*
F
i
E
+
T
F
i
i+i*i
S
i
S
e
i
S
i
S
i
E
T
F
i
E
-
E
-
T
F
i
i-i-i
S
i
S
T
F
i
i
e
S
i
S
i
语法树：
E
+
T
F
i
E
+
i+i+i
E
T
F
i
T
F
i
E
T
F
i
P-36-9
句子：iiiei 有两个语法树：
S⇒iSeS⇒iSei⇒iiSei⇒iiiei
S⇒iS⇒iiSeS⇒iiSei⇒iiiei
因此 iiiei 是二义性句子，因此
该文法是二义性的。
P-36-10
S→TS|T
T→(S)|()
P-36-11
L1: G(S): S→AC
A→aAb|ab
C→cC|ε
L2: G(S): S→AB
A→aA|ε
B→bBc|bc
L3: G(S): S→AB
A→aAb|ε
B→aAb|ε
L4: G(S): S→1S0|A
A→0A1|ε
或者：S→A|B A→0A1|ε B→1B0|A
2
课后答案网 www.khdaw.com
（1）
X
X
1（0|1）*101
1
1
Y
ε
0
2
1
确定化：
{X}
Φ
{1，2，3}
{2，3}
{2，3，4}
{2，3，5}
{2，3，4，Y}
第三章
ε
1
0
4
3
1
5
Y
1
{1，2，3}
Φ
{2，3，4}
{2，3，4}
{2，3，4}
{2，3，4，Y}
{2，3，4}
0
Φ
Φ
{2，3}
{2，3}
{2，3，5}
{2，3}
{2，3，5}
0
1
2
1
1
1
0
0
0
0
3
1
4
1
0
0
1
0
5
1
6
最小化：{0，1，2，3，4，5}，{6}
{0，1，2，3，4，5}0={1，3，5} {0，1，2，3，4，5}1={1，2，4，6}
{0，1，2，3，4}，{5}，{6}
{0，1，2，3，4}0={1，3，5}
{0，1，2，3}，{4}，{5}，{6}
{0，1，2，3}0={1，3} {0，1，2，3}1={1，2，4}
{0，1}，{2，3}，{4}，{5}，{6}
{0，1}0={1} {0，1}1={1，2} {2，3}0={3} {2，3}1={4}
{0}，{1}，{2，3}，{4}，{5}，{6}
3
课后答案网 www.khdaw.com
0
2
1
3
0
0
0
0
0
1
1
1
1
（0|1）*01
1
0
4
1
5
（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*（0|5）|（0|5）
0*1（0|10*1）* | 1*0（1|01*0）*
P64-8
(1)
(2)
(3)
P84-12
（a）
a
0
确定化：
a，b
a
1
{0}
{0,1}
{1}
Φ
给状态编号：
0
1
2
3
a
{0,1}
{0,1}
{0}
Φ
a
1
1
0
3
b
{1}
{1}
Φ
Φ
B
2
2
3
3
4
课后答案网 www.khdaw.com
a
1
b
b
0
a
a
b
2
最小化：
{0，1} {2，3}
{0，1}a={1}，{0，1}b={2}
{2，3}a={0，3}，{2，3}={3}
{0，1}，{2}，{3}
b
3
a
a
0
b
a
b
1
a
2
b
（b）
已经确定化，只需最小化：
{0，1}，{2，3，4，5}
{0，1}a = {1} {0，1}b = {2，4}
{2，3，4，5}a = {1，3，0，5} {2，3，4，5}b = {2，3，4，5}
又：{2，4}a = {1，0} {2，4}b = {3，5} {3，5}a={3，5} {3，5}b = {2，4}
分划为：{0，1}，{2，4}，{3，5}
{0，1}a = {1} {0，1}b = {2，4}
{2，4}a = {1，0} {2，4}b = {3，5}
{3，5}a = {3，5} {3，5}b = {2，4}
所以不能再分
a
0
b
a
1
b
b
a
2
5
课后答案网 www.khdaw.com
P64-14
正规式：（0|10）*
0
0
1
0
还可以：
ε
X
1
1
0
1
2
0
ε
然后再确定化，最小化，结果应该一样。
P65-15
首先构造 NFA：
1
1
S
0
0
A
1
0
B
0
C
1
0
1
1
0
则有：G（f） f→A1|B0|C1|C0
C→C0|C1|A1|B0
A→S1|1
B→S0|0
S→S0|S1|
或者是确定化，然后最小化：
0|1
S
0
1
A
1
0
B
0
1
G（C） C→C0|C1|A0|B1
A→0|B0
B→1|A1
0，1
C
Y
f
6
课后答案网 www.khdaw.com
人、狼、羊、白菜：
{{M、W、G、C}，{}}表示在左岸，{{}，{M、W、G、C}}在右岸，将可能存在的状态中去掉不安全
状态，剩下：
{}}，{{}，{M、W、G、C}}，{{M、W、G}，{C}}，{{M、W、C}，{G}}，
{{M、W、G、C}，
{{M、G、C}，{W}} ，{{C}，{M、W、G}} ，{{G}，{M、W、C}}，{{W}，{M、G、C}}，
{{M、G}，{W、C}} ，{{W，C}，{M、G}}
箭弧上的标记符：：表示人单独过河、：表示人和羊过河、：表示人和狼过河、：
{ M、C、G }，{{ W }}
{C}，{{M、W、G}}
{{M、W、G、C}，{}}
{{W，C}，{M、G}}
{{M、W、C}，{G}} {{G}，{M、W、C}}
{W}，{{M、G、C}}
{{W、M、G}，{ C}}
{ M、G}，{{ W、 C}}
{{},{M、W、G、C}
7
课后答案网 www.khdaw.com
P81-1
（1） 按照 T，S 的顺序消除左递归
第四章
G'（S）：S→a|⋀|（T）
T→ST'
T'→，ST'|ε
递归下降子程序：
procedure S:
begin
if sym = ‘a’or sym= ‘⋀’
then advance
else if sym=‘（’
then begin
advance；T；
if sym = ‘)’ then advance;
else error;
end
else error
end
procedure T;
begin
S;T'
End
Procedure T';
Begin
If sym = ‘,’
Then begin
Advance;
S;T'
End
End
其中：sysm 为输入串指针所指的符号；advance 是把输入指针调至下一输入符号。
（2） 求 First 和 Follow 集合：
First（S）={a 、 ⋀ 、（} First（T）={a 、 ⋀ 、（} First（T'）={， 、ε}
Follow（S）={ , 、) 、 #} Follow(T) = { ) } Follow(T'）={ ) }
a
⋀
(
S→a
S→⋀
T→ST'
T→ST'
S→(T)
T→ST'
)
,
#
T'→ε
T'→，ST'
S
T
T'
8
课后答案网 www.khdaw.com
相关推荐
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
