编译原理练习题库.pdf

大学课程大学课程编译原理练习测试题库编译原理练习测试题库 一、填空一、填空 1.若源程序是用高级语言编写的，目标程序是_，则其翻译程序称为编译程序。 2.词法分析和语法分析本质上都是对源程序的_进行分析。 3.如果源语言(编写源程序的语言)是高级语言， 而目标语言是某计算机的汇编语言或机器语 言，则这种翻译程序称为_。 4.对编译程序而言，输入数据是_,输出结果是_。 5. _，是构成语言文法的单词，是语法成分的最小单位。 6.由 PL0 的 EBNF 可知，PL0 语言可看成是 PASCAL 语言的子集，它的编译程序是一个 _。 7.由于 PL0 编译程序采用_，所以语法分析过程 BLOCK 是整个编译过程的核心。 8.用语法图描述语法规则的优点是_、_。 9.每个非终结符是一个语法成分，在书写语言程序时并不出现，它是由_和 _、或终结符串定义的。 10.PL0 的目标程序为假想栈式计算机的汇编语言，与具体计算机_。 11.PL0 的编译程序和目标程序的解释执行程序都是用_书写的， 因此 PL0 语言可 在配备_的任何机器上实现。 12.PL0 编译程序是用 PASCAL 语言书写的， 整个编译程序(包括主程序)是由_个嵌套 及并列的过程或函数组成 13.当源程序编译正确时，PL0 编译程序自动调用_，对目标代码进行解释执行， 并按用户程序要求输入数据和输出运行结果。 14.由于对某些非终结符可以递归定义，这就使得_可用有穷的文法描述。 15. _的任务是识别由词法分析给出的单词符号序列在结构上是否符合给定的文法规 则。 16. PL0 编译程序的语法分析采用了_。 17.语法分析程序除总控外主要有两大部分的功能，即_和_. 18.PL0 的词法分析程序 GETSYM， 是一个独立的过程， 其功能是为_提供单词用的， 是_的基础，它把输入的字符串形式的源程序分割成一个个单词符号。 19.每个过程应有过程首部以定义局部于它自己过程的常量、 变量和过程标识符， 也称_。 20.词法分析程序 GETSYM 将完成的任务有:_, 识别保留字；_,拼数,拼复合词, 输出源程序. 21.如果一个 PL0 语言的单词序列在整个语法分析中， 都能逐个得到匹配， 直到_， 这时就说所输入的程序是正确的。 22.若要构造程序设计语言的编译程序，则首先要对程序设计语言本身有较为精确的描述。 而关于程序设计语言的描述，将涉及_、语义和_三个方面。 23.凡是具有某种特殊性质的客体的聚合，都可称为_。 24.如果集合中元素个数为零， 即集合中不含有任何元素， 这样的集合称为_， 记为 。 25.设有集合 A 和 B，如果 A 和 B 有相同的元素，则称这两个集合是_. 26.设 A、B 为任意两个集合，由所有属于集合 A 或属于集合 B 的元素组成的集合，叫做集合 A 与 B 的_ 27. 设 A、B 为任意两个集合，由所有用于集合 A 且属于集合 B 的元素组成的集合，称为集 合 A 与 B 的_. 28. 如果一个集合，它能包含我们所要考虑目标之内的所有元素，则称此集合为_，记 为 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.例 设 P=（1，2） ， （3，4） ， （2，2） Q=（4，7） ， （2，9） ， （3，1） 则 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.对于上下文无关文法，_是句型推导过程的几何表示。 46.直接短语也称_. 47.每棵语法树的叶子组成一个_. 48.每棵子树的叶子组成一个_. 49. 每棵简单子树的叶子组成一个_. 50. 最左边简单子树的叶子组成_. 51.一个句型的最左直接短语称为该句型的_。 52.关于句型或句子的直接推导“=“和推导“=+“， 实际上均可视为符号串之间关系， 而且推 导“=+“为直接推导“=“的_。 53. _是语言文法的等价表示，可用它来代替 BNF 规则集合。 54.某条规则 Uu 中的左部符号 U(U 不是识别符号)，不在所属文法的任何其他规则右部出 现，那么这条规则在推导中不起作用，即所有句子的推导始终不会用到此规则，显然这种规 则是多余的。也称这种非终结符为_. 55.从文法的某个非终结符号 U 推不出终结符号串，显然，所有含有 U 的规则是多余的。也 称这种非终结符为_。 56.若 L 是上下文有关语言、上下文无关语言或正规语言，则 L 和 L - 分别是上 下文有关语言、_和正规语言。 57.设有文法 G，对于其中某一非终结符号 U 可能作出一些不同推导 U =+ Sx，其中 S 叫头 符号，由于推导不同，由 U 产生的头符号 S 也可能不同，这些头符号 S 构成的集合，称为 U 的推导的_. 58.一个上下文无关文法 G 包括四个组成部分依次是：_,_,_,_.11 59.文法所描述的语言是_的集合。 60.词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓 冲区称_。 二、选择二、选择 1.编译程序是一种常用的_软件。 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. 设 r=(a|b|c)(x|y|z)则 L（r）中元素为 个（ ） 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、语法分析的常用方法是_ 。 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（1）文法 CSLR（1）文法 BLR（1）文法 D上述三者都不是 15、算符文法是指_的文法。26 没有形如 U-VW的规则(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. 最左素短浯 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|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（S 为其开始符号）产生式如下： SaSb|ab| 则 G 是一个（ ） ALR（1）文法 BSLR（1）文法 C三型文法 D二型文法 25 在编译程序采用的优化方法中，_ 是在循环语句范围内进行的。12 合并已知常量 删除多余运算， 删除归纳变量 强度削弱 代码外提 A B C 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)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. 设布尔表达式的文法为 E E (1)E(2) E E (1) E(2) E i 假定它们将用于条件控制语句中，请 (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(