大学课程《编译原理》练习测试题库

\h大学课程《编译原理》练习测试题库一、填空若源程序是用高级语言编写的，目标程序是 ，则其翻译程序称为编译程序。词法分析和语法分析本质上都是对源程序的 进行分析。如果源语言(编写源程序的语言)是高级语言而目标语言是某计算机的汇编语言或机器语言，则这种翻译程序称为 。对编译程序而言，输入数据是 ,输出结果是 。 ，是构成语言文法的单词，是语法成分的最小单位。PL／0EBNF，PL／0PASCAL 。由于PL／0编译程序采用 法分析过程BLOCK是整个编译过程的核心。用语法图描述语法规则的优点是 、 。每个非终结符是一个语法成分，在书写语言程序时并不出现，它是由 和 、或终结符串定义的。的目标程序为假想栈式计算机的汇编语言，与具体计算机 。的编译程序和目标程序的解释执行程序都是用 在配备 的任何机器上实现。个嵌套及并列的过程或函数组成调用 并按用户程序要求输入数据和输出运行结果。由于对某些非终结符可以递归定义，这就使得 可用有穷的文法描述。 的任务是识别由词法分析给出的单词符号序列在结构上是否符合给定的文法规则。PL／0编译程序的语法分析采用了 。语法分析程序除总控外主要有两大部分的功能，即 和 .PL／0词法分程序GETYM是一独立过其功能是为 提供单用的是 的基础，它把输入的字符串形式的源程序分割成一个个单词符号。每个过程应有过程首部以定义局部于它自己过程的常量变量和过程标识符也称 。词法分析程序GETSYM将完成的任务有: ,识别保留字； ,拼数,拼复合词,输出源程序.如果一个PL／0语言的单词序列在整个语法分析中都能逐个得到匹配直到 ，这时就说所输入的程序是正确的。若要构造程序设计语言的编译程序，则首先要对程序设计语言本身有较为精确的描述。而关于程序设计语言的描述，将涉及 、语义和 三个方面。凡是具有某种特殊性质的客体的聚合，都可称为 。如果集合中元素个数为零即集合中不含有任何元素这样的集合称为 记为φ。设有集合A和B，如果A和B有相同的元素，则称这两个集合是 .设AB为意两个合由所有于集合A或于集合B元素组的集合叫集A与B的 ．B为任意两个集合，由所有用于集合A且属于集合B的元素组成的集合，称为集合A与B的 .如果一个集合，它能包含我们所要考虑目标之内的所有元素，则称此集合为 ，记为E。设A为一集合，由A的所有子集(包括空集及A本身)所组成的集合，称为A的 .由两个按一定次序排列的客体组成的序列，称为 .设A和B为任意两个集合若序偶的第一个成员是集合A的一个元素第二个成员是集合B的一个元素，则所有这样的序偶组成的集合称为集合A和B的 .集合X上的关系R，如对任意x∈X，均有(x，x)∈R，则称关系R是 。。在集合X上的关系R，如果合(x，y)∈R且(y，z)∈R，必有(x，z)∈R，则称关系R是 。35.例设P{（1，2（3，4（2，）}Q=（47（2，9（3，1}则P·Q= 符号串与符号组成顺序 ，如符号串ab ba，符号申001也 。假设G是一个文法，S是文法的开始符号，如果S=>*x,则称x是 。文法G产生的 该文法描述的语言。39.一个文法G[Z]存在推序列Z=>+·Z·,是 文法，这类文法所产生的句子有 个。40.乔姆斯基把文法分成 类型.四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是 .最右推导常被称为 。由规范推导所得的句型称为 。文法的二义性和语言的二义性是两个 概念。对于上下文无关文法， 是句型推导过程的几何表示。直接短语也称 .每棵语法树的叶子组成一个 .每棵子树的叶子组成一个 .每棵简单子树的叶子组成一个 .最左边简单子树的叶子组成 .一个句型的最左直接短语称为该句型的 。而且推导"=>+"为直接推导"=>"的 。 BNF则是多余的。也称这种非终结符为.不出终结符号串，显然，所有含有U的规则是多余的。也称这种非终结符为 。L∪{εLε}分别是上下文有关语言、和正规语言。GUUSxSUSSU的推导的.文无关文法G包括四个组成部分依次是： , , , .11文法所描述的语言是 集合。词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称 。二、选择编译程序是一种常用的 件。A.应用 B.系统 C.工具 D.测试在使用高级语言编程时，首先可通过编译程序发现源程序的全部 错误和部分 错误。语法B.语义 C.语用D.运行编译程序生成的目标程序 是机器语言的程序。一定 B.不一定C.某种情况下一定D.某种情况下不一定4.编译程序生成的目标程序 是可执行的程序。A.一定 B.不一定 C.某种情况下一定D.某种情况下不一定5.一个语言的文法是 .A．惟一的 B．不惟一的 C.个数有限的D.无限的巴科斯-诺尔范式(即BNF)是一种广泛采用的 的工具。A．描述规则 B.描述语言 C．描述文法 D．描述句子r=(a|b|c)(x|y|z)L（r）中元素为个（）A．9B．6C．18 D．278L={an|n≧0}相应的正则表达式是（）a*B．a+C．aa*D．aa+编译过程中扫描器的任务包括 。①组织源程序的输入②按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出⑧删除注解④删除空格及无用字符⑤行计数、列计数⑥发现并定位词法错误⑦建立符号表A．②③④⑦ B．②③④⑥⑦C．①②③④⑥⑦ D．①②③④⑤⑥⑦10、编译过程中，语法分析器的任务是 。分析单词是怎样构成的c.分析语句和说明是如何构成程序的d.分析程序的结构A.bc Bd C．bcd D．abcd11、语法分析的常用方法是 。a.自顶向下b.自底向上c.自左向右d.自右向左A．abcd B．ab C．cd D．abc12、编译程序中的语法分析器接受以 为单位的输入，并产生有关信息供以后各阶段使用。A．表达式 B．产生式 C．单词 D．语句13、LL(1)文法的条件是 。FIRST(Xi)∩FIRST(Xj)=Φ，(i≠j)FIRST(Xj)∩FOLLOW(U)=ΦC．ABD．都不是14、一个右线性文法G一定是（）A．LL（1）C．SLR（1）文法B．LR（1）D．上述三者都不是15、算符文法是指 的文法。26U->…VW…的规则(U，V，W∈VN)VT中任意两个符号对之间至多有一种优先关系成立⑧没有相同的规则右部U->ε的规则A.① B．①② C．①②③ D．①②③④16、算符优先文法是指 的文法。U->…VW…的规则(U，V，W∈VN)VT中任意两个符号对之间至多有一种优先关系成立⑧没有相同的规则右部U->ε的规则A.①② B．①②③ C.①②③④ D．①②④17、下列文法G[S]的句型aR／aSb／aTb／,b 的最左素短语为 。S->aTb|，T->RR->R／S|SA.aTb B.aSb C.S D.R／18算符优先分析法每次都是对 进行归约简单优先分析法每次都是对句柄进行归约。A．最左短语 B.简单短语 C.最左素短浯 D．素短语19、xab+cde-*f/:=是赋值语句( )相应的后缀式A．x:=a+b+c*d-e/f B．x:=a+(b+c)*d-e/fC．x:+a+b+c*(d-e)/f D．x:=a+b+c+(c*d)-e/f20、LR(K)方法是 。A．从左到右分析，每次走K步的一种编译方法B．从左到右分析，共经过K步的一种编译方法K步的一种编译方法K个输入符号的一种编译方法、下面三个文法中，为SLR(1)文法的是 。10G1：P->PaP|bG3：P->bPb|bPc|d仅Gl G2 C．仅G3 D．G2和G322、有下列文法：11S->Pa|Pb|cP->Pd|Se|f该文法是 。A.LL(1)文法 B.SLR(1)文法C.a和b D.都不是23．代码优化的主要目标是( ①如何提高目标程序的运行速度②如何减少目标程序运行所需的空间③如何协调①和②④如何使生成的目标代码尽可能短A①② B①②③ C①②④ D①②③④24、设文法G（S为其开始符号）产生式如下：S→aSb|ab|ε则G是一个（）A．LR（1）文法B．SLR（1）文法C．三型文法 D．二型文法在编译程序采用的优化方法中， 内进行的。12①合并已知常量 ②删除多余运算，③删除归纳变量 ④强度削弱⑤代码外提A①④ B①⑤ C①④⑤D③④⑤合并表达式中常量运算的目的是 。12①合并常量，使表达式中的常量尽可能少②合并常量，使表达式尽可能简短③将可在编译时刻计算的常量运算在编译时刻计算出来，然后用所计算出来的值替换表达式中出现的所有这种常量运算，使得生成的代码指令尽可能少A① B② C③ D①②③下面的程序段可以进行哪些优化 。12i：=1j：=l0read kL：x：=x*iy：=j*iz：=x*ywriteji：=i+1ifi<100 goto Lhalt①合并已知常量 ②删除多余运算③删除归纳变量 ④强度削弱⑤代码外提可选项有：A．①④ B①⑤C，①④⑤D．③④⑤属于低级语言的是（）B.Pascal C.Lisp DMasmC语言的八进制无符号整规表达式是（A.(oct)8 B.(oct)* C.(oct)+ D.(oct)#采用（）实现三地址代码时，不利于对中间代码进行优化。A.四元式B.间接三元式C.D.有向无循环图一个正规语言只能对应( A一个正规文法；B一个最小有限状态自动机；C.一个下推自动机D.一个确定的有限自动机文法G[A]：A→εA→aBB→AbB→a是( )：A正规文法 B二型文法上下无关文法 D.不确定下面说法正确的是( )：LALR（1）文法LALR（1）文法)：A．必要条件充分必要条件充分条件PL/0语言的目标程序解释执行时用到的数据对象有( )：A目标代码CODEC关键字表WORDDSPL/0语言编译时产生或使用的数据对象不包括( )：A目标代码CODECSWORD37、编译程序是一种常用的 件。A.应用 B.系统 C支撑 D.自动化38、在使用高级语言编程时，首先可通过编译程序发现源程序的全部 错误和部分语义错误。A.语法 B语义 C.语用 D.运行LR（1）LALR（1）文法：A则可能存在移进/归约冲突B则可能存在归约/归约冲突C则可能存在移进/归约冲突和归约/归约冲突D不存在冲突40、运算符与运算对象类型不符"属于 。A.语法错误 B.语义错误 C.语用错误 D.规则三、简答题解释程序定义哪些寄存器?PL／0LIT?LOD?STO?CAL?INT?JMP?JPC?OPR?5S→a|∧|(T)T→T，S|S((a，a)，a)的规范归约过程及每一步的句柄。写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。0开头。编译程序的结构是什么?关系有哪些基本性质？解释字母表,符号,符号串,符号串的长度,符号串联结？自下而上分析算法的基本思想是什么？设有文法G：s::=Qc|cQ::=Rb|bR::=Sa|aBNF范式表示下述文法以消去ε规则：S::=aABb|abA::=Aab|εB::=Aa|a考虑下面程序…………Vara：integer；ProcedureS(X)；Begina：＝a＋1；X：＝a＋XBegina：＝5；S(a)；Print(a)End．试问：若参数传递方式分别采取传名和传值时，程序执行后输出a的值是什么？设有文法G[I]:8判断下面符号串中哪些是该文法的句子.ab0(2)a0c01(3)aaabc10aabc(6)bbca为了正确地对源程序进行编译，不允许文法有二义性，那么怎样才能排除文法的二义性呢?9什么是简单子树？什么是子树？什么是句型的分析？自下而上分析算法的基本思想是什么？设有文法G：s::=Qc|cQ::=Rb|bR::=Sa|a四、综合题Whilea＞0∨b＜0doBeginX：＝X＋1；ifa＞0thena：＝a－1elseb：＝b＋1End；翻译成四元式序列。设布尔表达式的文法为EE(1)∨E(2)E→E(1)∧E(2)E→i改写文法，使之适合进行语法制导翻译和实现回填；写出改写后的短个产生式的语义动作。设文法G(S)：S→(L)|aS|aL→L，S|S消除左递归和回溯；FIRSTFOL