编译原理答案++陈意云+高等教育出版社

1、编译原理习题参考答案（一）zpli 2004-3-7version 1.1Page 1 of 7编译原理习题参考答案（一）编译原理习题参考答案（一）Bug report:.c nOr find:电一楼二楼全球计算实验室李兆鹏第二章2.3叙述由下列正规式描述的语言a) 0(0| 1)*0b) (技)1*)*c) (0|1)*0(0|1)(0|1)d) 0*10*10*10*e) (00|11)*(01|10)(00|11)*(01|10)(00|11)*)*An swer:a）以0开始和结尾，而且长度大于等于2的0、1串b）所有0,1串（含空串）c）倒数第三位是

2、0的0、1串d）仅含3个1的0、1串e）偶数个0和偶数个1的0、1串（含空串）2.4为下列语言写出正规定义：f）由偶数个0和偶数个1构成的所有0和1的串g）由偶数个0和奇数个1构成的所有0和1的串An swer:标准答案见 编译原理习题精选P1-P2 1.1 &1.2 题给出它们处理输入串ababbab的2.7用算法2.4为下列正规式构造非确定的有限自动机,转换序列c) ( e|a ) b*) d)(a|b)*abb(a|b)*An swer:c)NFA :输入串ababbab的转换序列：0 1456789 145678 789 1456789 10Or 0 1456789 14567

3、89 1236789 1456789 10d) NFA:eezpli 2004-3-7version 1.1Page 3 of 7编译原理习题参考答案（一）zpli 2004-3-7version 1.1Page # of 7编译原理习题参考答案（一）输入串ababbab的转换序列：0 1236 1456 789 10 11 12 13 16 11 14 15 16 172.8用算法2.2把习题2.7的NFA变换成DFA。给出它们处理输入串ababbab的状态转 换序列。An swer:/针对 2.7 (c)zpli 2004-3-7version 1.1Page # of 7编译原理习题参考

4、答案（一）zpli 2004-3-7version 1.1Page # of 7编译原理习题参考答案（一）3个不同的状态集合：A = 0, 1,2, 3, 4, 6, 7, 9, 10B = 1,2, 3, 4, 5, 6, 7, 9, 10C = 1,2, 3, 4, 6, 7, 8, 9, 10NFA的转换表：子集构造法应用于状态输入符号a bA BCB BCC BCzpli 2004-3-7version 1.1Page # of 7编译原理习题参考答案(一)2.11我们可以从正规式的最简DFA同构来证明两个正规式等价。使用这种技术，证明下面正规式等价。(a) (a|b)*(b) (a*

5、|b*)*(c) (£|a)b*)*An swer:(c ) NFA见2.7 (c)用子集构造法化简得DFA见2.8。最简的DFA为:Startzpli 2004-3-7version 1.1Page 5 of 7编译原理习题参考答案(一)zpli 2004-3-7version 1.1Page # of 7编译原理习题参考答案(一)同理可求出(b)正规式对应的最简 DFA亦是如此，故(b)(c) 等价。2.15修改算法2.4,使之尽可能少使用&转换，并保持所产生的NFA只有一个接收状态An swer:算法.4改进(a)N(s)N(t)开始状态合并作为N(s|t)的开始状态N

6、(s)N(t)接受状态合并作为N(s|t)的接受状态(C)N(s)开始状态与接受状态合并成一个状态j。start izpli 2004-3-7version 1.1Page # of 7编译原理习题参考答案(一)zpli 2004-3-7version 1.1Page # of 7编译原理习题参考答案(一)注意：必须保留一个i和f,否则可能在算法递归产生NFA过程中会出问题zpli 2004-3-7version 1.1Page # of 7编译原理习题参考答案(一)zpli 2004-3-7version 1.1Page # of 7编译原理习题参考答案(一)第三章3.2考虑文法S aSbS

7、 | bSaS |£(a) 为句子abab构造两个不同的最左推导，以此说明该文法是二义的(b) 为abab构造对应的最右推导。(c) 为abab构造对应的分析树。(d) 这个文法产生的语言是什么？An swer:S? Im aSbSS ? Im aSbS? Im abS? Im abSaSbS? Im abaSb S? Im abaSbS? Im ababS? Im ababS? Im abab - CD? Imabab-可知，对于句子abab存在两个不 冋的最左推导， 所以该文法是二义的(b)(d )；?rm aSbS?rmaSb?rmabSaS b?rmabSab?rmabab(

8、c )I?rm aSbS?rmaSbaSbS?rmaSbaSb?rmaSbab?rmabab该文法产生a、b个数相等的ab串(含空串)3.4文法R>R | ' R | RR | R* | (R) | a | b产生字母表a,b上所有不含&的正规式。注意，第一条竖线是正规式的符号“或”，而 不是文法产生式右部各选择之间的分隔符，另外“*”在这儿是一个普通的终结符。该文法是二义的。(b) 为该文法写一个等价的非二义的文法。它给予算符*、链接和|的优先级和结合性同2.2节中定义的一致。(c) 按上面两个文法构造句子ab|b*a 的分析树。An s wer:(b) 标准答案见编译

9、原理习题精选P17(c) 原文法的分析树：/文法二义，存在多个分析树Rbbzpli 2004-3-7version 1.1Page 7 of 7编译原理习题参考答案(一)zpli 2004-3-7version 1.1Page # of 7编译原理习题参考答案(一)无二义文法的分析树zpli 2004-3-7version 1.1Page # of 7编译原理习题参考答案(一)zpli 2004-3-7version 1.1Page # of 7编译原理习题参考答案(一)zpli 2004-3-7version 1.1Page # of 7编译原理习题参考答案（一）3.6为字母表a,b上的下列

10、每个语言设计一个文法，其中哪些语言是正规的?(a) 每个a后面至少有一个b跟随的所有串(b) a和b的个数相等的所有串An swer: S abS| bS |£该语言是正规，对应的正规式是(ab|b)*(b) 解法一：S aSbS | bSaS |£解法二：S -aB | bA |£A aS | bAAB 侮 | aBB解法三：S -abS | aSb | Sab | baS | bSa | Sba |该文法不是正规的。3.8(a)消除习题3.1文法的左递归(b)为(a)的文法构造预测分析器An swer: S (L) | aLS L1+L1 ，&

11、3;(b)上述文法的预测分析器为： procedure match(t:toke n);beginif lookahead = t the n lookahead := n exttoke n()else error() en d;procedure s;beginif lookahead = (' thenbeginmatch( (' ); L(); match( ')') endelse if lookahead = a' thenmatch( a')else error()en d;procedure L;beginS()；L1()en d;procedure L1;beginif lookahead =, ' thenbeginmatch( , ' ); S(); L1()e