完整版编译原理复习题Word格式文档下载.docx

1、 解释 和 编译 。42、自上而下分析法采用 移进 、归约、错误处理、 接受 等四种操作。43、一个LR分析器包括两部分：一个总控程序和 一张分析表 。44、后缀式abc-/所代表的表达式是 a/（b-c） 。 46、语法分析基于 上下文无关 文法进行，即识别的是该类文法的句子。语法分析的有效工具是 语法树 。48、语义分析阶段所生成的与源程序等价的中间表示形式可以有 逆波兰 、 四元式表示 与 三元式表示 等。51、自顶向下语法分析会遇到的主要问题有 左递归 和 回溯 。52、已知文法GE：ET|E+T；TF|T*F；F（E）|i该文法的开始符号是 E ，终结符号集合VT是 +、*、（、）、

2、i ，非终结符号结合VN是 E、T、F 。二、单选题1、一个编译程序中，不仅包含词法分析，（ A ），中间代码生成，代码优化，目标代码生成等五个部分。A、语法分析 B、文法分析C、语言分析D、解释分析2、语法分析器则可以发现源程序中的（ D ）。A、语义错误 B、语法和语义错误 C、错误并校正 D、语法错误3、解释程序处理语言时 , 大多数采用的是（ B ）方法。A、源程序命令被逐个直接解释执行B、先将源程序转化为中间代码 , 再解释执行C、先将源程序解释转化为目标程序 , 再执行D、以上方法都可以4、编译程序是一种（ B ）。A、汇编程序 B、翻译程序 C、解释程序 D、目标程序5、通常一个

3、编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括（ C ）。A、模拟执行器 B、解释器 C、表格处理和出错处理 D、符号执行器6、一个句型中的最左（ B ）称为该句型的句柄。A、短语 B、简单短语 C、素短语 D、终结符号7、文法 GE ： ETET TFTF Fa（E）该文法句型 EF（ET）的简单短语是下列符号串中的（ B ）。（ET） ET F F（ET）A、 和 B、 和 C、 和 D、8、词法分析器用于识别（ C ）。A、句子 B、句型 C、单词 D、产生式 9、在自底向上的语法分析方法中，分析的关键是（ D ）。A、寻找句柄 B、寻找

4、句型 C、消除递归 D、选择候选式10、文法 G 产生的（ D ）的全体是该文法描述的语言。A、句型 B、终结符集 C、非终结符集 D、句子11、若文法 G 定义的语言是无限集，则文法必然是（ A ）。A、递归的 B、前后文无关的 C、二义性的 D、无二义性的12、四种形式语言文法中，1型文法又称为（ C ）文法。A、短语结构文法 B、前后文无关文法 C、前后文有关文法 D、正规文法13、一个文法所描述的语言是（ A ）。A、唯一的 B、不唯一的 C、可能唯一，好可能不唯一 D、都不对14、（ B ）和代码优化部分不是每个编译程序都必需的。A、语法分析 B、中间代码生成 C、词法分析 D、目标

5、代码生成15、（ B ）是两类程序语言处理程序。A、高级语言程序和低级语言程序 B、解释程序和编译程序C、编译程序和操作系统 D、系统程序和应用程序16、一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组（ D ）。A、句子 B、句型 C、单词 D、产生式17、文法分为四种类型，即0型、1型、2型、3型。其中2型文法是（ D ）。A、短语文法 B、正则文法 C、上下文有关文法 D、上下文无关文法18、文法 G 所描述的语言是（ C ）的集合。A、文法G的字母表V中所有符号组成的符号串B、文法G的字母表V的闭包V*中的所有符号串C、由文法的开始符号

6、推出的所有终结符串D、由文法的开始符号推出的所有符号串19、文法分为四种类型，即0型、1型、2型、3型。其中0型文法是（ A ）。20、（ A ）是一种典型的解释型语言。A、BASIC B、C C、FORTRAN D、PASCAL21、与编译系统相比，解释系统（ D ）。A、比较简单，可移植性好，执行速度快B、比较复杂，可移植性好，执行速度快C、比较简单，可移植性差，执行速度慢D、比较简单，可移植性好，执行速度慢22、用高级语言编写的程序经编译后产生的程序叫（ B ）。A、源程序 B、目标程序 C、连接程序 D、解释程序23、编写一个计算机高级语言的源程序后，到正式上机运行之前，一般要经过（

