第1页 / 共23页
第2页 / 共23页
第3页 / 共23页
第4页 / 共23页
第5页 / 共23页
第6页 / 共23页
第7页 / 共23页
第8页 / 共23页
编译原理及实践教程(黄贤英_王柯柯_编著)_习题答案.doc
第2章参考答案：
第3章习题解答：
第4章习题解答：
第5章习题解答：
第6章习题解答：
第 2 章参考答案：
1，2，3：解答：略！
4. 解答：
A：① B：③ C：① D：②
5. 解答：
用 E 表示<表达式>，T 表示<项>，F 表示<因子>，上述文法可以写为：
E → T | E+T
T → F | T*F
F → (E) | i
最左推导：
E=>E+T=>E+T+T=>T+T+T=>F+T+T=>i+T+T=>i+F+T=>i+i+T
=>i+i+F=>i+i+i
E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i
最右推导：
E=>E+T=>E+F=>E+i=>E+T+i=>E+F+i=>E+i+i=>T+i+i
=>F+i+i=>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
i+i+i 和 i+i*i 的语法树如下图所示。
i+i+i、i+i*i 的语法树
6. 解答：
(1) 终结符号为：{or,and,not,(,),true,false}
非终结符号为：{bexpr,bterm,bfactor}
开始符号为：bexpr
(2) 句子 not(true or false)的语法树为：
7. 解答：
(1) 把 anbnci 分成 anbn 和 ci 两部分，分别由两个非终结符号生成，因此，生成此文法的
产生式为：
S → AB
A → aAb|ab
B → cB|
(2) 令 S 为开始符号，产生的 w 中 a 的个数恰好比 b 多一个，令 E 为一个非终结符号，
产生含相同个数的 a 和 b 的所有串，则产生式如下：
S → aE|Ea|bSS|SbS|SSb
E → aEbE|bEaE|
(3) 设文法开始符号为 S，产生的 w 中满足|a|≤|b|≤2|a|。因此，可想到 S 有如下的产生
式 （其中 B 产生 1 到 2 个 b）：
S → aSBS|BSaS
B → b|bb
(4) 解法一：
S →〈奇数头〉〈整数〉〈奇数尾〉
|〈奇数头〉〈奇数尾〉
|〈奇数尾〉
〈奇数尾〉→ 1|3|5|7|9
〈奇数头〉→ 2|4|6|8|〈奇数尾〉
〈整数〉→ 〈整数〉〈数字〉|〈数字〉
〈数字〉→ 0|〈奇数头〉
解法二：文法 G=({S,A,B,C,D},{0,1,2,3,4,5,6,7,8,9},P,S)
S→AB | B
A→AC | D
B→1|3|5|7|9
D→2|4|6|8|B
C→0|D
(5) 文法 G=({N,S,N,M,D},{0,1,2,3,4,5,6,7,8,9 },S,P)
S→N0 | N5
N→MD|
M→1|2|3|4|5|6|7|8|9
D→D0 | DM |
(6) G[S]：S→aSa | bSb | cSc | a | b | c |
8. 解答：
(1) 句子 abab 有如下两个不同的最左推导：
S => aSbS => abS =>abaSbS => ababS => abab
S => aSbS => abSaSbS => abaSbS => ababS => abab
所以此文法是二义性的。
(2) 句子 abab 的两个相应的最右推导：
S => aSbS => aSbaSbS => aSbaSb => aSbab => abab
S => aSbS => aSb => abSaSb => abSab => abab
(3) 句子 abab 的两棵分析树：
(a)
(b)
(4) 此文法产生的语言是：在{a，b}上由相同个数的 a 和 b 组成的字符串。
9，10：解答：略！
第 3 章习题解答：
1. 解答：
(1) √ (2) √ (3) × (4) × (5) √ (6) √
2. [分析]
有限自动机分为确定有限自动机和非确定有限自动机。确定有限自动机的确定性表现
在映射：Q×VT -->q 是单值函数，也就是说，对任何状态 q∈Q 和输入字符串 a∈VT， (q,a)
唯一确定下一个状态。显然，本题给出的是一个确定的有限自动机，它的状态转换图是 C
中的②。
它所接受的语言可以用正则表达式表示为 00(0|1)*，表示的含义为由两个 0 开始的
后跟任意个（包含 0 个）0 或 1 组成的符号串的集合。
2. 解答：A:④
3，4．解答：略！
5．解答：
D:②
E: ④
B:③
C:②
6．解答：
(1) (0|1)*01
(2) ((1|2|…|9)(0|1|2|…|9)*| )(0|5)
(3) (0|1)*(011)(0|1)*
(4) 1*|1*0(0|10)*(1|)
(5) a*b*c*…z*
(6) (0|10*1)*1
(7) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
(8) [分析]
设 S 是符合要求的串，|S|=2k+1 (k≥0）。
则 S→S10|S21，|S1|=2k (k>0），|S2|=2k (k≥0）。
且 S1 是{0,1}上的串，含有奇数个 0 和奇数个 1。
S2 是{0,1}上的串，含有偶数个 0 和偶数个 1。
考虑有一个自动机 M1 接受 S1，那么自动机 M1 如下：
和 L(M1)等价的正规式，即 S1 为：
((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*
类似的考虑有一个自动机 M2 接受 S2，那么自动机 M2 如下：
和 L(M2)等价的正规式，即 S2 为：
((00|11)|(01|10)(00|11)*(01|10))*
因此，S 为：
((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*0|
((00|11)|(01|10)(00|11)*(01|10))*1
7．解答：
(1) 以 0 开头并且以 0 结尾的，由 0 和 1 组成的符号串。
(2) {|∈{0,1}*}
(3) 由 0 和 1 组成的符号串，且从右边开始数第 3 位为 0。
(4) 含 3 个 1 的由 0 和 1 组成的符号串。{|∈{0,1}+，且中含有 3 个 1 }
(5) 包含偶数个 0 和 1 的二进制串，即{|∈{0,1}*，且中有偶数个 0 和 1}
8. 解答：
0
Q2
Q3
Q0
Q1
1
Q1
Q0
Q3
Q2
Q0*
Q1
Q2
Q3
9. 解答：
(1) DFA M=({0，1}，{q0，q1，q2}，q0，{q2}，)
其中定义如下:
(q0，0)=q1
(q1，0)=q2
(q2，0)=q2
状态转换图为：
(q0，1)=q0
(q1，1)=q0
(q2，1)=q0
(2) 正规式: 1*01*01*01*
DFA M=({0，1}，{q0，q1，q2，q3}，q0，{q3}，)，其中定义如下：
(q0，0)=q1
(q1，0)=q2
(q2，0)=q3
(q3，1)=q3
状态转换图为：
(q0，1)=q0
(q1，1)=q1
(q2，1)=q2
10. 解答：
(1) DFA M=({0，1}，{q0，q1，q2，q3}，q0，{q3}，)，其中定义如下：
(q0，0)=q1
(q1，0)=q1
(q2，0)=q3
状态转换图为：
(q0，1)=q2
(q1，1)=q3
(q2，1)=q1
(2) DFA M=({0，1}，{q0}，q0，{q0}，)，其中定义如下:
(q0，0)=q0
状态转换图为：
(q0，1)=q0
11 解答：
(1) (a|b)*a(a|b)
① 求出 NFA M:
②确定化，得到 DFA M:
③化简: 在第②步中求出的 DFA M 中没有等价状态，因此它就是最小化的 DFA M。
(2) (a)b)*a(a|b)(a|b)
① 求 NFA M：
② 确定化，得到 DFA M：
③化简，在第②步中求出的 DFA M 中没有等价状态，因此它已经是最小化的 DFA M 了。
12.解答：
对应的 NFA 为：
增加状态 X、Y，再确定化：
I
{x,5}
{A,T,Y}
{B}
{B,T,Y}
{T,Y}
Ia
{A,T,Y}
{A,T,Y}
{
{
{
}
}
}
Ib
{
{B}
}
{B,T,Y}
{T,Y}
{
}
得到的 DFA 为：
最小化：该自动机已经是最小化的 DFA 了。
13．解答：
其中 a 代表 1 元硬币，b 代表 5 角硬币
14．解答：
正规式为：(0|1)*(00|01) 化简：(0|1)*0(0|1)
不确定的有穷自动机为：
确定化，并最小化得到：
正规文法为：
S→1S | 0A
A→0B | 0 | 1C | 1
B→0B | 0 | 1C | 1
C→1S | 0A
15.解答：
① 正规式：(dd*:| )dd*(.dd*| )，d 代表 a~z 的字母
② NFA 为：
③ DFA 为：
16.解答：
词法分析器对源程序采取非常局部的观点，因此象 C 语言的语句
fi (a == f (x) ) …
中，词法分析器把 fi 当作一个普通的标识符交给编译的后续阶段，而不会把它看成是关键
字 if 的拼写错。
PASCAL 语言要求作为实型常量的小数点后面必须有数字，如果程序中出现小数点后面
没有数字情况，它由词法分析器报错。
17. 解答：
此时编译器认为
/* then part
return q
else
/* else part */
是程序的注释，因此它不可能再发现 else 前面的语法错误。
分析 这是注释用配对括号表示时的一个问题。注释是在词法分析时忽略的，而词法分
析器对程序采取非常局部的观点。当进入第一个注释后，词法分析器忽略输入符号，一直到
出现注释的右括号为止，由于第一个注释缺少右括号，所以词法分析器在读到第二个注释的
右括号时，才认为第一个注释处理结束。
为克服这个问题，后来的语言一般都不用配对括号来表示注释。例如 Ada 语言的注释
相关推荐
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
