《编译原理》练习测试题库.docVIP

华中师范大学网络教育学院编译原理练习测试题库一、填空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包括四个组成部分依次是：_,_,_,_.1159.文法所描述的语言是_的集合。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 D278、正则集合L=an|n0相应的正则表达式是（ ） Aa* Ba+ Caa* Daa+9. 编译过程中扫描器的任务包括_。 组织源程序的输入 按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出 删除注解 删除空格及无用字符 行计数、列计数 发现并定位词法错误 建立符号表 A B C D10、编译过程中，语法分析器的任务是_ 。 a.分析单词是怎样构成的 b.分析单词串是如何构成语句和说明的 c.分析语句和说明是如何构成程序的 d.分析程序的结构 A.bc Bd Cbcd Dabcd11、语法分析的常用方法是_ 。 a.自顶向下 b.自底向上 c.自左向右 d.自右向左 Aabcd Bab Ccd Dabc12、 编译程序中的语法分析器接受以_为单位的输入，并产生有关信息供以后各阶段使用。 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 D16、算符优先文法是指_的文法。 没有形如U-VW的规则(U，V，WVN) 终结符号集VT中任意两个符号对之间至多有一种优先关系成立 没有相同的规则右部 没有形如U-的规则 A. B C. D17、下列文法GS的句型aRaSbaTb,b 的最左素短语 为_。 S-aTb|， T-R R-RS|S A.aTb B.aSb C.S D.R18、算符优先分析法每次都是对_进行归约，简单优先分析法每次都是对句柄进行归约。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/f20、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 D27 下面的程序段可以进行哪些优化_。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)bbca19.为了正确地对源程序进行编译，不允许文法有二义性，那么怎样才能排除文法的二义性呢?920.什么是简单子树？ 21.什么是子树？ 22.什么是句型的分析？23.自下而上分析算法的基本思想是什么？24.设有文法G：s:=Qc|cQ:=Rb|bR:=Sa|a试求HARD(S),HARD(Q),HARD(R).25编译程序和高级语言有什么区别?26编译程序的工作分为那几个阶段?27简述自下而上的分析方法。28简述代码优化的目的和意义。六、综合题1. Whilea0 b0do BeginX：X1；if a0 then a：a1else b：b1End；翻译成四元式序列。2. 设布尔表达式的文法为E E(1)E(2)E E(1) E(2)E i假定它们将用于条件控制语句中，请(1) 改写文法，使之适合进行语法制导翻译和实现回填；(2) 写出改写后的短个产生式的语义动作。3. 设文法G(S)：S(L)|a S|aLL，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+j6、设布尔表达式的文法为 E E(1)E(2) E E(1)E(2) E i 假定它们将用于条件控制语句中，请 (1)改写文法，使之适合进行语法制导翻译和实现回填； (2)写出改写后的短个产生式的语义动作。7、 （8分）给定PASCAL程序语句while ab do if a0 then a:=a-1 else a:=a+1;1. 将该语句翻译成逆波兰式；2. 给出编译程序扫描到then处及分号处时所得的四元式序列。8.如何计算FIRST集？9证明下述文法G：SaSbS|aS|d是二义性文法。10对于文法GS：SAB，AAa|bB，Ba|Sb求句型baSb的全部短语、直接短语和句柄？句型baSb的语法树如图五(2)所示。ASBbBSab图五(2) 句型baSb的的语法树11设有非确定的有自限动机NFA M=(A，B，C，0，1，d，A，C)，其中：d (A，0)=C d (A，1)=A，B d (B，1)=C d (C，1)=C。请画出状态转换距阵和状态转换图。华中师范大学网络教育学院编译原理练习测试题库参考答案一、填空1.机器语言程序或汇编程序2.结构3.编译程序4.源程序，目标程序。5.终结符6.编译解释执行系统7.一趟扫描方法8.直观、易读9.终结符和非终结符串10.无关11.PASCAL语言12.1813.解释执行程序14.无穷的句子集15.语法分析16.自顶向下的递归子程序法17.说明部分的处理,程序体部分的处理18.语法分析,语法分析19局部量20滤空格,识别标识符,输出源程序21程序结束符22.语法,语用23.集合24.空集25.相等的26.并集27.交集28.全集29.幂集30.序偶31.笛卡尔乘积32.自反的33.对称的34.传递的35.（1，9），（3，7），（2，5）36.有关,不同于,不同于37.句型 38.句子39.(1)递归 (2)无数40.四种41.上下文无关的42.规范推导43.规范句型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.D 30.C31.B 32.B 33.A 34.A 35.A 36.C 37.B 38.A 39.B 40.A 41.A 42.C 43.D 44.C 45.B 46.B 47.A 48.D 49.C 50.C51 A 52 C 53 D 54 C 55 B 56 B 57 A 58 D 59 C 60 C3 名词解释题1词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。2若文法的任何两个产生式A a | b都满足下面两个条件：（1）FIRST(a ) FIRST(b ) = f；（2）若b * e ，那么FIRST(a ) FOLLOW( A ) = f。 我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。3句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号S。(2)每个节点的标记都是V中的一个符号。(3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2AR，那么AA1A2AR一定是P中的一条产生式。(4)若一标记为A的节点至少有一个除它以外的子孙，则AVN。(5)若树的所有叶节点上的标记从左到右排列为字符串w，则w是文法G的句型；若w中仅含终结符号，则w为文法G所产生的句子。4 所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。5文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法G定义为四元组的形式：G=(VN，VT，P，S)其中：VN 是非空有穷集合，称为非终结符号集合；VT 是非空有穷集合，称为终结符号集合；P是产生式的集合(非空)；S是开始符号(或识别符号)。这里，VNVT=，SVN。V=VNVT，称为文法G的字母表，它是出现文法产生式中的一切符号的集合。文法G所描述的语言用L(G)表示，它由文法G所产生的全部句子组成，即L(G)=x| S*x，其中S为文法开始符号，且 简单的说，文法描述的语言是该文法一切句子的集合。四 判断题1、 2、 3、 4、 5、 6、 7、 8、 9、 10、五、简答题1.答：含有优化功能的编译程序，其优化是指对生成的目标代码进行优化，而不是编译程序本身得到优化，它提高目标代码的效率，而不是编译程序的效率。所以，上述说法不对。2.答：不正确。编译程序的五个组成部分中，词法分析，语法分析，语义分析和代码生成是必须完成的，而代码优化是为了提高目标程序的质量，它不是必需的，没有优化部分的编译程序也能生成目标代码。3.指令寄存器,程序地址寄存器,栈顶寄存器,基址寄存器4. (1)对于一些易于校正的错误，如丢了逗号、分号等，则指出出错位置，并加以校正。校正的方式就是补上逗号或分号。 (2)对某些错误，编译程序难于确定校正的措施，为了使当前的错误不致影响整个程序的崩溃，把错误尽量局限在一个局部的语法单位中。这样就需跳过一些后面输入的单词符号，直到读入一个能使编译程序恢复正常语法分析工作的单词为止。5. LIT：将常量值取到运行栈顶。LOD：将变量放到栈顶。STO：将栈顶的内容送入某变量单元中。CAL：调用过程的指令。INT：为被调用的过程(或主程序)在运行栈中开辟数据区。JMP：无条件转移指令。JPC：条件转移指令。OPR：关系运算和算术运算指令。将栈顶和次栈顶的内容进行运算，结果存放在次栈顶，此外还可以是读写等特殊功能的指令6. 句型归约规则句柄(a，a)，a)Saa(S，a)，a)TSS(T，a)，a)Saa(T，S)，a)TT，S T，S(S)，a) TSS(T)，a) SS(T) (T)(S，a) TSS(T，a) Saa(T，S) TT，S T，S(T) S(T)(T)S7. 优化：对程序进行各种等价变换，使得从变换后的程序出 发，能产生更有效的目标代码。 三种级别：局部优化、循环优化、全局优化。8. 目标代码通常采用三种形式：机器语言，汇编语言，待装配 机器语言模块。 应着重考虑的问题： (1)如何使生成的目标代码较短； (2)如何充分利用寄存器，以减少访问内存次数； (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|D11 编译过程的六个阶段的任务，再加上表格管理和出错处理的工作可分别由几个模块或程序完成，它们分别称作词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。12 自反的 在集合X上的关系R，如对任意xX，均有(x，x) R，则称关系R是自反的。 非自反的 在集合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的联结，记为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,c16 S:=aABb|ab A:=ab B:=Aa|a17传名：a12 传值：a618. (1)错误 (2)正确 (3)正确 (4)正确 (5)错误 (6)错误 (7)错误19.(1)在语义上加些限制，或者说加一些语法的非形式规定。这样做不必改变文法中原有的语法规则。 (2)把排除二义性的规则合并到原有文法中，即构造一个等价的无二义性的文法G。这样做，需要改造原有文法。20.只有单层分支的子树称为简单子树。21.由某一结点及其所有分支组成的部分，成为原语法树的一棵子树。22.句型的分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。23.从所给符号串x开始，在其中寻找与文法的某条规则右部相匹配的子串，并用该规则的左部取代此子串(即归约)，重复此过程，步步向上归约，最后试图将符号串x归约到文法的识别符号Z。如归约成功，则符号串x是文法的句子。24.HARD(S)=S,Q,R,a,b,c HARD(Q)=S,Q,R,a,b,c HARD(R)=S,Q,R,a,b,c25 用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器语言表示的目标程序（这个过程即编译），才能由计算机执行。执行转换过程的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转换过的叫目标程序，也就是机器语言。 编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来将汇编语言编写的程序，按照一一对应的关系，转换成用机器语言表示的程序。解释型编译程序将高级语言程序的一个语句，先解释成为一组机器语言的指令，然后立即执行，执行完了，取下一组语句解释和执行，如此继续到完成一个程序止。用解释型编译程序，执行速度很慢，但可以进行人和计算机的对话，随时可以修改高级语言的程序。BASIC语言就是解释型高级语言。编译型编译程序将级语言编写的程序，一次就会部翻译成机器语言表示的程序，而且过程进行很快，在过程中，不能进行人机对话修改。FORTRAN语言就是编译型高级语言。26词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端)，而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序27 所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。28 代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目标程序运行时所需要的时间短，同时所占用的存储空间少。五、综合题每题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，