编译原理2010级(A)试卷以及参考答案

试卷 课程名称： 编译原理（A） 适用专业年级： 软件工程、计算机 2010 级（闭卷） 考生学号： 考生姓名： ……………………………………………………………………………………………………… 一、单项选择题（20分，每小题2分） 1、_____是两类程序语言处理程序。 A．高级语言程序和低级语言程序 B． 解释程序和编译程序 C．编译程序和操作系统 D．系统程序和应用程序 2、 若文法 G 定义的语言是无限集，则文法必然是 _____。 A．递归的 B． 上下文无关的 C． 二义性的 D． 无二义性的 3、 四种形式语言文法中，3型文法又称为 _____文法。 A． 短语结构文法 B．上下文无关文法 C． 上下文有关文法 D． 正规文法 4、 一个文法所描述的语言是_____。 A． 唯一的 B．不唯一的 C． 可能唯一，也可能不唯一 D．都不对 5、 _____和代码优化部分不是每个编译程序都必需的。 A． 语法分析 B． 中间代码生成 C． 词法分析 D． 目标代码生成 6、文法 G 产生的_____的全体是该文法描述的语言。 A．句型 B． 终结符集 C．非终结符集 D． 句子 7、高级语言编译程序常用的语法分析方法中，LL（1）分析方法属于 。 A.自左至右 B.自顶向下 C.自底向上 D.自右至左 8、一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。

（第 1 页）

A． 句子 B． 句型 C． 单词 D． 产生式 9、一个句型的最左 称为该句型的句柄。 A. 短语 B. 直接短语 C. 素短语 D.终结符号 10、文法：G：S→aSa | b所识别的语言是 。 A. aba B.（aba）* C. a*ba* 二.填空题（20分，每空2分） 1、语法分析是依据语言的 规则进行的。 2、算符优先分析法每次规约当前句型的 。 3、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 。 4、对于文法G，仅含终结符号的句型称为 。 5、逆波兰式ab+c*所对应的表达式为 。 6、编译程序的工作过程一般由 、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段组成。 7．文法G[S]：S->S0 | S1 | a 该文法对应的正规式为 。 8、文法G[E]：E->T | E+T, T->F | T*F, F->(E) | i 该文法的句型 T*F+T的句柄是 。 9、语言L={an bm|n,m≧0}相应的正规表达式是 。 10、规范推导的逆过程是 。 三、判断题.（10分，每小题2分） 1、对任何一个正规语言L，都有一正规表达式r，满足L（r）=L。 2、文法G[S]：S->Sa | Aa, A->Ab |b 是LL(1)文法。 3、解释程序和编译程序一样，生成目标代码。 4、文法中的每个句型都有规范推导。 5、每一个NFA都对应有唯一的一个最小化的DFA。 注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。

（第 2 页）

D. anban（n≥0） 四、解答题（50分） 1、已知文法G(E) （8分） E→T|E＋T T→F|T *F F→(E)|i （1）给出句型 T *F＋i的规范推导（2分） （2）画出上面句型的语法树； （3分） （3）给出句型T *F＋i 的全部短语。(3分) 2、已知文法G：（6分） S->aAd |d A->Bb | ε B->aA | ε 求每个非终结符的FIRST及FOLLOW集。 FIRST FOLLOW S S A A B B (3分) (3分) 3、已知文法G：（6分） S->a | (A) A->A,S| S （1）消除上述文法左递归。（3分） （2）证明改写以后的文法是LL（1）文法。（3分） 4、按要求给出下列语言的文法。（6分） (1) L1={ ab| n，m≥1 } 用右线性正规文法。 （3分） （要求：用2个非终结符S和B描述，S为文法开始符） (2) L2={ an bmcn∣n≥1,m≥0} 用二型文法。 （3分） （要求：用2个非终结符S和B描述，S为文法开始符） 注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。

（第 3 页）

nm 5、已知文法G[Z]： （4分） Z->aAa A->A+b | b 构造文法算符优先关系表 a b + a b + * 6、对于正规式 (10∣0)（10分） （1）请构造与之等价的自动机（4分） （2）将上述自动机确定化（3分） （3）化简（3分） 7、已知文法G[S’] （10分） S’->S S->aA A->Ab A->ε （1）请构造该文法的以LR（0）项目集为状态的识别活前缀的DFA。（5分） （2）判断该文法是否为SLR（1）文法，并说明理由。（2分） （3）构造SLR（1）分析表。（3分） 注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。

（第 4 页）

2010级编译原理试卷（A）参考答案： 4、单项选择题（20分；每小题2分） 1～5：BADAB 6～10：DBDBD 5、填空题（20分；每空2分） 1、语法 2、最左素短语 3、二义性文法 4、句子 5、(a+b)*c 6、词法分析 7、a(0|1)* 8、T*F 9、a* b* 10、规范规约 6、判断题.（10分；每小题2分） 1、 √ 2、 × 3、× 4、× 5、√ 7、解答题（50分） 1、（8分） （1）句型T *F＋i的规范推导：(2分；每错一步推导扣1分，直到扣完) E=> E+T=>E+F=>E+i=>T+i=>T*F+i （2）语法树：（3分；错一条边扣1分, 直到扣完） E E T T * + T F F i （3）短语：（3分，多一个、少一个、错一个均扣1分，直到扣完) T *F＋i T *F i 注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。

（第 5 页）

本文来源：https://www.bwwdw.com/article/r9k2.html