7、B ）这几步:（1）编辑 （2）编译 （3）连接 （4）运行A、（1）（2）（3）（4） B、（1）（2）（3） C、（1）（3） D、（1）（4）24、把汇编语言程序翻译成机器可执行的目标程序的工作是由（ B ）完成的。A、编译器 B、汇编器 C、解释器 D、预处理器25、词法分析器的输出结果是（ C ）。A、单词的种别编码 B、单词在符号表中的位置C、单词的种别编码和自身值 D、单词自身值26、正规式M1和M2等价是指（ C ）。A、M1和M2的状态数相等 B、M1和M2的有向边条数相等C、M1和M2所识别的语言集相等 D、M1和M2状态数和有向边条数相等27、文法G：SxSx|y所识别的

8、语言是（ C ）。A、xyx B、（xyx）* C、xnyxn（n0） D、x*yx*28、如果文法G是无二义的，则它的任何句子（ A ）。A、最左推导和最右推导对应的语法树必定相同B、最左推导和最右推导对应的语法树可能不同C、最左推导和最右推导必定相同D、可能存在两个不同的最左推导，但它们对应的语法树相同29、构造编译程序应掌握（ D ）。A、源程序 B、目标语言 C、编译方法 D、以上三项都是30四元式之间的联系是通过（ B ）实现的。A、指示器 B、临时变量 C、符号表 D、程序变量31、表达式（AB）（CD）的逆波兰表示为（ B ）。A、ABCD B、ABCDC、ABCD D、ABCD

9、33、编译程序是对（ D ）。A、汇编程序的翻译 B、高级语言程序的解释执行C、机器语言的执行 D、高级语言的翻译34、采用自上而下分析，必须（ C ）。A、消除左递归 B、消除右递归 C、消除回溯 D、提取公共左因子35、在规范归约中，用（ B ）来刻画可归约串。A、直接短语 B、句柄 C、最左素短语 D、素短语36、间接三元式表示法的优点为（ A ）。A、采用间接码表，便于优化处理 B、节省存储空间，不便于表的修改C、便于优化处理，节省存储空间 D、节省存储空间，不便于优化处理37、在目标代码生成阶段，符号表用（ D ）。A、目标代码生成 B、语义检查 C、语法检查 D、地址分配38、下面

10、关于解释程序的描述正确的是（ B ）。（1） 解释程序的特点是处理程序时不产生目标代码（2） 解释程序适用于COBOL 和 FORTRAN 语言（3） 解释程序是为打开编译程序技术的僵局而开发的A、（1）（2） B、（1） C、（1）（2）（3） D、（2）（3）39、解释程序处理语言时，大多数采用的是（ B ）方法。B、先将源程序转化为中间代码，再解释执行C、先将源程序解释转化为目标程序，在执行40、用不同语言编写的程序产生（）后，可用（）连接在一起生成机器可执行的程序.在机器中真正执行的是（）。上面三空格对应的选项是（ A ）a、源程序 b、目标程序 c、函数 d、过程e、机器指令代码 f

11、、模块 g、连接程序 h、程序库A、b、g、e B、b、c、e C、e、g、f D、e、c、f41、由于受到具体机器主存容量的限制，编译程序几个不同阶段的工作往往被组合成 （），诸阶段的工作往往是（）进行的. 上面两空格对应的选项是（ A ）a、过程 b、程序 c、批量 d、遍e、顺序 f、并行 g、成批 h、穿插A、d和h B、d和e C、a和h D、a和e42、编译过程中，语法分析器的任务就是（ B ）（1）分析单词是怎样构成的（2）分析单词串是如何构成语句和说明的（3）分析语句和说明是如何构成程序的（4）分析程序的结构A、（2）（3） B、（2）（3）（4） C、（1）（2）（3） D、

12、（1）（2）（3）（4）43、编译程序必须完成的工作有（ A ）（1）词法分析 （2）语法分析 （3）语义分析（4）代码生成 （5）中间代码生成 （6）代码优化A、（1）（2）（3）（4） B、（1）（2）（3）（4）（5）C、（1）（2）（3）（4）（5）（6） D、（1）（2）（3）（4）（6）44、按逻辑上划分，编译程序第二步工作是（ C ）。A、语义分析 B、词法分析 C、语法分析 D、代码优化45、已知语言L= xnyyn | n=1，则下述文法中，（ D ）可以产生语言L。A 1、ZxZy|xAy|y B 1、AxAy 2、AxAy|x 2、AxC 1、ZAyB D 1、ZxAy

