编译原理教程课后习题答案

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. 解答： *

它所接受的语言可以用正则表达式表示为00(0|1)，表示的含义为由两个0开始的后跟任意个（包含0个）0或1组成的符号串的集合。 2. 解答：a:④b:③c:②d:② e: ④ 3，4．解答：略！ 5．解答： 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 (k0），|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. 解答： 9. 解答：

(1) dfa m=({0，1}，{q0，q1，q2}，q0，{q2}，?) 其中?定义如下:

? (q0，0)=q1 ? (q0，1)=q0 ? (q1，0)=q2 ? (q1，1)=q0 ? (q2，0)=q2 ? (q2，1)=q0 状态转换图为：

(2) 正规式: 1010101

dfa m=({0，1}，{q0，q1，q2，q3}，q0，{q3}，?)，其中?定义如下：

? (q0，0)=q1 ? (q0，1)=q0 ? (q1，0)=q2 ? (q1，1)=q1 ? (q2，0)=q3 ? (q2，1)=q2 ? (q3，1)=q3状态转换图为： ****

10. 解答：

(1) dfa m=({0，1}，{q0，q1，q2，q3}，q0，{q3}，?)，其中?定义如下：

? (q0，0)=q1 ? (q0，1)=q2 ? (q1，0)=q1 ? (q1，1)=q3 ? (q2，0)=q3 ? (q2，1)=q1 状态转换图为：