《编译原理》练习题库参考答案.docx

《《编译原理》练习题库参考答案.docx》由会员分享，可在线阅读，更多相关《《编译原理》练习题库参考答案.docx（22页珍藏版）》请在三一办公上搜索。

1、编译原理练习题库参考答案编译原理练习测试题库 一、填空 1.若源程序是用高级语言编写的，目标程序是_，则其翻译程序称为编译程序。 2.词法分析和语法分析本质上都是对源程序的_进行分析。 3.如果源语言(编写源程序的语言)是高级语言，而目标语言是某计算机的汇编语言或机器语言，则这种翻译程序称为_。 4.对编译程序而言，输入数据是_,输出结果是_。 5. _，是构成语言文法的单词，是语法成分的最小单位。 6.由PL0的EBNF可知，PL0语言可看成是PASCAL语言的子集，它的编译程序是一个_。 7.由于PL0编译程序采用_，所以语法分析过程BLOCK是整个编译过程的核心。 8.用语法图描述语法规

2、则的优点是_、_。 9.每个非终结符是一个语法成分，在书写语言程序时并不出现，它是由_和_、或终结符串定义的。 10.PL0的目标程序为假想栈式计算机的汇编语言，与具体计算机_。 11.PL0的编译程序和目标程序的解释执行程序都是用_书写的，因此PL0语言可在配备_的任何机器上实现。 12.PL0编译程序是用PASCAL语言书写的，整个编译程序(包括主程序)是由_个嵌套及并列的过程或函数组成 13.当源程序编译正确时，PL0编译程序自动调用_，对目标代码进行解释执行，并按用户程序要求输入数据和输出运行结果。 14.由于对某些非终结符可以递归定义，这就使得_可用有穷的文法描述。 15. _的任务

3、是识别由词法分析给出的单词符号序列在结构上是否符合给定的文法规则。 16. PL0编译程序的语法分析采用了_。 17.语法分析程序除总控外主要有两大部分的功能，即_和_. 18.PL0的词法分析程序GETSYM，是一个独立的过程，其功能是为_提供单词用的， 是_的基础，它把输入的字符串形式的源程序分割成一个个单词符号。 19.每个过程应有过程首部以定义局部于它自己过程的常量、变量和过程标识符，也称_。 20.词法分析程序GETSYM将完成的任务有:_, 识别保留字；_,拼数,拼复合词,输出源程序. 21.如果一个PL0语言的单词序列在整个语法分析中，都能逐个得到匹配，直到_，这时就说所输入的程

4、序是正确的。 22.若要构造程序设计语言的编译程序，则首先要对程序设计语言本身有较为精确的描述。而关于程序设计语言的描述，将涉及_、语义和_三个方面。 23.凡是具有某种特殊性质的客体的聚合，都可称为_。 24.如果集合中元素个数为零，即集合中不含有任何元素，这样的集合称为_，记为。 25.设有集合A和B，如果A和B有相同的元素，则称这两个集合是_. 26.设A、B为任意两个集合，由所有属于集合A或属于集合B的元素组成的集合，叫做集合A与B的_ 27. 设A、B为任意两个集合，由所有用于集合A且属于集合B的元素组成的集合，称为集合A与B的_. 28. 如果一个集合，它能包含我们所要考虑目标之内

5、的所有元素，则称此集合为_，记为E。 29.设A为一集合，由A的所有子集(包括空集及A本身)所组成的集合，称为A的_. 30. 由两个按一定次序排列的客体组成的序列，称为_. 31. 设A和B为任意两个集合，若序偶的第一个成员是集合A的一个元素，第二个成员是集合B的一个元素，则所有这样的序偶组成的集合称为集合A和B的_. 32.在集合X上的关系R，如对任意xX，均有(x，x) R，则称关系R是_。 33.在集合X上的关系R，如果合(x，y) R，便必有(y，x) R，则称关系R是_。 34.在集合X上的关系R，如果合(x，y) R且(y，z) R，必有(x，z) R，则称关系R是_。 35.例

6、 设 P=， Q=， 则PQ=_ 36.符号串与符号组成顺序_，如符号串ab_ba，符号申001也_010。 37.假设G是一个文法，S是文法的开始符号，如果S=*x,则称x是_。 38. 文法G产生的_的全体是该文法描述的语言。 39.一个文法GZ若存在推导序列Z=+Z, 则称G(z)是_文法，这类文法所产生的句子有_个。 40.乔姆斯基把文法分成_类型. 41.四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是_. 42.最右推导常被称为_。 43.由规范推导所得的句型称为_。 44.文法的二义性和语言的二义性是两个_的概念。 45.对于上下文无关文法，_是句型推导过程的几何表示。

