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

试卷 课程名称： 编译原理（A） 适用专业年级： 软件工程、计算机 2010 级（闭卷） 考生学号： 考生姓名： ……………………………………………………………………………………………………… 一、单项选择题（20分，每小题2分） 1、_____是两类程序语言处理程序。 　A．高级语言程序和低级语言程序 ??????? 　　B． 解释程序和编译程序 　C．编译程序和操作系统 ??????????????? 　　D．系统程序和应用程序 2 若文法 G 定义的语言是无限集，则文法必然是 _____。? 　A．递归的 ? 　 　B． 文无关的　? C． 二义性的 　　 D． 无二义性的 3 四种形式语言文法中，型文法又称为 _____文法。 　A． 短语结构文法 ????? B．文无关文法 　　C．文有关文法 ??? D． 正规文法 4 一个文法所描述的语言是_____。 　A． 唯一的 　 ? 　　 ? 　 ? 　　 ? B．不唯一的 　??C． 可能唯一，可能不唯一 ? 　　D．都不对 5 _____和代码优化部分不是每个编译程序都必需的。 　A． 语法分析???　　　B． 中间代码生成 ??? ??C． 词法分析 ?????　 D． 目标代码生成 6文法 G 产生的_____的全体是该文法描述的语言。 　A．句型 　　 B． 终结符集 　　C．非终结符集 　　D． 句子 A.自左至右 B.自顶向下 C.自底向上 D.自右至左 8、一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 　A． 句子 　 　B． 句型　C． 单词 　　　 D． 产生式 90分，每空2分） 1、语法分析是依据语言的 规则进行的。 2、算符优先分析法每次规约当前句型的 。 3、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 。 4、对于文法G，仅含终结符号的句型称为 。 5、逆波兰式ab+c*所对应的表达式为 。 6、编译程序的工作过程一般由 、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段组成。 7． 。 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分，每小题2分） 1、对任何一个正L，都有正表达式r，满足L（r）=LLL(1)文法。 3、解释程序和编译程序一样，生成目标代码。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集。 FOLLOW S A B FIRST S A B (3分) (3分) 已知文法G：（6分） S-a | (A) A-A,S| S 消除上述文法左递归。（3分） 证明改写以后的文法是LL（1）文法。（3分） 4、按给出下列语言的文法。　　(1) L1={ abm| n，m≥1 } 用正规文法。 （要求：用2个非终结符S和B描述，S为文法开始符）　　(2) L2={ an bmn≥1,m≥0} 用二型文法。’] （10分） S’-S S-aA A-Ab A-ε （1）请构造该文法的以LR（0）项目集为状态的识别活前缀的DFA。（5分） （2）判断该文法是否为SLR（1）文法，并说明理由。（2分） （3）构造SLR（1）分析表。（3分） 2010级编译原理试卷（A）参考答案： 单项选择分.（10分；每小题2分） √ 2、 × 3、× 4、× 5、√ 解答题（50分） 1、（8分） （1）句型T *F＋i的规范推导：(2分；每错一步推导扣1分，直到扣完) E= E+T=E+F=E