编译原理习题及答案(课堂PPT)

1《编译原理教程》习题解析.1第一章绪论第二章词法分析第三章语法分析2《编译原理教程》习题解析.2第一章绪论1.1完成下列选择题：(1)下面叙述中正确的是。A．编译程序是将高级语言程序翻译成等价的机器语言程序的程序B．机器语言因其使用过于困难，所以现在计算机根本不使用机器语言C．汇编语言是计算机唯一能够直接识别并接受的语言D．高级语言接近人们的自然语言，但其依赖具体机器的特性是无法改变的3《编译原理教程》习题解析.3(2)将编译过程分成若干“遍”是为了。A．提高程序的执行效率B．使程序的结构更加清晰C．利用有限的机器内存并提高机器的执行效率D．利用有限的机器内存但降低了机器的执行效率(3)构造编译程序应掌握。A．源程序B．目标语言C．编译方法D．A～C项4《编译原理教程》习题解析.4(4)编译程序绝大多数时间花在上。A．出错处理B．词法分析B．目标代码生成D．表格管理(5)编译程序是对。A．汇编程序的翻译B．高级语言程序的解释执行C．机器语言的执行D．高级语言的翻译5《编译原理教程》习题解析.5【解答】(1)编译程序可以将用高级语言编写的源程序转换成与之在逻辑上等价的目标程序，而目标程序可以是汇编语言程序或机器语言程序。故选A。(2)分多遍完成编译过程可使整个编译程序的逻辑结构更加清晰。故选B。(3)构造编译程序应掌握源程序、目标语言和编译方法这三方面内容。故选D。6《编译原理教程》习题解析.6(4)编译各阶段的工作都涉及到构造、查找或更新有关表格，即编译过程的绝大部分时间都用在造表、查表和更新表格的事务上。故选D。(5)由(1)可知，编译程序实际上实现了对高级语言程序的翻译。故选D。7《编译原理教程》习题解析.71.2计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，然后再读入下一条源程序语句并解释执行，而所翻译的机器代码语句串在该语句执行后并不保留。这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。8《编译原理教程》习题解析.8在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。因此，编译对源程序的处理是先翻译，后执行。从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。9《编译原理教程》习题解析.91.3请画出编译程序的总框图。如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？【解答】编译程序总框图如图1-1所示。作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。总之，总设计师在设计编译程序时必须估量系统功能要求、硬件设备及软件工具等诸因素对编译程序构造的影响。10《编译原理教程》习题解析.10图1-1编译程序总框图11《编译原理教程》习题解析.11第二章词法分析2.1完成下列选择题：(1)词法分析所依据的是。A．语义规则B．构词规则C．语法规则D．等价变换规则(2)词法分析器的输入是。A．单词符号串B．源程序C．语法单位D．目标程序12《编译原理教程》习题解析.12(3)词法分析器的输出是。A．单词的种别编码B．单词的种别编码和自身的值C．单词在符号表中的位置D．单词自身值(4)状态转换图(见图2-1)接受的字集为_______。A．以0开头的二进制数组成的集合B．以0结尾的二进制数组成的集合C．含奇数个0的二进制数组成的集合D．含偶数个0的二进制数组成的集合13《编译原理教程》习题解析.13图2-1习题2.1的DFAM14《编译原理教程》习题解析.14(5)对于任一给定的NFAM，一个DFAM′，使L(M)=L(M′)。A．一定不存在B．一定存在C．可能存在D．可能不存在(6) DFA适用于。A．定理证明B．语法分析C．词法分析D．语义加工15《编译原理教程》习题解析.15(7)下面用正规表达式描述词法的论述中，不正确的是。A．词法规则简单，采用正规表达式已足以描述B．正规表达式的表示比上下文无关文法更加简洁、直观和易于理解C．正规表达式描述能力强于上下文无关文法D．有限自动机的构造比下推自动机简单且分析效率高(8)与(a|b)*(a|b)等价的正规式是。A．(a|b)(a|b)*B．a*|b*C．(ab)*(a|b)*D．(a|b)*16《编译原理教程》习题解析.16【解答】(1)由教材第一章1.3节中的词法分析，可知词法分析所遵循的是语言的构词规则。故选B。(2)词法分析器的功能是输入源程序，输出单词符号。故选B。(3)词法分析器输出的单词符号通常表示为二元式：(单词种别，单词自身的值)。故选B。(4)虽然选项A、B、D都满足题意，但选项D更准确。故选D。17《编译原理教程》习题解析.17(5) NFA可以有DFA与之等价，即两者描述能力相同；也即，对于任一给定的NFAM，一定存在一个DFAM'，使L(M)=L(M′)。故选B。(6) DFA便于识别，易于计算机实现，而NFA便于定理的证明。故选C。(7)本题虽然是第二章的题，但答案参见第三章3.1.3节。即选C。(8)由于正则闭包R+=R*R=RR*，故(a|b)*(a|b)=(a|b)(a|b)*。故选A。18《编译原理教程》习题解析.182.2什么是扫描器？扫描器的功能是什么？【解答】扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常把词法分析器作为一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。19《编译原理教程》习题解析.192.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, s0, Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，因此M是一非确定有限自动机。先画出NFAM相应的状态图，如图2-2所示。20《编译原理教程》习题解析.20图2-2习题2.3的NFAM21《编译原理教程》习题解析.21用子集法构造状态转换矩阵，如表2-1所示。表2-1状态转换矩阵将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到Sab0211—2222IIaIb{x}{x,y}{y}{y}—{x,y}{x,y}{x,y}{x,y}22《编译原理教程》习题解析.22将图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′其状态转换图如图2-3所示。23《编译原理教程》习题解析.23图2-4图2-3化简后的DFAM′24《编译原理教程》习题解析.242.4正规式(ab)*a与正规式a(ba)*是否等价？请说明理由。【解答】正规式(ab)*a对应的NFA如图2-5所示，正规式a(ba)*对应的NFA如图2-6所示。用子集法将图2-5和图2-6分别确定化为如图2-7(a)和(b)所示的状态转换矩阵，它们最终都可以得到最简DFA，如图2-8所示。因此，这两个正规式等价。25《编译原理教程》习题解析.25图2-5正规式(ab)*a对应的NFA26《编译原理教程》习题解析.26图2-6正规式a(ba)*对应的NFA27《编译原理教程》习题解析.27图2-7图2-5和图2-6确定化后的状态转换矩阵—28《编译原理教程》习题解析.28图2-8最简DFA29《编译原理教程》习题解析.29实际上，当闭包*取0时，正规式(ab)*a与正规式a(ba)*由初态X到终态Y之间仅存在一条a弧。由于(ab)*在a之前，故描述(ab)*的弧应在初态结点X上；而(ba)*在a之后，故(ba)*对应的弧应在终态结点Y上。因此，(ab)*a和a(ba)*所对应的NFA也可分别描述为如图2-9(a)和(b)所示的形式，它们确定化并化简后仍可得到图2-8所示的最简DFA。30《编译原理教程》习题解析.30图2-9(ab)*a和a(ba)*分别对应的NFA31《编译原理教程》习题解析.312.5设有L(G)={a2n+1b2ma2p+1|n≥0,p≥0,m≥1}。(1)给出描述该语言的正规表达式；(2)构造识别该语言的确定有限自动机(可直接用状态图形式给出)。【解答】该语言对应的正规表达式为a(aa)*bb(bb)*a(aa)*，正规表达式对应的NFA如图2-10所示。32《编译原理教程》习题解析.32图2-10习题2.5的NFA33《编译原理教程》习题解析.33用子集法将图2-10确定化，如图2-11所示。由图2-11重新命名后的状态转换矩阵可化简为(也可由最小化方法得到){0,2}{1}{3,5}{4,6}{7}图2-11习题2.5的状态转换矩阵34《编译原理教程》习题解析.34按顺序重新命名为0、1、2、3、4后得到最简的DFA，如图2-12所示。图2-12习题2.5的最简DFA35《编译原理教程》习题解析.352.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-13所示。36《编译原理教程》习题解析.36图2-13习题2.6的NFA37《编译原理教程》习题解析.37用子集法将图2-13所示的NFA确定化，如图2-14所示由图2-14可看出非终态2和4的下一状态相同，终态6和8的下一状态相同，即得到最简状态为{0}{1}{2,4}{3}{5}{6,8}{7}38《编译原理教程》习题解析.38按顺序重新命名为0、1、2、3、4、5、6，则得到最简DFA，如图2-15所示。图2-15习题2.6的最简DFA39《编译原理教程》习题解析.392.7已知正规式((a | b)*| aa)*b和正规式(a | b)*b。(1)试用有限自动机的等价性证明这两个正规式是等价的；(2)给出相应的正规文法。【解答】(1)正规式((a | b)*| aa)*b对应的NFA如图2-16所示。用子集法将图2-16所示的NFA确定化为DFA，如图2-17所示。40《编译原理教程》习题解析.40图2-16正规式((a | b)*|aa)*b对应的NFA41《编译原理教程》习题解析.41图2-17图2-16确定化后的状态转换矩阵42《编译原理教程》习题解析.42由于对非终态的状态1、2来说，它们输入a、b的下一状态是一样的，故状态1和状态2可以合并，将合并后的终态3命名为2，则得到表2-3(注意，终态和非终态即使输入a、b的下一状态相同也不能合并)。由此得到最