7、46.直接短语也称_. 47.每棵语法树的叶子组成一个_. 48.每棵子树的叶子组成一个_. 49. 每棵简单子树的叶子组成一个_. 50. 最左边简单子树的叶子组成_. 51.一个句型的最左直接短语称为该句型的_。 52.关于句型或句子的直接推导=和推导=+，实际上均可视为符号串之间关系，而且推导=+为直接推导=的_。 53. _是语言文法的等价表示，可用它来代替BNF规则集合。 54.某条规则Uu中的左部符号U(U不是识别符号)，不在所属文法的任何其他规则右部出现，那么这条规则在推导中不起作用，即所有句子的推导始终不会用到此规则，显然这种规则是多余的。也称这种非终结符为_. 55.从文法的

8、某个非终结符号U推不出终结符号串，显然，所有含有U的规则是多余的。也称这种非终结符为_。 56.若L是上下文有关语言、上下文无关语言或正规语言，则L和L - 分别是上下文有关语言、_和正规语言。 57.设有文法G，对于其中某一非终结符号U可能作出一些不同推导U =+ Sx，其中S叫头符号，由于推导不同，由U产生的头符号S也可能不同，这些头符号S构成的集合，称为U的推导的_. 58.一个上下文无关文法G包括四个组成部分依次是：_,_,_,_.11 59.文法所描述的语言是_的集合。 60.词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称_。 二、选择 1.编译程

9、序是一种常用的_软件。 A.应用 B.系统 C.工具 D.测试 2.在使用高级语言编程时，首先可通过编译程序发现源程序的全部_错误和部分_错误。 A.语法 B.语义 C.语用 D.运行 3.编译程序生成的目标程序_是机器语言的程序。 A.一定 B.不一定 C.某种情况下一定 D.某种情况下不一定 4.编译程序生成的目标程序_是可执行的程序。 A.一定 B.不一定 C.某种情况下一定 D.某种情况下不一定 5.一个语言的文法是_. A惟一的 B不惟一的 C.个数有限的 D.无限的 6.巴科斯-诺尔范式(即BNF)是一种广泛采用的_的工具。 A描述规则 B.描述语言 C描述文法 D描述句子 7.

10、设r=(a|b|c)(x|y|z)则L中元素为 个 A9 B6 C18 D27 8、正则集合L=an|n0相应的正则表达式是 Aa* Ba+ Caa* Daa+ 9. 编译过程中扫描器的任务包括_。 组织源程序的输入 按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出 删除注解 删除空格及无用字符 行计数、列计数 发现并定位词法错误 建立符号表 A B C D 10、编译过程中，语法分析器的任务是_ 。 a.分析单词是怎样构成的 b.分析单词串是如何构成语句和说明的 c.分析语句和说明是如何构成程序的 d.分析程序的结构 A.bc Bd Cbcd Dabcd 11、语法分析的常用方法

11、是_ 。 a.自顶向下 b.自底向上 c.自左向右 d.自右向左 Aabcd Bab Ccd Dabc 12、 编译程序中的语法分析器接受以_为单位的输入，并产生有关信息供以后各阶段使用。 A表达式 B产生式 C单词 D语句 13、LL(1)文法的条件是_。 A对形如U-Xl|X2|Xn的规则，要求FIRST(Xi)FIRST(Xj)=，(ij) B对形如U-Xl|X2|Xn的规则，若Xi=*，则要求FIRST(Xj)FOLLOW(U) = CA和B D都不是 14、一个右线性文法G一定是 ALL文法 CSLR文法 BLR文法 D上述三者都不是 15、算符文法是指_的文法。26 没有形如U-V

12、W的规则(U，V，WVN) 终结符号集VT中任意两个符号对之间至多有一种优先关系成立 没有相同的规则右部 没有形如U-的规则 A. B C D 16、算符优先文法是指_的文法。 没有形如U-VW的规则(U，V，WVN) 终结符号集VT中任意两个符号对之间至多有一种优先关系成立 没有相同的规则右部 没有形如U-的规则 A. B C. D 17、下列文法GS的句型aRaSbaTb,b 的最左素短语 为_。 S-aTb|， T-R R-RS|S A.aTb B.aSb C.S D.R 18、算符优先分析法每次都是对_进行归约，简单优先分析法每次都是对句柄进行归约。 A最左短语 B.简单短语 C. 最

