编译原理-答案

《编译原理教程》（第三版）习题解析与上机指导胡元义等编著西安电子科技大学出版社普通高等院校计算机类专业系列教材目录第一章绪论第二章词法分析第三章语法分析第四章语义分析和中间代码生成第五章代码优化第六章运行时存储空间组织第七章目标代码生成第八章符号表与错误处理第九章小型编译程序介绍第十章上机实验内容第十一章小型编译程序第一章绪论•1.1完成下列选择题：•(1)构造编译程序应掌握。•a.源程序b.目标语言•c.编译方法d.以上三项都是•(2)编译程序绝大多数时间花在上。•a.出错处理b.词法分析•c.目标代码生成d.表格管理•(3)编译程序是对。•a.汇编程序的翻译b.高级语言程序的解释执行•c.机器语言的执行d.高级语言的翻译•【解答】•(1)d(2)d(3)d•1.2计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？•【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。••在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，而所翻译的机器代码语句串在该语句执行后并不保留，最后再读入下一条源程序语句，并解释执行。这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。•在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。因此，编译对源程序的处理是先翻译，后执行。•从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。•这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。•1.3请画出编译程序的总框图。如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？•【解答】编译程序总框图如图1-1所示。程序子程序或分程序语句表达式算符数据引用函数调用图1-1编译程序总框图•作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。总之，总设计师在设计编译程序时必须估量系统功能要求、硬件设备及软件工具等诸因素对编译程序构造的影响等。第二章词法分析•2.1完成下列选择题：•(1)词法分析器的输出结果是。•a.单词的种别编码b.单词在符号表中的位置•c.单词的种别编码和自身值d.单词自身值•(2)正规式M1和M2等价是指。•a.M1和M2的状态数相等•b.M1和M2的有向边条数相等•c.M1和M2所识别的语言集相等•d.M1和M2状态数和有向边条数相等•(3)DFAM(见图2-1)接受的字集为。•a.以0开头的二进制数组成的集合•b.以0结尾的二进制数组成的集合•c.含奇数个0的二进制数组成的集合•d.含偶数个0的二进制数组成的集合•【解答】•(1)c(2)c(3)d•XY001图2-1习题2.1的DFAM•2.2什么是扫描器？扫描器的功能是什么？•【解答】扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。•2.3设M=({x,y},{a,b},f,x,{y})为一非确定的有限自动机，其中f定义如下：•f(x,a)={x,y}f{x,b}={y}•f(y,a)=Φf{y,b}={x,y}•试构造相应的确定有限自动机M′。•【解答】对照自动机的定义M=(S,Σ,f,So,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，因此M是一非确定有限自动机。•先画出NFAM相应的状态图，如图2-2所示。XabbbaY图2-2习题2.3的NFAM•用子集法构造状态转换矩阵，如表2-1所示。表2-1状态转换矩阵IIaIb{x}{x,y}{y}{y}—{x,y}{x,y}{x,y}{x,y}•将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到•M′=({0,1,2},{a,b},f,0,{1,2})，其状态转换图如图2-3所示。表2-2状态转换矩阵f字符状态ab0211—2222•将图2-3所示的DFAM′最小化。首先，将M′的状态分成终态组{1,2}与非终态组{0}。其次，考察{1,2}，由于{1,2}a={1,2}b={2}{1,2}，所以不再将其划分了，也即整个划分只有两组：{0}和{1,2}。令状态1代表{1,2}，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图2-4所示的化简了的DFAM′。图2-3习题2.3的DFAM′021abba,b01aba,b图2-4图2-3化简后的DFAM′•2.4正规式(ab)*a与正规式a(ba)*是否等价？请说明理由。•【解答】正规式(ab)*a对应的NFA如图2-5所示，正规式a(ba)*对应的NFA如图2-6所示。Y1X2aba图2-5正规式(ab)*a对应的NFAY1X2aba图2-6正规式a(ba)*对应的DFA•这两个正规式最终都可得到最简DFA，如图2-7所示。因此，这两个正规式等价。0ab1图2-7最简NFA•2.5设有L(G)={a2n+1b2ma2p+1|n≥0,p≥0,m≥1}。•(1)给出描述该语言的正规表达式；•(2)构造识别该语言的确定有限自动机(可直接用状态图形式给出)。•【解答】该语言对应的正规表达式为a(aa)*bb(bb)*a(aa)*，正规表达式对应的NFA如图2-8所示。Y1Xba345bbab6aa2aa图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所示。{X}{1}{2}{1}{1}{2}{3}{4}{5}{Y}{6}—{Y}—{6}{Y}—{3}—{4}{5}{4}——0123457612——3—17—67454——重新命名IIaIbSab图2-9习题2.5的状态转换矩阵410ba23ababa图2-10习题2.5的最简DFA•2.6有语言L={w|w∈(0,1)+，并且w中至少有两个1，又在任何两个1之间有偶数个0}，试构造接受该语言的确定有限状态自动机(DFA)。•【解答】对于语言L，w中至少有两个1，且任意两个1之间必须有偶数个0；也即在第一个1之前和最后一个1之后，对0的个数没有要求。据此我们求出L的正规式为0*1(00(00)*1)*00(00)*10*，画出与正规式对应的NFA，如图2-11所示。Y1X0156700100123400000图2-11习题2.6的NFA•用子集法将图2-11的NFA确定化，如图2-12所示。重新命名II0I1S01{X}{X}001{1}{2,5}12—{1}—{3,6}—2—3{2,5}{1,Y}345{4,7}{3,6}{3,6}43——{4,7}56——{2,5,Y}{1,Y}{3,6,Y}—67{2,5,Y}—{4,7,Y}78{1,Y}{3,6,Y}5—{3,6,Y}{4,7,Y}87—图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所示。04123561000100010图2-13习题2.6的最简DFA•2.7已知正规式((a|b)*|aa)*b和正规式(a|b)*b。•(1)试用有限自动机的等价性证明这两个正规式是等价的；•(2)给出相应的正规文法。•【解答】(1)正规式((a|b)*|aa)*b对应的NFA如图2-14所示。XY13aa24bba图2-14正规式((a|b)*|aa)*b对应的NFA•用子集法将图2-14所示的NFA确定化为DFA，如图2-15所示。重新命名{1,2,4,Y}332{1,2,3,4}{1,2,4,Y}{1,2,3,4}223{1,2,3,4}{1,2,4,Y}{X,1,2,4}123{1,2,3,4}{1,2,4,Y}IIaIbSab图2-15图2-14确定化后的状态转换矩阵•由于对非终态的状态1、2来说，它们输入a、b的下一状态是一样的，故状态1和状态2可以合并，将合并后的终态3命名为2，则得到表2-3(注意，终态和非终态即使输入a、b的下一状态相同也不能合并)。•由此得到最简DFA，如图2-16所示。•正规式(a|b)*b对应的NFA如图2-17所示。•表2-3合并后的状态转换矩阵Sab112212baba12图2-16习题2.7的最简DFAX12Yabb图2-17正规式(a|b)*b对应的NFA•用子集法将图2-17所示的NFA确定化为如图2-18所示的状态转换矩阵。重新命名{1,2,Y}332{1,2}{1,2,Y}{1,2}223{1,2}{1,2,Y}{X,1,2}123{1,2}{1,2,Y}IIaIbSab图2-18图2-17确定化后的状态转换矩阵•比较图2-18与图2-15，重新命名后的转换矩阵是完全一样的，也即正规式(a|b)*b可以同样得到化简后的DFA如图2-16所示。因此，两个自动机完全一样，即两个正规文法等价。•(2)对图2-16，令A对应状态1，B对应状态2，则相应的正规文法G[A]为•G[A]：A→aA|bB|b•B→aA|bB|b•G[A]可进一步化简为G[S]：S→aS|bS|b(非终结符B对应的产生式与A对应的产生式相同，故两非终结符等价，即可合并为一个产生式)。•2.8下列程序段以B表示循环体，A表示初始化，I表示增量，T表示测试：•I=1;•while(I=n)•{•sun=sun+a[I];•I=I+1;•}•请用正规表达式表示这个程序段可能的执行序列。•【解答】用正规表达式表示程序段可能的执行序列为A(TBI)*。•2.9将图2-19所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。XY1342abaabbabab图2-19习题2.9的NFA•其中，X为初态，Y为终态。•【解答】用子集法将NFA确定化，如图2-20所示。b重新命名IIaIbSa{X}{1}012{3}{2,3,Y}13{3,Y}{1}4—{3,4}25—{3}{2,3,4,Y}336{2,3,Y}{2,3,Y}{2,3,Y]435{3,4}{3,Y}557{3,4,Y}{3,4}{3,4}{2,3,4,Y}{2,3,4,Y}66{2,3,4,Y}6{2,3,4,Y}76{3,4,Y}{3,4,Y}7图2-20习题2.9的状态转换矩阵•图2-20所对应的DFA如图2-21所示。345aabba2bb01a7bb6babaa图2-21习题2.9的DFA012ab435aabbbbbaa图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