模拟题-编译原理

、选择（）是两类程序语言处理程序.BA.高级语言程序和低级语言程序B.解释程序和编译程序C.编译程序和操作系统D.系统程序和应用程序.编译程序前三个阶段完成的工作是（C）词法分析、语法分析和代码优化代码生成、代码优化和词法分析词法分析、语法分析、语义分析和中间代码生成A..词法分析、语法分析和代码优化代码优化的目的是（）C..CA.节省时间B.节省空间C.节省时间和空间，把编译程序进行等价交换代码优化的目的是（节省时间和空间）描述一个语言的文法是（）

3.CA.唯一的B.不唯一的C.可能唯一，也可能不唯一D.都不对.下推自动机识别的语言是（C）型语言型语言型语言型语言如果文法是无二义的，则它的任何句子（）A.0B.1C.2D.

3.G A最左推导和最右推导对应的语法树必定相同最左推导和最右推导对应的语法树可能不同A.B.最左推导和最右推导必定相同.可能存在两个不同的最左推导，但它们对应的语法树相同C.D

7.LR

（0）分析法中，语法分析栈中存放的状态是识别规范句型（B）的DFA状态A前缀活前缀.LR

（0）项目句柄B8若文法定义的语言是无限集，则文法必然是（）.G A.递归的前后文无关的二义性的无二义性的［分析］本题考查语言文法的特点A.B.C.D.所谓文法就是语法规则，是描述语言的语法结构的形式规则如果一个文法定义的语言是无限集，那么此文法必然是递归的

9.扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即（）B字符单词句子句型.算符文法是指（A）的文法A.B.C.D.

①没有形如的规则（U,V,WIVN）

②叮中任意两个符号之间至多存在一种算符优先关系

③没有相同右部的规则

④没有形如U-£的规则A

①①和

②.

①、

②和

③①、

②、

③和

④B

11.一般程序设计语言的定义都涉及（B）三个方面

①语法

②语义

③语用

④程序基本符号的确定.A.

①、

②和

③B.

①、

②和

④C.

①、

③和

④D.

②、

③和

④［解析］一般情况下，程序设计语言的定义都涉及语法、语义、语用等个方面

①语法是指由程序语言3基本符号组成程序中的各个语法成分（包括程序）的一组规则，不涉及语法成分的特定含义，也不涉及使用者

②语义是程序语言中按语法规则构成的各个语法成分的含义，但不涉及使用者

③语用表示了构成语言的各个记号和使用者的关系试卷给出的答案是.生成能被5整除的正整数的文法G［Z］是（C）BA.GZ Z-AC,A-BA|B,B-O|l⑵…|9,C-0A-*BA|e,B-*0|l|2|-|9,C-0A-BA|B,B^0|l|2|-|9,C-*0A-*BA|B,BfO1|2|…|9,C-*O.程序的基本块是指（D）B.GZ Z-AC,C.GZ Z-AC|5,D.GZ Z-*AC|C,A.不含无条件转移语句的程序段B.不含条件转移语句的程序段C.不含停机的语句程序段D.仅含有一个入口语句和一个出口语句的顺序程序文法分为四种类型，即型、型、型、型其中型文

14.01233法是（）B o短语文法正则文法上下文有关文法上下文无关文法乔姆斯基把方法分成四种类型，即型、型、型和型，源A.B.C.D.123于《编译原理》，但《软件设计师》教程对于该分类的介绍很简略，也很抽象，根据网上各类博客对其的解释和教程的说法，大致总结如下首先要阐明的是，一般的文法至少都是型文法，也就是说型文法限制最少，二型文法都是在1,2,3型文法基础上加以限制形成0若将型文法比作基类的话，就是不断继承并加以限制得到的子类0123,4

①0型文法设G=（VN,VT,P,S）,如果它的每个产生式a是这样一种结构a£（VNUVT）*且至少含有一个非终结符，而8£（VNUVT）*,则G是一个0型文法型文法也称短语文法0型文法的能力相当于图灵机（Turing）我们发现型文法是限制最少的一种文法，平时见到的文法几乎都属于型文法00