13、左素短浯 D素短语 19、xab + cde -*f/:=是赋值语句( ) 相应的后缀式 Ax:=a+b+c*d-e/f Bx:=a+(b+c)*d-e/f Cx:+a+b+c*(d-e)/f Dx:=a+b+c+(c*d)-e/f 20、LR(K)方法是_。 A从左到右分析，每次走K步的一种编译方法 B从左到右分析，共经过K步的一种编译方法 C从左到右分析，每次向前预测K步的一种编译方法 D从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法 21、下面三个文法中，为SLR(1)文法的是_。10 G1：P-PaP|b G2：P-bPb|cPc|b|c G3：P-bPb|bPc|

14、d A.仅Gl B仅G2 C仅G3 DG2和G3 22、有下列文法：11 S-Pa|Pb|c P-Pd|Se|f 该文法是_。 A.LL(1)文法 B.SLR(1)文法 C.a和b D.都不是 23代码优化的主要目标是( )12 如何提高目标程序的运行速度 如何减少目标程序运行所需的空间 如何协调和 如何使生成的目标代码尽可能短 A B C D 24、设文法G产生式如下： SaSb|ab| 则G是一个 ALR文法 BSLR文法 C三型文法 D二型文法 25 在编译程序采用的优化方法中，_ 是在循环语句范围内进行的。12 合并已知常量 删除多余运算， 删除归纳变量 强度削弱 代码外提 A B C

15、 D 26 合并表达式中常量运算的目的是_。12 合并常量，使表达式中的常量尽可能少 合并常量，使表达式尽可能简短 将可在编译时刻计算的常量运算在编译时刻计算出来，然后用所计算出来的值替换表达式中出现的所有这种常量运算，使得生成的代码指令尽可能少 A B C D 27 下面的程序段可以进行哪些优化_。12 i：= 1 j：= l0 read k L：x：= x*i y：= j*i z：= x*y write j i：= i+1 if iI1/I0/Ia/Ic/a/b/c 判断下面符号串中哪些是该文法的句子. (1) ab0 (2)a0c01 (3)aaa (4)bc10 (5)aabc (6)

16、bbca 19.为了正确地对源程序进行编译，不允许文法有二义性，那么怎样才能排除文法的二义性呢?9 20.什么是简单子树？ 21.什么是子树？ 22.什么是句型的分析？ 23.自下而上分析算法的基本思想是什么？ 24.设有文法G： s:=Qc|c Q:=Rb|b R:=Sa|a 试求HARD(S),HARD(Q),HARD(R). 四、综合题 1. While a0 b0 do Begin X：X1； if a0 then a：a1 else b：b1 End； 翻译成四元式序列。 2. 设布尔表达式的文法为 (1)(2) E EE (1)(2) E E E E i 假定它们将用于条件控制语句

17、中，请 (1) 改写文法，使之适合进行语法制导翻译和实现回填； (2) 写出改写后的短个产生式的语义动作。 3. 设文法G(S)： S(L)|a S|a LL，S|S (1) 消除左递归和回溯； (2) 计算每个非终结符的FIRST和FOLLOW； 4. 对下列文法G: 26 S-#S# S-D(R) R-R; P|p P-S|i D-i 计算文法中每个非终结符的FIRSTVT集和LASTVT集 。 5. 将下列赋值语句译成三地址代码。 Ai,j :=Bi,j + CAk,l + Di+j 6、设布尔表达式的文法为 E E(1)E(2) E E(1)E(2) E i 假定它们将用于条件控制语句

18、中，请 (1)改写文法，使之适合进行语法制导翻译和实现回填； (2)写出改写后的短个产生式的语义动作。 7、 给定PASCAL程序语句 while ab do if a0 then a:=a-1 else a:=a+1; 1. 将该语句翻译成逆波兰式； 2. 给出编译程序扫描到then处及分号处时所得的四元式序列。 8.如何计算FIRST集？ 更多课程资料请到大学课程网www.0206.cc学习 编译原理练习测试题库参考答案 一、填空 1.机器语言程序或汇编程序 2.结构 3.编译程序 4.源程序，目标程序。 5.终结符 6.编译解释执行系统 7.一趟扫描方法 8.直观、易读 9.终结符和非终

19、结符串 10.无关 11.PASCAL语言 12.18 13.解释执行程序 14.无穷的句子集 15.语法分析 16.自顶向下的递归子程序法 17.说明部分的处理,程序体部分的处理 18.语法分析,语法分析 19局部量 20滤空格,识别标识符,输出源程序 21程序结束符 22.语法,语用 23.集合 24.空集 25.相等的 26.并集 27.交集 28.全集 29.幂集 30.序偶 31.笛卡尔乘积 32.自反的 33.对称的 34.传递的 35.， 36.有关,不同于,不同于 37.句型 38.句子 39.(1)递归 (2)无数 40.四种 41.上下文无关的 42.规范推导 43.规范句

