编译原理课后习题答案

第一章1 ．典型的编译程序在逻辑功能上由哪几部分组成？答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。2. 实现编译程序的主要方法有哪些？答：主要有：转换法、移植法、自展法、自动生成法。3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？答：编译法、解释法。4. 编译方式和解释方式的根本区别是什么？答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快；解释方式：在执行时，必须源程序和解释程序同时参加才能运行，其不产生可执行程序文件，效率低，执行速度慢。第 二 章1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关系如何？答：1 ）0 型文法、1 型文法、2 型文法、3 型文法。2 ）2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0 为前导。答：ZSME | BS1|2|3|4|5|6|7|8|9M | D | MDD0|SB2|4|6|8E0|B3. 设文法G 为：N D|NDD 0|1|2|3|4|5|6|7|8|9请给出句子123 、301 和75431 的最右推导和最左推导。答：NNDN3ND3N23D23123NNDNDDDDD1DD12D123NNDN1ND1N01D01301NNDNDDDDD3DD30D301NNDN1ND1N31ND31N431ND431N5431D543175431NNDNDDNDDDNDDDDDDDDD7DDDD75DDD754DD7543D754314. 证明文法 SiSeS|iS| i是二义性文法。答：对于句型iiSeS存在两个不同的最左推导：SiSeSiiSesSiSiiSeS所以该文法是二义性文法。5. 给出描述下面语言的上下文无关文法。（1 ） L1={anbnci |n>=1,i>=0 }（2 ） L2={aibj|j>=i>=1}（3 ） L3={anbmcmdn |m,n>=0}答：（1 ）SABAaAb | abBcB | （2 ）SASb |abAa | （3 ）SaSd | A | AbAc | 6. 设计一个最简的DFA M,使其能够识别所有的被3 整除的无符号十进制整数。答：7. 设计一个DFA, 使其能够接受被4 整除的二进制数。答：8. 写出表达下列各项的正则表达式。（1 ）二进制数且为5 的倍数。（2 ）Σ={a,b,c}, 第一个a 位于第一个b 之前的字符串。（3 ）Σ={a,b,c}, 包含偶数个a 的字符串。（ 4 ） Σ={0 ， 1}, 不 包 含 11 子 串 的 字 符 串 ...