中国科技大学继续教育学院 2009-2010 学年度（第二学期）
《编译原理》试题
姓名_______ 班级__________ 学号__________
题 号 得 分 一 二 三 四
6、编译过程中，比较常见的中间语言有（ ）。 ①波兰表示 ②逆波兰表示 ③三元式 ④四元式 ⑤树形表示 A.①③④ B.②③④ C.③④①⑤ D.②③④⑤
7、一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 （ ）。 A.句子 B.句型 C.单词 D.产生式
8、 一个句型中的最左（ ）称为该句型的句柄。
总 分 一、单项选择题（本大题共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.①②③
A.短语 B.简单短语 C.素短语 D.终结符号
9、词法分析器用于识别（ ）。
A.句子 B.句型 C.单词 D.产生式
10、采用自上而下分析，必须（ ）。 A. 消除左递归 B.消除右递归 C. 消除回溯 D.提取公共左因子
11、用高级语言编写的程序经编译后产生的程序叫（ ）。
A. 源程序 B.目标程序 C.连接程序 D.解释程序
12、文法 G[N]= （ {b} ， {N ， B} ， N ， {N→b│bB ， B→bN} ），该文法所描述的语言是 （ ）
A.L(G[N])={bi│i≥0} B.L(G[N])={b2i│i≥0} C.L(G[N])={b2i+1│i≥0} D.L(G[N])={b2i+1│i≥1}
13、正规式 M 1 和 M 2 等价是指（ ）。
A.M1和M2的状态数相等 B.M1和M2的有向边条数相等 C.M1和M2所识别的语言集相等 D.M1和M2状态数和有向边条数相等
《编译原理》试题A卷 第 1 页 共 5 页
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.L0?L1?L2?L3 B.L3?L2?L1?L0 C.L3=L2?L1?L0 D.L0?L1?L2=L3
19、代码生成阶段的主要任务是（ ） A.把高级语言翻译成汇编语言 B.把高级语言翻译成机器语言
C.把中间代码变换成依赖具体机器的目标代码 D.把汇编语言翻译成机器语言
20、下面三个文法中，为正规文法的是（ ）。 G1：P->PaP|b G2：P->Pb|cP|b|c G3：P->bP|cP|d
A.仅Gl B.G1和G2 C.仅G3 D.G2和G3
题号 答案
11 12 13 14 15 16 17 18 19 20 二、是非题（请在括号内，正确的划√，错误的划×）（每个1分，共10分）
1、计算机高级语言翻译成低级语言只有解释一种方式。 （ ） 2、下推自动机是一个七元组:M=(Q,∑,H,δ,q0,z0,F),其中H表示下推栈内字母表。 （ ） 3、上下文无关文法其产生式为 A->a ,A->Bb, A,B∈VN ,a 、 b∈VT 。 （ ） 4、一个有限状态自动机中,有且仅有一个唯一的终态。 （ ） 5、最左推导的逆过程是最右归约。 （ ） 6、回溯会引起时间和空间的大量消耗。 （ ） 7、两个正规集相等的必要条件是他们对应的正规式等价。 （ ） 8、有限自动机的确定化是用子集法,最小化是用划分法,两者最主要区别是划分法有交集。
（ ）
9、消除回溯可以使用预测和提左因子。 （ ） 10、对每个有限自动机M，只存在一个右线性文法GR与其对应。 （ ）
三、计算题（本大题共4小题，每小题6分，共24分）
1、已知文法G[S] S→AB A→aA∣a B→bB∣b
给出aaabbb的最左推导。
4 5 6 7 8 9 10
请将答案填在表格中
题号 答案 1 2 3 《编译原理》试题A卷 第 2 页 共 5 页
2. 已知文法 G[S] 为： S→dAB A→aA|a B→Bb|ε
G[S] 产生的语言是什么？
3.文法 G[S]: 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
A卷 第 3 页 共 5 页
《编译原理》试题
四.综合题（本大题共2小题，第一题10分，第二题16分，共26分）
1、把下述上下文无关文法等价地变换为无ε产生式的文法： G： (1) E->E' (2) E'->+TE' (3) E'->ε (4) T->PT' (5) T'->ε (6) P->(E) (7) P->i
2、将下面的NFA确定化和最小化： a a3aa X?1?25?6?Y2 bb4bb
《编译原理》试题A卷 第 4 页 共 5 页
《编译原理》试题A卷 第 5 页 共 5 页
编译原理试卷