13、2、AxA|x 2、AxAy|y 3、ByB|y46、乔姆斯基（Chomsky）把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是（ B ）。A、短语文法 B、正则文法 C、上下文有关文法 D、上下文无关文法48、设G是一个给定的文法，S是文法的开始符号，如果S x（其中xV*），则称x是文法G的一个（ B ）。A、候选式 B、句型 C、单词 D、产生式49、若一个文法是递归的，则它所产生的语言的句子（ A ）。A、是无穷多个 B、是有穷多个 C、是可枚举的 D、个数是常量50、文法的二义性和语言的二义性是两个（ A ）的概念。A、不同 B、相同 C、无法判断 D、不存在51、在语法

14、分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是（ B ）。A、非终结符集 B、终结符集 C、字母表 D、状态集52、编译程序中语法分析器接收以（ A ）为单位的输入。A、单词 B、表达式 C、产生式 D、句子53、在LR分析法中，分析栈中存放的状态是识别规范句型（ C ）的DFA状态。A、句柄 B、前缀 C、活前缀 D、LR（0）项目三、是非题（下列各题，你认为正确的，请在题干的括号内打“”，错的打“”。）（）1、计算机高级语言翻译成低级语言只有解释一种方式。）2、在编译中进行语法检查的目的是为了发现程序中所有错误。）3、甲机上的某编译程序在乙机上能直接使用的必要条件是甲机

15、和乙机的操作系统功能完全相同。）4、“用高级语言书写的源程序都必须通过编译，产生目标代码后才能投入运行”这种说法。（）5、正则文法其产生式为A?a，A?Bb，A，BVN，a、bVT。）6、产生式是用于定义词法成分的一种书写规则。）7、解释程序适用于COBOL和FORTRAN语言。（）8、正规文法产生的语言都可以用上下文无关文法来描述。（）9、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。）10、编译程序是对高级语言程序的解释执行。）11、一个有限状态自动机中，有且仅有一个唯一的终态。）12、语法分析时必须先消除文法中的左递归。（）13、两个正规集相等的必要条件是他们对应的

16、正规式等价。）14、设r和s分别是正规式，则有L（r|s）=L（r）L（s）。（）15、确定的自动机以及不确定的自动机都能正确地识别正规集。）16、词法分析作为单独的一遍来处理较好。（）17、构造LR分析器的任务就是产生LR分析表。）18、编译程序与具体的机器有关，与具体的语言无关。）19、每个文法都能改写为LL（1）文法。（）20、递归下降法允许任一非终结符是直接左递归的。（）21、递归下降分析法是自顶向下分析方法。（）22、一个 LL（l）文法一定是无二义的。）23、算符优先关系表不一定存在对应的优先函数。）24、自底而上语法分析方法的主要问题是候选式的选择。）25、LR分析方法是自顶向下

17、语法分析方法。）26、简单优先文法允许任意两个产生式具有相同右部。）27、若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。（）28、一个句型的句柄一定是文法某产生式的右部。（）29、在 SLR（1）分析法的名称中，S的含义是简单的。）30、综合属性是用于 “ 自上而下 ” 传递信息。（）31、一个算符优先文法可能不存在算符优先函数与之对应。（）32、LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。（）33、规范归约和规范推导是互逆的两个过程。）34、LR分析技术无法适用二义文法。（）35、逆波兰表示法表示表达式时无须使用括号。（）36、逆波兰法表示的表达式

18、亦称后缀式。）38、在程序中标识符的出现仅为使用性的。）39、设为a，b，则a，ba，都是上的正规式。）40、对于上下文无关文法GS，若 SAB则A 一定是一条产生式规则，其中,（VTVN）*。（）41、对于逆波兰后缀式，无论从哪头开始分析均可得到唯一正确的分解。（）42、LR（0）分析法是一种规范归约法。（）43、算符优先分析法只能用来分析算符优先文法。）44、解释程序和编译程序一样，生成目标代码。）45、编译程序生成的目标代码只能是机器语言。）46、等价文法是指两个文法完全相同。（）47、对于字母表上的任一NFA M，必存在上与NFA M 等价的DFA M。）48、每个文法都能改写为LL（

