编译原理教程第四版答案.docx

1、编译原理教程第四版答案编译原理教程第四版答案【篇一：编译原理教程课后习题答案第三章】.1 完成下列选择题： (1) 文法g：sxsx|y所识别的语言是 a. xyx b. (xyx)* c. xnyxn(n0) d. x*yx* a. 最左推导和最右推导对应的语法树必定相同 b. 最左推导和最右推导对应的语法树可能不同 c. 最左推导和最右推导必定相同 d. 可能存在两个不同的最左推导，但它们对应的语法树相同 (3) 采用自上而下分析，必须。 a. 消除左递 a. 必有ac归 b. 消除右递归 c. 消除回溯 d. 提取公共左因子 (4) 设a、b、c是文法的终结符，且满足优先关系ab和bc，

2、则。 b. 必有ca c. 必有bad. ac都不一定成立 (5) 在规范归约中，用 a. 直接短语b. 句柄 c. 最左素短语 d. 素短语 a. 归约 b. 移进 c. 接受 d. 待约 a. lalr文法 b. lr(0)文法 c. lr(1)文法 d. slr(1)文法 (8) 同心集合并有可能产生新的冲突。 a. 归约 b. “移进”/“移进” c.“移进”/“归约” d. “归约”/“归约” 【解答】 (1) c (2) a (3) c (4) d (5) b (6) b (7) d (8) d 3.2 令文法gn为 gn: nd|nd d0|1|2|3|4|5|6|7|8|9 (

3、1) gn的语言l(gn)是什么? (2) 给出句子0127、34和568的最左推导和最右推导。 【解答】 (1) gn的语言l(gn)是非负整数。 (2) 最左推导： nndnddnddddddd0ddd01dd012d0127 nnddd3d34 nndnddddd5dd56d568 最右推导： nndn7nd7n27nd27n127d1270127 nndn4d434 nndn8nd8n68d68568 3.3 已知文法gs为sasb|sb|b，试证明文法gs为二义文法。【解答】 由文法gs：sasb|sb|b，对句子aabbbb可对应如图3-1所示的两棵语法树。 ss asbsb as

4、basb sbasb bb 图3-1 句子aabbbb对应的两棵不同语法树 因此，文法gs为二义文法(对句子abbb也可画出两棵不同语法树)。 sassas sas?sas ? (a)(b) 图3-2 句子aa对应的两棵不同的语法树 由图3-2可知，文法gs为二义文法。 3.5 按指定类型，给出语言的文法。 (1) l=aibj|ji0的上下文无关文法； (3) 由相同个数a和b组成句子的无二义文法。 【解答】 (1) 由l=aibj|ji0知，所求该语言对应的上下文无关文法首先应有sasb型产生式，以保证b的个数不少于a的个数；其次，还需有ssb或sb型的产生式，用以保证b的个数多于a的个数

5、。因此，所求上下文无关文法gs为 gs：sasb|sb|b 由图3-3可直接得到正规文法gs：saa|bbaas|bc|b 图3-3 习题3.5的(3) 我们用一个非终结符a代表一个a(即有aa)，用一个非终结符b代表一个b(即有bb)；为了保证a和b的个数相同，则在出现一个a时应相应地出现一个b，出现一个b时则相应出现一个a。假定已推导出ba，如果下一步要推导出连续两个b时，则应有babbaa。也即为了保证b和a的个数一致，应有abaa；同理有babb。此外，为了保证递归地推出所要求的ab串，应有sabs和sbas。由此得到无二义文法gs为 abaa|a babb|b 3.6 有文法gs:

6、saacb|bd aaab|c bbsca|b (1) 试求句型aaabcbbdcc和aacbbdcc的句柄； (2) 写出句子acabcbbdcc的最左推导过程。 【解答】 (1) 分别画出对应句型aaabcbbdcc和aacbbdcc的语法树如图3-4的(a)、 s(b)所示。 saacb aacb aabbsca bscabdc图3-4 习题3.6的语法树 bdc b (a )(b ) (a) aaabcbbdcc; (b) aacbbdcc 对树(a)，直接短语有3个：aab、b和c，而aab为最左直接短语(即为句柄)。对树(b)，直接短语有两个：bd和c，而bd为最左直接短语。 能否

7、不画出语法树，而直接由定义(即在句型中)寻找满足某个产生式的候选式这样一个最左子串(即句柄)呢？例如，对句型aaabcbbdcc，我们可以由左至右扫描找到第一个子串aab，它恰好是满足aaab右部的子串；与树(a)对照，aab的确是该句型的句柄。是否这一方法始终正确呢？我们继续检查句型aacbbdcc，由左至右找到第一个子串c，这是满足ac右部的子串，但由树(b)可知，c不是该句型的句柄。由此可知，画出对应句型的语法树然后寻找最左直接短语是确定句柄的好方法。 (2) 句子acabcbbdcc的最左推导如下： saacbaaabcbacabcbacabcbacabcbscaacabcbbdca