②型文法型文法也叫上下文有关文法，此文法对应于线性有界自动机它是在型文法的基础上每一个-曳都有|110a p|=|这里的|表示的是的长度aI|B B注意虽然要求但有一特例一£也满足型文法|B|=|a|,a1如有则|符合型文法要求反之，如则不符合型文法A-Ba B|=2,|a|=11aA-a,1

③型文法型文法也叫上下文无关文法，它对应于下推自动机型文法是在型文法的基础上，再满足每一个都有2221a a是非终结符如符合型文法要求A-Ba,2如虽然符合型文法要求，但不符合型文法要求，因为其而不是一个非终结符Ab-Bab12a=Ab,Ab

④型文法型文法也叫正规文法，它对应于有限状态自动机它是在型文法的基础上满足:（右线性）或（左332A-a|aB A-a|Ba线性）如有则符合型文法的要求但如果推导为或推导为:则不符合型方法的要A-a,A-aB,B-a,B-cB,3:A-ab,A-aB,B-a,B-cB3求了具体的说，例子中的不符合型文法的定义，如果把后面的改成“一个非终结符+一A-ab A-aB,B-a,B-cB A-ab3ab,z个终结符”的形式（即为aB）就对了例子A-a,A-Ba,B-a,B-cB中如果把B-cB改为B-Bc的形式就对了，因为A-a|aB（右线性）和（左线性）两套规则不能同时出现在一个语法中，只能完全满足其中的一个，才能算型文法A-a|Ba3那么这四类文法如何判断呢？其实四种文法就是规定产生式的左和右边的字符的组成规则不同而已，于是我们便可以严格根据左边和右边规则的不同来加以判断首先，应该明确，四种文法，从型到型，其规则和约定越来越多，限制条件也越来越多，所以我们应该按照33-2-1-0的顺序去判断，一旦满足前面的规则，就不用去判断后面的了.先来看看型文法的判断规则

①左边必须只有一个字符，且必须是非终结符；13

②其右边最多只能有两个字符，要么是一个非终结符+终结符（终结符+非终结符），要么是一个终结符

③对于型文法中的所有产生式，若其右边有两个字符的产生式，这些产生式右边两个字符中终结符和非终结符的相对3位置一定要固定，也就是说如果一个产生式右边的两个字符的排列是终结符+非终结符，那么所有产生式右边只要有两个字符的，都必须满足终结符+非终结符反之亦然.再看看型文法判断规则

①与型文法的第一点相同，即左边必须有且仅有一个非终结符223

②型文法所有产生式的右边可以含有若干个终结符和非终结符（只要是有限的就行，没有个数限制）

2.最后再看看型文法判断规则

①型文法所有产生式左边可以含有一个、两个或两个以上的字符，但其中必须至少有311一个非终结符

②与型文法第二点相同，但需要满足2|a|W|B|.型文法不需要判断了，一般的文法都是型文法（）中间代码生成时所依据的是（）o oo n_n o.C语法规则.词法规则语义规则等价变换规则16A.B C.D..A.B

1.6符号串ablb2是给定文法G[A]A-aB,B-bB|b的句子，该句子的句柄是（B）bl b

2.常用的中间.代码形式不含（）C.DA.cB.blb2C.三元式四元式逆波兰式语法树解释程序处理语言时，大多数采用的是（）方法A.B.C.D..A源程序命令被逐个直接解释执行先将源程序转化为中间代码，再解释执行先将源程序解释转化为目标程序,再执行A.B.C.D.以上方法都可以下列—优化方法不是针对循环优化进行的

17.C—强度削弱删除归纳变量删除多余运算.代码外提在编译程序采用的优化方法中，是在循环语句范围内进行的A.B.C.D D

①合并已知常量

②删除多余运算

③删除归纳变量

④强度削弱

⑤代码外提

①④①⑤①④⑤③④⑤一个文法所描述的语言是（）A.B.C.D..A唯一的不唯一的可能唯一，也可能不唯一都不对

二、判断A.B.C.D.