20、型 44.不同 45.语法树 46.简单短语 47.句型 48.短语 49.简单短语 50.句柄 51.句柄 52.传递闭包 53.语法图 54.不可达到的 55.不可终止的 56.上下文无关语言 57.头符号集合 58.终结符号，非终结符号，开始符号，产生式 59.由文法的识别符推出的所有终结符号串 60.输入缓冲区 二、选择 1.B 2.A 3.B 4.B 5.B 6.B 7.B 8.A 9.D 10.C 11.B 12.C 13.C 14.A 15.A 16.D 17.B 18. D 19.A 20.D 21.C 22.B 23.B 24.D 25.D 26.D 27.C 28.D 29

21、.D 30.C 31.B 32.B 33.A 34.A 35.A 36.C 37.B 38.A 39.B 40.A 三、简答题 1.答：含有优化功能的编译程序，其优化是指对生成的目标代码进行优化，而不是编译程序本身得到优化，它提高目标代码的效率，而不是编译程序的效率。所以，上述说法不对。 2.答：不正确。编译程序的五个组成部分中，词法分析，语法分析，语义分析和代码生成是必须完成的，而代码优化是为了提高目标程序的质量，它不是必需的，没有优化部分的编译程序也能生成目标代码。 3.指令寄存器,程序地址寄存器,栈顶寄存器,基址寄存器 4. (1)对于一些易于校正的错误，如丢了逗号、分号等，则指出出错位

22、置，并加以校正。校正的方式就是补上逗号或分号。 (2)对某些错误，编译程序难于确定校正的措施，为了使当前的错误不致影响整个程序的崩溃，把错误尽量局限在一个局部的语法单位中。这样就需跳过一些后面输入的单词符号，直到读入一个能使编译程序恢复正常语法分析工作的单词为止。 5. LIT：将常量值取到运行栈顶。LOD：将变量放到栈顶。STO：将栈顶的内容送入某变量单元中。CAL：调用过程的指令。INT：为被调用的过程(或主程序)在运行栈中开辟数据区。JMP：无条件转移指令。JPC：条件转移指令。OPR：关系运算和算术运算指令。将栈顶和次栈顶的内容进行运算，结果存放在次栈顶，此外还可以是读写等特殊功能的指

23、令 6. 句型 归约规则 句柄 (a，a)，a) Sa a (S，a)，a) TS S (T，a)，a) Sa a (T，S)，a) TT，S T，S (S)，a) TS S (T)，a) SS(T) (T) (S，a) TS S (T，a) Sa a (T，S) TT，S T，S (T) S(T) (T) S 7. 优化：对程序进行各种等价变换，使得从变换后的程序出 发，能产生更有效的目标代码。 三种级别：局部优化、循环优化、全局优化。 8. 目标代码通常采用三种形式：机器语言，汇编语言，待装配 机器语言模块。 应着重考虑的问题： (1)如何使生成的目标代码较短； (2)如何充分利用寄存器，

24、以减少访问内存次数； (3)如何充分利用指仅系统的的特点。 9. 逆波兰表示： abc*ab/d 三元式序列： (*，b，c) (，a，) (，a，b) (/，) (，d) 10. 文法G(N)： NAB|B AAC|D B1|3|5|7|9 DB|2|4|6|8 C0|D 11 编译过程的六个阶段的任务，再加上表格管理和出错处理的工作可分别由几个模块或程序完成，它们分别称作词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。 12 自反的 在集合X上的关系R，如对任意xX，均有(x，x) R，则称关系R是自反的。 非自反的

25、在集合X上的关系R，如对任意xX，均有(x，x)R，则称关系R是非自反。 对称的 在集合X上的关系R，如果合(x，y) R，便必有(y，x) R，则称关系R是对 称的。 非对称的 在集合X上的关系R，如果有(x，y) R丛xy，便必有(y，x)R，则称关系R是非对称的。 传递的 在集合X上的关系R，如果合(x，y) R且(y，z) R，必有(x，z) R，则称关系R是传递的。 13. 元素的非空有穷集合。字母表中的元素。由字母表中的符号组成的任何有穷序列，惯用小写字母t、u、v、x、y表示符号串。长度是符号串所含符号的个数。设有符号串x和y，把y的符号写在x的符号之后所得的符号串，叫做x与y的

