编译原理习题

编译原理习题Tag内容描述：<p>1、编译原理课后习题答案第十一章 第 11 章 代码优化 第题 何谓代码优化？进行优化所需要的基础是什么？ 答案： 对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行 速度加快或占用存储空间减少，或两者都有。 优化所需要的基础是在中间代码生成之后或目标代码生成之后。 第题 编译过程中可进行的优化如何分类？ 答案： 依据优化所涉及的程序范围，可以分为：局部优化、循环优化和全局优化。 第题 最常用的代码优化技术有哪些？ 答案： 1. 删除多余运算 2. 代码外提 3. 强度削弱 4. 变换循环控制条件 5. 合并已。</p><p>2、编译原理课后习题编译原理课后习题第 1 章引论第 1 题解释下列术语：（1） 编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。（2） 源程序：源语言编写的程序称为源程序。（3） 目标程序：目标语言书写的程序称为目标程序。（4） 编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。。</p><p>3、第第 1、2 章章 一 填空 1.若源程序是用高级语言编写的，目标程序是__________语言的程序，则相应的翻译程序 称为编译程序。 2.（华中科大）翻译程序是这样一种程序，它能够将_____________转换成与其等价的 ________________。 3. 对编译程序而言，输入数据是____________，输出结果是_________________。 4.（华东计算所）汇编程序是将_________翻译成_________；编译程序是将____翻译成 _________ a 汇编语言程序 b 机器语言程序 c 高级语言程序 d a 或 b e a 或 c f b 或 c 5. （国防科大）编译过程中，语法分析器的任务是_______ （1。</p><p>4、二、概念题1、设有文法：PP+Q|QQQ*R|RR(P)|i（1）证明Q*R+Q+Q是它的一个句型。（3分)（2）给出Q*R+Q+Q的所有短语，直接短语和句柄。(4分)（3）给出句子+*的最右推导。(4分)（4）给出句子+*的最左推导。(4分)2、设有文法：EE+T|T TT*F|F F(E)|i（1）证明E+T*F是它的一个句型。（3分)答案：（2）给出E+T*F的所有短语，直接短语和句柄。(4分)短语: E+T*F, T*F,直接短语: T*F句柄: T*F（3）给出句子+*的最右推导。(4分)3、写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。答案：逆波兰式：(abcd-*+) 三元式序列:OP ARG1 ARG2(1) - c d(2) * b。</p><p>5、第一章1典型的编译程序在逻辑功能上由哪几部分组成？答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。2. 实现编译程序的主要方法有哪些？答：主要有：转换法、移植法、自展法、自动生成法。3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？答：编译法、解释法。4. 编译方式和解释方式的根本区别是什么？答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高。</p><p>6、编译原理复习题及答案一、 选择题1 一个正规语言只能对应(B)A 一个正规文法B 一个最小有限状态自动机2 文法GA：A AaB BAb Ba是(A)A 正规文法B 二型文法3 下面说法正确的是(A)A 一个SLR（1）文法一定也是LALR（1）文法B 一个LR（1）文法一定也是LALR（1）文法4 一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A)A 必要条件B 充分必要条件5 下面说法正确的是(B)A 一个正规式只能对应一个确定的有限状态自动机B 一个正规语言可能对应多个正规文法6 算符优先分析与规范归约相比的优点是(A)A 归约速度快B 对文法限制。</p><p>7、编译原理习题解答参考1.计算机执行用高级语言编写的程序的途径有哪些？它们之间主要区别是什么？答：计算机执行用高级语言编写的程序途径有两种：解释方式和编译方式。解释方式下直接对源程序进行解释执行，并得到计算结果，特点是计算机并不事先对高级语言进行全盘翻译将其全部变为机器代码，而是每读入一条语句，就用解释器将其翻译为机器代码，予以执行，然后再读入下一条高级语句，翻译为机器代码，再执行，如些反复，即边翻译边执行；编译方式下对源程序的执行需要经过翻译阶段和运行阶段才能得到计算结果，其特点是计算机事先对高级。</p><p>8、3.简答题：至少使用两种不同的形式表示法描述由7/9的一切精度的近似值组成的集合。方法（1）S0.A A7A | 7方法（2）S0.7 | S7方法（3）0.7+16.简答题：语法分析器的输入、必要的输出及主要的任务是什么？输入是词法分析器的结果、单词或单词的序列。必要的输出是语法单位、语法出错信息，包括错误的位置和错误的性质等。主要任务是检查形式语法错误，即检查语法结构错误。8.问答题：LL(1)分析法和递归子程序分析法在方法上有何异同？性能上各有何优缺点？方法上的相同点：在方法上同属于自上而下的基于推导的分析算法，对文法的要求也是相。</p><p>9、一、填空题:1-01.编译程序的工作过程一般可以划分为 词法分析,语法分析,语义分析，之间代码生成,代码优化 等几个基本阶段,同时还会伴有 表格处理 和 出错处理 .1-02.若源程序是用高级语言编写的,目标程序是 机器语言程序或汇编程序 ,则其翻译程序称为编译程序.1-03.编译方式与解释方式的根本区别在于 是否生成目标代码 .1-04.翻译程序是这样一种程序,它能够将 用甲语言书写的程序 转换成与其等价的 用乙语言书写的程序 .1-05.对编译程序而言,输入数据是 源程序 ,输出结果是 目标程序 .1-06.如果编译程序生成的目标程序是机器代码程序,则源。</p><p>10、编译原理习题（一）词法分析一、是非题（请在括号内，正确的划，错误的划）1编译程序是对高级语言程序的解释执行。( )2一个有限状态自动机中，有且仅有一个唯一的终态。()3两个正规集相等的必要条件是他们对应的正规式等价。 ( )4. 对任何正规表达式e，都存在一个DFAM，满足L(M)L(e)。二、选择题1词法分析器的输出结果是_____。A( ) 记号 B( ) 相应条目在符号表中的位置 C( ) 记号和属性二元组 D( ) 属性值2 正规式 M 1 和 M 2 等价是指_____。 A( ) M1和M2的状态数相等 B( ) M1和M2的有向边条数相等C( ) M1和M2所识别的语言集相等 D( ) M。</p><p>11、第2章 形式语言1试分别构造产生下列语言的文法：（1）an#bn|n0cn#dn|n0；（2）任何不是以0打头的所有奇整数所组成的集合。答：(1) 对应文法为G(S)=(S,X,Y,a,b,c,d,#, SX, SY, XaXb|#, YcYd|# ,S)(2) G(S)=(S,A,B,I,J,0,1,2,3,4,5,6,7,8,9,SJ|IBJ, B0B|IB|, IJ|2|4|6|8, J1|3|5|7|9,S)2对于下列的文法SAB|c AbA|a BaSb|c试给出句子bbaacb的最右推导。答：S=AB=AaSb= Aacb=bAacb=bbAacb=bbaacb3已知文法GS: S-(AS)|(b)A-(SaA)|(a)请找出符号串(a)和(A(SaA)(b)的短语、简单短语和句柄。答：因为S 不能 (a),。</p><p>12、1.1何谓源程序、目标程序、翻译程序、编译程序和解释程序?它们之间可能有何种关系? 1.2一个典型的编译系统通常由哪些部分组成?各部分的主要功能是什么? 1.3选择一种你所熟悉的程序设计语言，试列出此语言中的全部关键字，并通过上机使用该语言以判明这些关键字是否为保留字。 1.4选取一种你所熟悉的语言，试对它进行分析，以找出此语言中的括号、关键字END以及逗号有多少种不同的用途。 1.5试用你常用的一种高级语言编写一短小的程序，上机进行编译和运行，记录下操作步骤和输出信息，如果可能，请卸出中间代码和目标代码。第一章 习题解。</p><p>13、第1、2章一 填空1.若源程序是用高级语言编写的，目标程序是__________语言的程序，则相应的翻译程序称为编译程序。2.（华中科大）翻译程序是这样一种程序，它能够将_____________转换成与其等价的________________。3. 对编译程序而言，输入数据是____________，输出结果是_________________。4.（华东计算所）汇编程序是将_________翻译成_________；编译程序是将____翻译成_________a 汇编语言程序b 机器语言程序c 高级语言程序d a或be a或cf b或c5. （国防科大）编译过程中，语法分析器的任务是_______（1）分析单词是怎样构成的（2）。</p><p>14、1与机器有关的代码优化有那些种类，请分别举例说明。解答：与机器有关的优化有：寄存器优化，多处理优化，特殊的指令优化，无用的指令消除等四类。冗余指令删除假设源程序指令序列a:=b+c; c:=a-d;编译程序为其生成的代码很可能是下列指令序列：MOV b, R0ADD c, R0MOV R0,aSUB d, R0MOV R0,c假如第四条指令没有标号，上述两个赋值语句在一个基本块内，则第四条指令是多余的，可删除。特殊指令的使用例如，如果目标机器指令系统包含增1指令INC，对于i:=i+1的目标代码MOV i, R0ADD #1, R0MOV R0, i便可被代之以1条指令Inc i说明：优化的特点。</p><p>15、编译技术习题3一、单项选择题1如果文法G是无二义的，则下面（ ）成立。A、对于文法中的任意一个句子，它的最左或最右推导对应的语法树相同B、文法中的一个句子对应两棵不同的语法树C、文法中的某个句子有两棵不同的最左推导D、文法中的某个句子有两棵不同的最右推导2解释程序和编译程序是两类程序语言处理程序，它们的主要区别在于（ ）。A、单用户与多用户的差别 B、对用户程序的差错能力 C、机器执行效率 D、是否生成目标代码3有文法的开始符号经0步或多步推导产生的文法符号序列是（ ）。A、句型 B、短语 C、句柄 D、句子4规范规约分析。</p><p>16、大学课程大学课程编译原理练习测试题库编译原理练习测试题库 一、填空一、填空 1.若源程序是用高级语言编写的，目标程序是______，则其翻译程序称为编译程序。 2.词法分析和语法分析本质上都是对源程序的______进行分析。 3.如果源语言(编写源程序的语言)是高级语言， 而目标语言是某计算机的汇编语言或机器语 言，则这种翻译程序称为_____。 4.对编译程序而言，输入数据是_______,输出结果是________。 5. ______，是构成语言文法的单词，是语法成分的最小单位。 6.由 PL0 的 EBNF 可知，PL0 语言可看成是 PASCAL 语言的子集，它的编译程。</p><p>17、一.填空题:1-01.编译程序的工作过程一般可以划分为_ __等几个基本阶段,同时还会伴有_ __和 .1-02.若源程序是用高级语言编写的,目标程序是 __ __,则其翻译程序称为编译程序.1-03.编译方式与解释方式的根本区别在于_ _.1-04.翻译程序是这样一种程序,它能够将__ ___转换成与其等价的__ __.1-05.对编译程序而言,输入数据是__ __,输出结果是 __ __.1-06.如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两大阶段:_ __和__ __.如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分为三个阶段: _ __,_ ___和_ __ .1-07.一个。</p>