1.削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性V.静态数组的存储空间可以在编译时确定（X）正则文法其产生式为、

2.A-a,A-Bb,A,BeVN,a beVT.X

3.构造LR分析器的任务就是产生LR分析表VOOOOOOOOOOOOOO.设r和s分别是正规式，则有L（r|s）=L（r）L（s）oX进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用若一个句型中出现了某产生式

4.X.的右部，则此右部一定是该句型的句柄X在编译中进行语法检查的目的是为了发现程序中所有错误甲机上的某编译程序在乙机上能直接使用的必要条件是甲

5.X.机和乙机的操作系统功能完全相同J自底而上语法分析方法的主要问题是候选式的选择“用高级语言书写的源程序都必须通过编译，产生目标代码后才

6.X能投入运行”这种说法（X）2型文法一定是3型文法（X）3型文法一定是2型文法（LR法是自顶向下语法分析方法（X）LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点（J）LR分析技术无法适用二义文法（X）LR分析器的任务就是产生LR分析表（J）LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点（J）编译程序是对高级语言程序的解释执行（X）编译程序与具体的机器有关，与具体的语言无关（X）编译过程中，语法分析器的任务是分析单词是怎样构成的（X）并不是每个文法都能改写成LL⑴文法（J）采用三元式实现三地址代码时，不利于对中间代码进行优化（J）产生式是用于定义词法成分的一种书写规则（X）程序语言的语言处理程序是一种应用软件（X）递归下降法不允许任一非终极符是直接左递归的（J）递归下降分析法是一种自下而上分析法（X）递归下降分析法是自顶向下分析方法（J）对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略（X）分析作为单独的一遍来处理较好（X）符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等（X）归约和规范推导是互逆的两个过程（J）计算机高级语言翻译成低级语言只有解释一种方式（X）甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同（J）简单优先文法允许任意两个产生式具有相同右部（X）仅考虑一个基本块，不能确定一个赋值是否真是无用的（V）进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用（X）静态数组的存储空间可以在编译时确定（X）两个正规集相等的必要条件是他们对应的正规式等价（X）每个过程的活动记录的体积在编译时可静态确定（J）每个基本块可用一个DAG表示（V）每个基本块只有一个入口和一个出口（J）每个文法都能改写为LL⑴文法（J）目标代码生成时，应考虑如何充分利用计算机的寄存器的问题（J）逆波兰表示法表示表达式时无须使用括号（J）逆波兰表示法表示表达式时无须使用括号（J）逆波兰法表示的表达式亦称后缀式（J）逆波兰法表示的表达试亦称前缀式（J）确定的的自动机以及不确定的自动机都能正确地识别正集（J）如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的（J）如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的（J）若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄（）树形表示和四元式不便于优化，而三元式和间接三元式则便于优化X（）数组元素的地址计算与数组的存储方式有关（）数组元素的地址计算与数组的存储方式有关（）X XX算符优先分析法每次都是对句柄进行归约（X）算符优先关系表不一定存在对应的优先函数（X）同心集的合并有可能产生新的“移进”/“归约”冲突（X）削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性（J）序中的表达式语句在语义翻译时不需要回填技术（J）一个LL（I）文法一定是无二义的（J）一个句型的句柄一定是文法某产生式的右部（J）一个句型的直接短语是唯一的（X）一个上下文无关文法的开始符，可以是终结符或非终结符（X）一个算符优先文法可能不存在算符优先函数与之对应（J）一个优先表一定存在相应的优先函数（X）一个有限状态自动机中，有且仅有一个唯一的终态（X）一个语义子程序描述了一个文法所对应的翻译工作（X）一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态（J）目标代码生成时，应考虑如何充分利用计算机的寄存器的问题（X）已经证明文法的二义性是可判定的.（X）语法分析时必须先消除文法中的左递归（X）在编译中进行语法检查的目的是为了发现程序中所有错误（X）在程序中标识符的出现仅为使用性的（X）在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度（X）日底而上语法分析方法的主要问题是候选式的选择（）X综合属性是用于“自上而下”传递信息（）X。