编译技术原理及其实现方法 (王汝传 着) 课后习题答案 成都科技大学出版社

5.1 考虑以下的文法：S→S;T|TT→a（1）为这个文法构造LR(0)的项目集规范族。

（2）这个文法是不是LR(0)文法？如果是，则构造LR(0)分析表。

（3）对输入串“a;a”进行分析。

解：（1）拓广文法G[S’]：0：S’→S1：S→S;T2：S→T3：T→a构造LR(0)项目集规范族（2）该文法不存在“归约－归约”和“归约－移进”冲突，因此是LR(0)文法。

LR(0)分析表如下：（3）对输入串“a;a”进行分析如下：5.2 证明下面文法是SLR(1)文法，但不是LR(0)文法。

S→AA→Ab|bBaB→aAc|a|aAb解：文法G[S]：0：S→A1：A→Ab2：A→bBa3：B→aAc4：B→a5：B→aAb状态5存在“归约－移进”冲突，状态9存在“归约－归约”冲突，因此该文法不是LR(0)文法。

状态5：FOLLOW(B)＝｛a｝，因此，FOLLOW(B)∩｛b｝＝Φ状态9：FOLLOW(B)＝｛a｝，FOLLOW(A)＝｛#，b，c｝，因此FOLLOW(B)∩FOLLOW(A)＝Φ该SLR(1)分析表无重定义，因此该文法是SLR(1)文法，不是LR(0)文法。

5.3 证明下面文法是LR(1)文法，但不是SLR(1)文法。

S→AaAb|BbBaA→εB→ε解：拓广文法G[S’]：0：S’→S1：S→AaAb2：S→BbBa3：A→ε4：B→ε＝｛a,b｝，即FOLLOW(A)∩FOLLOW(B)＝｛a,b｝≠Φ，所以该文法不是SLR(1)文法。

构造LR(1)项目集规范族：分析表无重定义，说明该文法是LR(1)文法，不是SLR(1)文法。

5.4 考虑以下的文法：E→EE＋E→EE*E→a（1）为这个文法构造LR(1)项目集规范族。

（2）构造LR(1)分析表。

（3）为这个文法构造LALR(1)项目集规范族。

（4）构造LALR(1)分析表。

（5）对输入符号串“aa*a+”进行LR(1)和LALR(1)分析。

编译原理第二版课后习答案《编译原理》课后习题答案第一章第 1 章引论第 1 题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2）源程序：源语言编写的程序称为源程序。

（3）目标程序：目标语言书写的程序称为目标程序。

（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第 2 题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

答案：一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

表格管理程序：负责建立、填写和查找等一系列表格工作。

第二章 词法分析2.1 完成下列选择题： (1) 词法分析器的输出结果是 。

a. 单词的种别编码 b. 单词在符号表中的位置 c. 单词的种别编码和自身值 d. 单词自身值 (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 习题的DFA M2.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 是一非确定有限自动机。

先画出NFA M 相应的状态图，如图2-2所示。

图2-2 习题的NFA M用子集法构造状态转换矩阵，如表表2-1 状态转换矩阵1b将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到 M ′=({0,1,2},{a,b},f,0,{1,2})，其状态转换图如图2-3所示。

《编译原理》课程实验教学大纲课程编号：BS 课程名称：编译原理课内总学时：48 上机实验学时：8实验类别：□通识基础□学科基础□专业基础■专业一、实验课程目的和任务性质：本实验课程是计算机及其相关专业的专业课程，该实验是理论课程的课内上机实验环节。

目的和任务：编译原理是一门理论与实践结合紧密的课程。

通过实验，使学生加深对课内所学的有关编译过程各阶段所采用的主要算法、方法和技术等内容的理解，能把《编译原理》的相关理论运用到软件开发中。

在学生手动编写词法分析器及语法分析器的过程中，使学生对这些部分的工作机理有一个详细的了解，从而提高学生的应用程序设计能力，提高分析问题、解决问题的能力。

通过上机实验将所学理论知识与实践相结合，加深对课程的理解。

二、实验内容、学时分配及基本要求三、考核及实验报告（一）考核本课程非独立授课，实验成绩记入课程平时成绩，约占课程总成绩的10%，结合学生上实验课的课堂表现（如：有无缺勤、有无事先准备程序代码、课堂上是否认真实验以及实验结果等）及实验报告综合打分。

（二）实验报告实验报告的内容：实验名称、实验目的、实验任务、实验内容、实验过程描述（包括实验结果分析、实验过程遇到的问题及体会）。

实验报告的要求：实验报告以文本或电子档形式递交，实验报告书写要求如下：1. 问题描述：包括实验名称、目的、内容，以简洁明了的叙述说明本次上机实验的任务和目标，程序的输入和输出要求以及程序的功能。

2. 主要仪器设备：包括实验过程中所用的主要仪器设备、软件等。

3. 实验过程描述：包括源程序的各个组成部分以及算法分析过程，演示结果等。

4. 分析和体会：包括实验结果分析，测试、调试过程所遇到的问题，程序设计与实现的经验和体会，进一步改进的设想。

四、主要仪器设备硬件：微型计算机。

软件：Eclipse或Visual C++ 6.0（也可以是其它集成开发环境）。

五、教材及参考书教材[1] 王汝传．编译技术原理及其实现方法．成都科技大学出版社，1998参考书[1] 吕映芝，张素琴，蒋维杜．编译原理．清华大学出版社，1998[2] 陈火旺等．程序设计语言编译原理．国防工业出版社，2000六、说明无执笔人：蒋凌云审核人：黄海平实验院长：陈丹伟编写完成时间：2013年6月2附录1：《词法分析器的构造》综合性实验大纲一、实验目的设计、编制、调试一个词法分析程序，对单词进行识别和编码，加深对词法分析原理的理解。

1.翻译程序：能够将某种语言写的程序转换成另一种语言的程序，而且后者与前者在逻辑上是等价的。

编译程序：是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序解释程序：接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。

源程序：被翻译的程序。

目标程序：翻译后的程序。

遍：对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。

编译前端：主要指与源语言有关，与目标语言无关的部分，通常包括词法分析、语法分析、语义分析和中间代码生成，与机器无关部分的代码优化编译后端：指与目标机器有关的部分。

如与机器有关的优化、目标代码生成2.高级语言程序有哪两种执行方式？其特点是什么？阐述其主要异同点。

答：高级语言程序有编译程序和解释程序两种执行方式；编译程序（Compiler）——将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。

解释程序（Interpreter）——将高级程序设计语言写的源程序作为输入，边解释边执行源程序本身，而不产生目标程序的翻译程序。

3.编译过程可分为哪些阶段？各个阶段的主要任务是什么？答：编译过程逻辑上可分为五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。

第一阶段：词法分析任务: 从左到右扫描源程序，识别出每个单词第二阶段：语法分析任务: 在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。

第三阶段：语义分析和中间代码生成任务：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)。

第四阶段：代码优化任务：对已产生的中间代码进行加工变换，使生成的目标代码更为高效(时间和空间)。

第五阶段：目标代码的生成任务：把中间代码(或经优化的中间代码)变换成特定机器上的低级语言代码。

4. 编译程序有哪些主要构成成分？各自的主要功能是什么？答：(1) 记号(token)当扫描程序将字符收集到一个记号中时，它通常是以符号表示这个记号；这也就是说，作为一个枚举数据类型的值来表示源程序的记号集。

第一章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⇒75431 4. 证明文法S→iSeS|iS| i是二义性文法。

答：对于句型iiSeS存在两个不同的最左推导：S⇒iSeS⇒iiSesS⇒iS⇒iiSeS所以该文法是二义性文法。