8、acabcbbdcaacabcbbdcc 3.7 对于文法gs: s(l)|as|a ll,s|s (1) 画出句型(s,(a)的语法树； (2) 写出上述句型的所有短语、直接短语、句柄、素短语和最左素短语。 【解答】 (1) 句型(s, (a)的语法树如图3-5所示。 s (l) l,s s(l)图3-5 句型(s,(a)的语法树 s a(2) 由图3-5可知： 短语：s、a、(a)、s,(a)、(s,(a)； 直接短语：a、s； 句柄：s； 素短语：素短语可由图3-5中相邻终结符之间的优先关系求得，即： #? (?，? (?a?)?)?# 因此，素短语为a。 3.8 下述文法描述了c语言整

9、数变量的声明语句： gd: dtl tint|long|short lid|l,id (1) 改造上述文法，使其接受相同的输入序列，但文法是右递归的； (2) 分别用上述文法gd和改造后的文法gd为输入序列int a,b,c构造分析树。 【解答】 (1) 消除左递归后，文法gd如下： dtl d tint|long|short dtllidl intal intl,c,bl l,b,cl图3-6 两种文法为int a,b,c构造的分析树 a? (a ) (b )(a) 文法g(d)； (b) 文法g(d) 3.9 考虑文法gs: s(t) | a+s | a tt,s | s 消除文法的左递归

10、及提取公共左因子，然后对每个非终结符写出不带回溯的递归子程序。 【解答】 消除文法gs的左递归： s(t) | a+s | a tst 提取公共左因子： s(t) | as tst 改造后的文法已经是ll(1)文法，不带回溯的递归子程序如下： void match (token t) if ( lookahead=t) lookahead=nexttoken; else error ( ); void s ( ) if ( lookahead=a) match (a); else if ( lookahead=() match (); t ( ); void s( ) if ( lookahe

11、ad=+) match (+); s ( ); void t ( ) s ( ); t( ); void t ( ) if ( lookahead=, ) match (, ); s ( ); t ( ); 3.10 已知文法ga: aaabl|a bbb|d (1) 试给出与ga等价的ll(1)文法ga； (2) 构造ga的ll(1)分析表； (3) 给出输入串aadl#的分析过程。 来消除左递归。由此，将产生式bbb|d改造为 bdb 其次，应通过提取公共左因子的方法来消除ga中的回溯，即将产生式aaabl|a改造为 aaa【篇二：编译原理教程课后习题答案第一章】 完成下列选择题： (1)

12、 构造编译程序应掌握 a. 源程序 b. 目标语言 c. 编译方法 d. 以上三项都是 (2) 编译程序绝大多数时间花在上。 a. 出错处理 b. 词法分析 c. 目标代码生成 d. 表格管理 (3) 编译程序是对。 a. 汇编程序的翻译 b. 高级语言程序的解释执行 c. 机器语言的执行 d. 高级语言的翻译 【解答】 (1) d (2) d(3) d 1.2 计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？ 【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。 在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序

13、的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，而所翻译的机器代码语句串在该语句执行后并不保留，最后再读入下一条源程序语句，并解释执行。这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。 在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。因此，编译对源程序的处理是先翻译，后执行。 从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试

14、。 这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。 1.3 请画出编译程序的总框图。如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？ 【解答】 编译程序总框图如图1-1所示。 作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。总之，总设计师在设计编译程序时必须估量系统功能要求、硬件设备及软件工具等诸因素对编译程序构造的影响等。 程序 子程序或分程序 语句 表达式 数据

15、引用算符函数调用【篇三：编译原理课后答案】下列正规式描述的语言 (a) 0(0|1)*0 在字母表0, 1上,以0开头和结尾的长度至少是2的01串 在字母表0, 1上,所有的01串,包括空串 在字母表0, 1上,含有3个1的01串 (e) (00|11)*(01|10)(00|11)*(01|10)(00|11)*)* 在字母表0, 1上,含有偶数个0和偶数个1的01串 2.4为下列语言写正规定义 c语言的注释，即以 /* 开始和以 */ 结束的任意字符串，但它的任何前缀（本身除外）不以 */ 结尾。 解答 other a | b | other指除了*以外c语言中的其它字符 other1 a

16、 | b | other1指除了*和/以外c语言中的其它字符 comment /* other* (* * other1 other*)* * */ (f) 由偶数个0和偶数个1构成的所有0和1的串。 解答 由题目分析可知，一个符号串由0和1组成，则0和1的个数只能有四种情况： x 偶数个0和偶数个1（用状态0表示）； x 偶数个0和奇数个1（用状态1表示）； x 奇数个0和偶数个1（用状态2表示）； x 奇数个0和奇数个1（用状态3表示）； 所以， x 状态0（偶数个0和偶数个1）读入1，则0和1的数目变为：偶数个0和奇数个1（状态1） x 状态0（偶数个0和偶数个1）读入0，则0和1的数目

17、变为：奇数个0和偶数个1（状态2） x 状态1（偶数个0和奇数个1）读入1，则0和1的数目变为：偶数个0和偶数个1（状态0） x 状态1（偶数个0和奇数个1）读入0，则0和1的数目变为：奇数个0和奇数个1（状态3） x 状态2（奇数个0和偶数个1）读入1，则0和1的数目变为：奇数个0和奇数个1（状态3） x 状态2（奇数个0和偶数个1）读入0，则0和1的数目变为：偶数个0和偶数个1（状态0） x 状态3（奇数个0和奇数个1）读入1，则0和1的数目变为：奇数个0和偶数个1（状态2） x 状态3（奇数个0和奇数个1）读入0，则0和1的数目变为：偶数个0和奇数个1（状态1） 因为，所求为由偶数个0和

18、偶数个1构成的所有0和1的串，故状态0既为初始状态又为终结状态，其状态转换图： 由此可以写出其正规文法为： (1) s3 = (00|11) s3 + (01|10) s0 + 01 + 10 (2) 解(2)式得： s3 = (00|11)* (01|10) s0 + (01|10) 代入(1)式得： s0 = (00|11) s0 + (01|10) (00|11)*(01|10) s0 + (01|10) + (00|11) = s0 = (00|11) + (01|10) (00|11)*(01|10)s0 + (01|10) (00|11)*(01|10) + (00|11) = s

19、0 = (00|11)|(01|10) (00|11)*(01|10)*(00|11) + (01|10) (00|11)* (01|10) = s0 = (00|1 1)|(01|10) (00|11)* (01|10)+ 解答 此题目我们可以借鉴上题的结论来进行处理。 对于由偶数个0和奇数个1构成的所有0和1的串，我们分情况讨论：(1) 若符号串首字符为0，则剩余字符串必然是奇数个0和奇数个1，因此我们必须在上题偶数个0和偶数个1的符号串基础上再读入10（红色轨迹）或01（蓝色轨迹），又因为在01和13的过程中可以进行多次循环（红色虚线轨迹），同理02和23（蓝色虚线轨迹），所以还必须增加

20、符号串(00|11)*，我们用s0表示偶数个0和偶数个1， 用s表示偶数个0和奇数个1则其正规定义为： s 0(00|11)*(01|10) s0 s0 (00|11)|(01|10) (00|11)* (01|10)* (2) 若符号串首字符为1，则剩余字符串必然是偶数个0和偶数个1，其正规定义为：s 1s0 s0 (00|11)|(01|10) (00|11)* (01|10)* 综合(1)和(2)可得，偶数个0和奇数个1构成的所有0和1串其正规定义为：s 0(00|11)*(01|10) s0|1s0 s0 (00|11)|(01|10) (00|11)* (01|10)*ababbab

21、:s-4-0-1-5-6-7-8-4-0-1-5-6-7-6-7-8-4-0-1-5-6-7-8-f 2.12 为下列正规式构造最简的dfa (b) (a|b)* a (a|b) (a|b) (1) 根据算法2.4构造该正规式所对应的nfa，如图所示。 (2) 根据算法2.2（子集法）将nfa转换成与之等价的dfa（确定化过程） 初始状态 (3) 根据算法2.3过将dfa最小化 第一次划分：s0, s1, s2, s3, s4 s5, s6, s7, s8s0, s1, s2, s3, s4a = s1, s3, s1, s5, s7 第二次划分：s0, s1, s2 s3, s4s5, s6

22、, s7, s8s0, s1, s2a = s1, s3, s1 第三次划分：s0, s2 s1 s3, s4 s5, s6, s7, s8s0, s2a = s1 s0, s2b = s2 s0, s2不可区分，即等价。 s5, s6, s7, s8a = s5, s7, s3, s1 第四次划分：s0, s2 s1 s3, s4 s5, s6s7, s8s3, s4a = s5, s7第五次划分：s0, s2 s1 s3s4 s5, s6s7, s8s5, s6a = s5, s7 第六次划分：s0, s2 s1 s3s4 s5s6s7, s8 s7, s8a = s3, s1 第七次划分：s0, s2 s1 s3s4 s5s6s7s8 集合不可再划分， 所以s0, s2等价，选取s0表示s0, s2，其状态转换图，即题目所要求的最简dfa如下所示： 第三章 3.1 3.2 3.10 3.113.20 3.23