编译原理试卷.doc

中国科技大学继续教育学院 2009-2010 学年度（第二学期）编译原理试题姓名_ 班级_ 学号_ 题 号一二三四总 分得 分一、单项选择题（本大题共20小题，每小题2分，共40分）1、语法分析器则可以发现源程序中的（ ）。A.语义错误 B.语法和语义错误C.错误并校正 D.语法错误2、一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。A.唯一的 B.不唯一的 C.可能唯一,可能不唯一A.唯一的 B.不唯一的 C.可能唯一,可能不唯一3、（ ）和代码优化部分不是每个编译程序都必需的。A.语法分析B.中间代码生成 C.词法分析 D.目标代码生成 4 文法分为四种类型，即0型、1型、2型、3型。其中2型文法是（ ）。A.短语文法 B.正则文法 C.上下文有关文法D.上下文无关文法5、语法分析的常用方法是（ ）。自顶向下 自底向上 自左向右 自右向左 A. B. C. D.6、编译过程中，比较常见的中间语言有（ ）。波兰表示 逆波兰表示 三元式 四元式 树形表示A. B. C. D.7、一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 （ ）。 A.句子 B.句型C.单词 D.产生式8、 一个句型中的最左（ ）称为该句型的句柄。A.短语 B.简单短语 C.素短语 D.终结符号 9、词法分析器用于识别（ ）。A.句子 B.句型 C.单词 D.产生式 10、采用自上而下分析，必须（ ）。A. 消除左递归 B.消除右递归C. 消除回溯 D.提取公共左因子 11、用高级语言编写的程序经编译后产生的程序叫（ ）。 A. 源程序B.目标程序C.连接程序 D.解释程序12、文法 GN= （ b ， N ， B ， N ， NbbB ， BbN ），该文法所描述的语言是（ ） A.L(GN)=bii0 B.L(GN)=b2ii0C.L(GN)=b2i+1i0 D.L(GN)=b2i+1i113、正规式 M 1 和 M 2 等价是指（ ）。 A.M1和M2的状态数相等 B.M1和M2的有向边条数相等C.M1和M2所识别的语言集相等 D.M1和M2状态数和有向边条数相等14、一个编译程序中，不仅包含词法分析，（ ），中间代码生成，代码优化，目标代码生成等五个部分。A.语法分析 B.文法分析C.语言分析D.解释分析15、进行优化时所依据的是（ ）。 A.语法规则 B.词法规则 C.语义规则 D.等价变换规则16、文法 G 产生的（ ）的全体是该文法描述的语言。 A.终结符串 B.终结符集 C.非终结符集 D.句型17、下推自动机识别的语言是（ ）A.0型语言 B.1型语言 C.2型语言 D.3型语言18、对应Chomsky四种文法的四种语言之间的关系是（ ） A.L0L1L2L3 B.L3L2L1L0 C.L3=L2L1L0 D.L0L1L2=L319、代码生成阶段的主要任务是（ ） A.把高级语言翻译成汇编语言 B.把高级语言翻译成机器语言 C.把中间代码变换成依赖具体机器的目标代码 D.把汇编语言翻译成机器语言20、下面三个文法中，为正规文法的是（ ）。G1：P-PaP|bG2：P-Pb|cP|b|cG3：P-bP|cP|dA.仅Gl B.G1和G2 C.仅G3 D.G2和G3 请将答案填在表格中题号12345678910答案题号11121314151617181920答案二、是非题（请在括号内，正确的划，错误的划）（每个1分，共10分）1、计算机高级语言翻译成低级语言只有解释一种方式。 （ ）2、下推自动机是一个七元组:M=(Q,H,q0,z0,F),其中H表示下推栈内字母表。 （ ）3、上下文无关文法其产生式为 A-a ,A-Bb,A,BVN ,a 、 bVT 。 （ ）4、一个有限状态自动机中,有且仅有一个唯一的终态。 （ ）5、最左推导的逆过程是最右归约。 （ ）6、回溯会引起时间和空间的大量消耗。 （ ）7、两个正规集相等的必要条件是他们对应的正规式等价。 （ ）8、有限自动机的确定化是用子集法,最小化是用划分法,两者最主要区别是划分法有交集。（ ）9、消除回溯可以使用预测和提左因子。 （ ）10、对每个有限自动机M，只存在一个右线性文法GR与其对应。 （ ）三、计算题（本大题共4小题，每小题6分，共24分）1、已知文法GSSABAaAaBbBb给出aaabbb的最左推导。2. 已知文法 GS 为： SdAB AaA|a BBb| GS 产生的语言是什么？3.文法 GS: S (T) | a+S | a T T,S | S 消除文法的左递归。4、化简下面文法，其中S为开始符号(1) S-E+T (2) E-S+F|T(3) F-F|FP(4) P-G(5) G-G|GG|F(6) T-T*i|i(7) Q-E|E+F(8) S-i四.综合题（本大题共2小题，第一题10分，第二题16分，共26分）1、把下述上下文无关