《编译原理 答案》由会员分享，可在线阅读，更多相关《编译原理 答案（689页珍藏版）》请在金锄头文库上搜索。
1、,编译原理教程（第三版） 习题解析与上机指导,胡元义等 编著,西安电子科技大学出版社 http:/,普通高等院校计算机类专业系列教材,目 录,第一章 绪论 第二章 词法分析 第三章 语法分析 第四章 语义分析和中间代码生成 第五章 代码优化 第六章 运行时存储空间组织 第七章 目标代码生成 第八章 符号表与错误处理 第九章 小型编译程序介绍 第十章 上机实验内容 第十一章 小型编译程序,第一章 绪论,1.1 完成下列选择题： (1) 构造编译程序应掌握 。 a. 源程序 b. 目标语言 c. 编译方法 d. 以上三项都是 (2) 编译程序绝大多数时间花在 上。 a. 出错处理 b. 词法分析
2、c. 目标代码生成 d. 表格管理,(3) 编译程序是对 。 a. 汇编程序的翻译 b. 高级语言程序的解释执行 c. 机器语言的执行 d. 高级语言的翻译 【解答】 (1) d (2) d (3) d 1.2 计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？ 【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。,在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，而所翻译的机器代码语句串在该语句执行后并不保留，最后再读入下一条
3、源程序语句，并解释执行。这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。,在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。因此，编译对源程序的处理是先翻译，后执行。 从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。 这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。,1.3 请画出编译程序的总框图。如果你是一个编译程序的总设计师
4、，设计编译程序时应当考虑哪些问题？ 【解答】 编译程序总框图如图1-1所示。,图1-1 编译程序总框图,作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。总之，总设计师在设计编译程序时必须估量系统功能要求、硬件设备及软件工具等诸因素对编译程序构造的影响等。,第二章 词法分析,2.1 完成下列选择题： (1) 词法分析器的输出结果是 。 a. 单词的种别编码 b. 单词在符号表中的位置 c. 单词的种别编码和自身值 d. 单
5、词自身值 (2) 正规式M1和M2等价是指 。 a. M1和M2的状态数相等 b. M1和M2的有向边条数相等 c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向边条数相等,(3) DFA M(见图2-1)接受的字集为 。 a. 以0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合 c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合 【解答】 (1) c (2) c (3) d,图2-1 习题2.1的DFA M,2.2 什么是扫描器？扫描器的功能是什么？ 【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词
6、符号，其输出结果是单词符号，供语法分析器使用。通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。,2.3 设M=(x,y, a,b, f, x, y)为一非确定的有限自动机，其中f定义如下： f(x,a)=x,y fx,b=y f(y,a)= fy,b=x,y 试构造相应的确定有限自动机M。 【解答】 对照自动机的定义M=(S,f,So,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，因此M是一非确定有限自动机。 先画出NFA M相应的状态图，如图2-2所示。,图2-2 习题2.3
7、的NFA M,用子集法构造状态转换矩阵，如表2-1所示。,表2-1 状态转换矩阵,将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到 M=(0,1,2,a,b,f,0,1,2)，其状态转换图如图2-3所示。,表2-2 状态转换矩阵,将图2-3所示的DFA M最小化。首先，将M的状态分成终态组1,2与非终态组0。其次，考察1,2，由于1,2a=1,2b=21,2，所以不再将其划分了，也即整个划分只有两组：0和1,2。令状态1代表1,2，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图2-4所示的化简了的DFA M。,图2-3 习题2.3的DFA M,图2-4 图2-3
8、化简后的DFA M,2.4 正规式(ab)*a与正规式a(ba)*是否等价？请说明理由。 【解答】 正规式(ab)*a对应的NFA如图2-5所示，正规式a(ba)*对应的NFA如图2-6所示。,图2-5 正规式(ab)*a对应的NFA,图2-6 正规式a(ba)*对应的DFA,这两个正规式最终都可得到最简DFA，如图2-7所示。因此，这两个正规式等价。,图2-7 最简NFA,2.5 设有L(G)=a2n+1b2ma2p+1| n0,p0,m1。 (1) 给出描述该语言的正规表达式； (2) 构造识别该语言的确定有限自动机(可直接用状态图形式给出)。 【解答】 该语言对应的正规表达式为a(aa)
9、*bb(bb)*a(aa)*，正规表达式对应的NFA如图2-8所示。,图2-8 习题2-5的NFA,用子集法将图2-8确定化，如图2-9所示。 由图2-9重新命名后的状态转换矩阵可化简为(也可由最小化方法得到) 0,2 1 3,5 4,6 7 按顺序重新命名为0、1、2、3、4后得到最简的DFA，如图2-10所示。,图2-9 习题2.5的状态转换矩阵,图2-10 习题2.5的最简DFA,2.6 有语言L=w|w(0,1)+，并且w中至少有两个1，又在任何两个1之间有偶数个0，试构造接受该语言的确定有限状态自动机(DFA)。 【解答】 对于语言L，w中至少有两个1，且任意两个1之间必须有偶数个0
10、；也即在第一个1之前和最后一个1之后，对0的个数没有要求。据此我们求出L的正规式为0*1(00(00)*1)*00(00)*10*，画出与正规式对应的NFA，如图2-11所示。,图2-11 习题2.6的NFA,用子集法将图2-11的NFA确定化，如图2-12所示。,图2-12 习题2.6的状态转换矩阵,由图2-12可看出非终态2和4的下一状态相同，终态6和8的下一状态相同，即得到最简状态为 0、1、2,4、3、5、6,8、7 按顺序重新命名为0、1、2、3、4、5、6，则得到最简DFA，如图2-13所示。,图2-13 习题2.6的最简DFA,2.7 已知正规式(a|b)*|aa)*b和正规式(
11、a|b)*b。 (1) 试用有限自动机的等价性证明这两个正规式是等价的； (2) 给出相应的正规文法。 【解答】 (1) 正规式(a|b)*|aa)*b对应的NFA如图2-14所示。,图2-14 正规式(a|b)*|aa)*b对应的NFA,用子集法将图2-14所示的NFA确定化为DFA，如图2-15所示。,图2-15 图2-14确定化后的状态转换矩阵,由于对非终态的状态1、2来说，它们输入a、b的下一状态是一样的，故状态1和状态2可以合并，将合并后的终态3命名为2，则得到表2-3(注意，终态和非终态即使输入a、b的下一状态相同也不能合并)。 由此得到最简DFA，如图2-16所示。 正规式(a|
12、b)*b对应的NFA如图2-17所示。,表2-3 合并后的状态转换矩阵,图2-16 习题2.7的最简DFA,图2-17 正规式(a|b)*b对应的NFA,用子集法将图2-17所示的NFA确定化为如图2-18所示的状态转换矩阵。,图2-18 图2-17确定化后的状态转换矩阵,比较图2-18与图2-15，重新命名后的转换矩阵是完全一样的，也即正规式(a|b)*b可以同样得到化简后的DFA如图2-16所示。因此，两个自动机完全一样，即两个正规文法等价。 (2) 对图2-16，令A对应状态1，B对应状态2，则相应的正规文法GA为 GA：AaA|bB|b BaA|bB|b GA可进一步化简为GS：SaS
13、|bS|b(非终结符B对应的产生式与A对应的产生式相同，故两非终结符等价，即可合并为一个产生式)。,2.8 下列程序段以B表示循环体，A表示初始化，I表示增量，T表示测试： I=1; while (I=n) sun=sun+aI; I=I+1; 请用正规表达式表示这个程序段可能的执行序列。,【解答】 用正规表达式表示程序段可能的执行序列为A(TBI)*。 2.9 将图2-19所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。,图2-19 习题2.9的NFA,其中，X为初态，Y为终态。 【解答】 用子集法将NFA确定化，如图2-20所示。,图2-20 习题2.9的状态转换矩阵
14、,图2-20所对应的DFA如图2-21所示。,图2-21 习题2.9的DFA,图2-22 习题2.9的最简DFA,对图2-21的DFA进行最小化。首先将状态分为非终态集和终态集两部分：0,1,2,5和3,4,6,7。由终态集可知，对于状态3、6、7，无论输入字符是a还是b的下一状态均为终态集，而状态4在输入字符b的下一状态落入非终态集，故将其化为分 0,1,2,5, 4, 3,6,7 对于非终态集，在输入字符a、b后按其下一状态落入的状态集不同而最终划分为 0, 1, 2, 5, 4, 3,6,7 按顺序重新命名为0、1、2、3、4、5，得到最简DFA如图2-22所示。,2.10 有一台自动售
15、货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中投放3分的硬币，便可得到一块糖(注意：只给一块并且不找钱)。 (1) 写出售货机售糖的正规表达式； (2) 构造识别上述正规式的最简DFA。 【解答】 (1) 设a=1，b=2，则售货机售糖的正规表达式为a (b|a(a|b)|b(a|b)。 (2) 画出与正规表达式a(b|a(a|b)|b(a|b)对应的NFA，如图2-23所示。,图2-23 习题2.10的NFA,用子集法将图2-21的NFA确定化，如图2-24所示。,图2-24 习题2.10的状态转换矩阵,由图2-24可看出，非终态2和非终态3面对输入符号a或b的下一状态相同，故合并为一个状态，即最简状态0、1、2，3、4。按顺序重新命名为0、1、2、3，则得到最简DFA，如图2-25所示。,图2-25 习题2.10的最简DFA,第三章 语法分析,3.1 完成下列选择题： (1) 文法G：SxSx|y所识别的语言是 。 a. xyx b. (xyx)* c. xnyxn(n0) d. x*yx* (2) 如果文法G是无二义的，则它的任何句子 。 a. 最左推导和最右推导对应的语法树必定相同 b. 最左