26、联结，记为xy。 14答：从所给符号串x开始，在其中寻找与文法的某条规则右部相匹配的子串，并用该规则的左部取代此子串(即归约)，重复此过程，步步向上归约，最后试图将符号串x归约到文法的识别符号Z。如归约成功，则符号串x是文法的句子。 15 HARD(S)=S,Q,R,a,b,c HARD(Q)=S,Q,R,a,b,c HARD(R)=S,Q,R,a,b,c 16 S:=aABb|ab A:=ab B:=Aa|a 17传名：a12 传值：a6 18. (1)错误 (2)正确 (3)正确 (4)正确 (5)错误 (6)错误 (7)错误 19.(1)在语义上加些限制，或者说加一些语法的非形式规定。这

27、样做不必改变文法中原有的语法规则。 (2)把排除二义性的规则合并到原有文法中，即构造一个等价的无二义性的文法G。这样做，需要改造原有文法。 20.只有单层分支的子树称为简单子树。 21.由某一结点及其所有分支组成的部分，成为原语法树的一棵子树。 22.句型的分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。 23.从所给符号串x开始，在其中寻找与文法的某条规则右部相匹配的子串，并用该规则的左部取代此子串(即归约)，重复此过程，步步向上归约，最后试图将符号串x归约到文法的识别符号Z。如归约成功，则符号串x是文法的句子。 24. HARD(S)=S,Q,R,a,b,c HARD(Q)

28、=S,Q,R,a,b,c HARD(R)=S,Q,R,a,b,c 四、综合题 每题10分，3题共30分 1. 解： (1) (j，a，0，5) (2) (j，3) (3) (j，b，0，5 (4) (j，15) (5) (，1，T1) (6) (：，T1，) (7) (j，a，0，9) (8) (j，12) (9) (，a，1，T2) (10) (：，T2，a) (11) (j，1) (12) (，b，1， T3) (13) (：，T3，b) (14) (j，1) 2. 解：(1) E0E(1) EE0E(2) EAE(1) EEAE(2) Ei (2) EE(1) BACKPATCH(E(1

29、)FC，NXQ)； E0TC：E(1)TC EE0E(2) EFC：E(2)FC； ETC：MERG(E0TC，E(2)TC) EAE(1) BACKPATCH(E(1)TC，NXQ)； E0FC：E(1)FC EEAE(2) ETC：E(2)TC； EFC：MERG(EAFC，E(2)FC) Ei ETC：NXQ；EFC：NXQ1； GEN(jn2，entry(i)，0)； GEN(j，0) 3解： (1) S(L)|aS SS| LSL LSL| (2) FIRST)S)(，a FIRST(S)，a, FIRST(L)(，a FIRST(L)， (3) FOLLOW(S)#，) FOLLO

30、W(S)#，) FOLLOW(L) ) FOLLOW(L ) a ， ( ) S S L L SaS S(L) SS S SS S S LSL LSL L L 4.(1) 文法G中每个非终结符的FIRSTVT集和LASTVT集为： FIRSTVT(s)=# FIRSTVT(P)=i, FIRSTVT(s)=(,i) FIRSTVT(D)=i FIRSTVT(R)=;,(,i) (2) 文法G中每个非终结符的LASTVT集为： LASTVT(S)=# LASTVT(P)=i, LASTVT(S)= LASTVT(D)=i LASTVT(R)=;,i 5. t11 := i * 20 t12 :=

31、 t11+j t13 := A-84; t14 := 4*t12 t15 := t13t14 /Ai,j t21 := i*20 t22 := t21+j t23 := B-84; t24 := 4*t22 t25 := t23t24 /Bi,j t31 := k*20 t32 := t31+l t33 := A-84 t34 := 4*t32 t35 := t33t34 /Ak,l t36 := 4*t35 t37 := C-4 t38 := t37t36 /CAk,l t41 := i+j t42 := 4*t41 t43 := D-4 t44 := t43t42 /Di+j t1 := t25 +t38 t2 := t1 + t44 t23t24 := t2 6. 解：(1) E0E(1) EE0E(2) EAE(1) EEAE(2) Ei (2) EE(1) BACKPATCH(E(1)FC，NXQ)； E0TC：E(1)TC EE0E(2) EFC：E(2)FC； ETC：MERG(E0TC，E(2)TC) EAE(1) BACKPATCH(E(1)TC，NXQ)； E0FC：E(1)FC EEAE(2) ETC：E(2)TC；