19、1）文法。（）49、不存在正规文法能产生语言：L=anbn|n=1四、简答题1、什么是句子 什么是语言设G是一个给定的文法，S是文法的开始符号，如果Sx（其中xVT*）,则称x是文法的一个句子。设GS是给定文法，则由文法G所定义的语言L（G）可描述为：L（G）xSx，xVT*。2、已知文法GE为：ET|E+T|E-TTF|T*F|T/FF（E）|i 该文法的开始符号（识别符号）是什么 请给出该文法的终结符号集合VT和非终结符号集合VN。 找出句型T+T*F+i的所有短语、简单短语和句柄。 该文法的开始符号（识别符号）是E。 该文法的终结符号集合VT=+、-、*、/、（、）、i。非终结符号集合V

20、N=E、T、F。 句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i；简单短语为i、T*F、第一个T；句柄为第一个T。3、已知文法GS为：SdABAaA|aBBb| GS产生的语言是什么 GS能否改写为等价的正规文法 GS产生的语言是L（GS）=danbmn1，m0。 GS能改写为等价的正规文法，其改写后的等价的正规文法GS为：SdAA aA|aB|aB bB|b5、证明下面文法GN是二义性文法。GN：N SEE S SDD E 0210D 01210是文法GN的一个句子，并且有两个不同的最右推导。（1）S=E=10（2）S=SE=S0=D0=因此说明此文法有二义性。7、简述DFA

21、与NFA有何区别 DFA与NFA的区别表现为两个方面:一是NFA可以若干个开始状态，而DFA仅只一个开始状态。另一方面，DFA的映象M是从K到K，而NFA的映象M是从K到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。8、试给出非确定自动机的定义。一个非确定的有穷自动机（NFA）M是一个五元组：M=（K，f，S，Z）。其中:1、K是一个有穷集，它的每个元素称为一个状态。2、是一个有穷字母表，它的每个元素称为一个输入符号。3、f是一个从K*到K的全体子集的映像，即K*2K，其中2K表示K的幂集。4、S?K，是一个非空初态集。5、Z?K，是一个终态集。9、为正规式（a|b）*a

22、（a|b） 构造一个等价的确定的有限自动机。10、构造正规式相应的NFA：1（0|1）*101 12、已知文法 GS 为： SdAB AaA|a BBb| GS 产生的语言是什么 GS产生的语言是L（GS）=danbmn1，m0。13、编译过程一般分为几个阶段各阶段的输入输出分别为什么15、在LL（1）分析法中，LL分别代表什么含义第一个L代表从左到右的扫描，第二个L代表每次进行最左推导。16、文法G为： SaAB Aa B|则判断G为LL（1）文法的条件是：（1）文法G不含左递归（2）对于每个非终结符，First（）、First（）、First（）两两不相交。（3）对于每个非终结符，不含能推

23、出的产生式，故不考虑非终结符的First集和Follow集相交的情况。17、文法G=（A, B, S, a, b, c, P, S），其中P为：SAc|aBAabBbc该文法是二义的吗说明理由。18、文法G=（E，+，*，i，（，），P，E），其中P为：EiEE+EEE*EE（E）19、自顶向下分析思想是什么从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。25、简单优先方法基本思想是什么简单优先方法基本思想是首先规定文法符号之间的优先关系和结合性质，然后再利用这种关系，通过比较两个相邻的符

24、号之间的优先顺序来确定句型的“句柄”并进行归约。28、语法制导翻译方法的基本思想是什么在语法分析过程中，每当使用一条产生式进行推导或归约时，就执行该产生式所对应的语义动作进行属性计算，完成对输入符号串的翻译。33、给定下列中缀式，分别写出等价的后缀式和四元式（运算符优先级按常规理解）。（1）（ab*c）/（ab）d后缀式：abc*+ab+/d-四元式：（*，b，c，t1） （+，a，t1，t2） （+，a，b，t3） （/，t2，t3，t4） （-，t4，d，t5）一、最左、最右推导及语法树1、令文法为 ET|E+T|E-T TF|T*F|T/F F（E）|i（1）给出i+i*i的最左推导和最右推导；（2）给出i+i*i的最左推导语法树。2、已知文法G： :=|+*=（）|i3、下面的文法生成的是以x和y为操作数、二元运算符+、*和-为运算符的前缀表达式：E+EE|*EE|-EE|x|y（1）给出串+*-xyxy的最左推导和最右推导；（2）给出+*-x