南昌航空大学2012—2013学年第一学期期末考试
课程名称： 编译原理 闭卷 B卷 120 分钟
题号 满分 实得分 一 20 二 20 三 30 四 30 合计 100 姓名----------------- 重修标记 评阅人 得分 一、 单向选择题（在每小题列出的四个备选项中只有一个是
符合题目要求的,请将其代码填写在题目前的表格中。错
选、多选或未选均无分。每小题 2 分，共 20 分) 1 2 1．表达式a*(-b+c)的逆波兰表示为 A、a*-b+c
B、ab*-c+
C、a*b-c+ D、ab-c+*
3 4 5 6 7 8 9 10 2．若a为终结符，则 A→?.a? 为 A、移进项目
B、归约项目 C、接受项目 D、待约项目
班级------------------- 学号-------------- 3．_____和代码优化部分不是每个编译程序都必需的。
A、 语法分析 B、中间代码生成 C、 词法分析 D、 目标代码生成 4．在语法制导翻译中不采用拉链回填技术的语句是
A、跳转语句 B、赋值语句 C、条件语句 D、循环语句 5. 词法分析器用于识别_____。
A、字符串 B、语句 C、单词 D、标识符
6．已知文法G是无二义的，则对G的任意句型α：
A、最左推导和最右推导对应的语法树必定相同 B、最左推导和最右推导对应的语法树可能相同 C、最左推导和最右推导必定相同
D、可能存在两个不同的最左推导，但他们对应的语法树相同
命题教师（签字） 试做教师（签字） 系、室主任（签字） 第 1 页 共 8 页
7. 正规式 M 1 和 M 2 等价是指_____。
A、M1和M2的状态数相等 B、M1和M2的有向边条数相等 C、 M1和M2所识别的语言集相等 D、M1和M2状态数和有向边条数相等 8. 在规范归约中，用_____来刻画可归约串。
A、直接短语 B、句柄 C、最左素短语 D、素短语 9．一个文法所描述的语言是 A、唯一的 B、不唯一的 C、个数有限的 D、不能确定 10. 下列文法产生式不可能是算符文法的是： A、S->AB B、S->aAB C、S->AAB D、 S->a
评阅人 得分 二、填空题（共 20 分）
1、对于文法G，仅含终结符号的句型称为_____________。(2分)
1、 已知文法G(S)为：S->aA A->aA|B|? B->bB|b 该文法的开始符号是______________,
终结符号集合是_____________,非终结符号集合是_______________。（3分）
2、 一般来说，编译程序分为__________________、语法分析、语义分析和中间代码生成、优
化、_______________5个阶段。（3分）
*(0|1)001描述的正规集是____________________________________。4、正规式（2分）
5、最常用的两类语法分析方法是___________________ 和__________________分析法。 6、计算机执行用高级语言编写的程序主要有两种途径：____________和____________。（2分） 7、A->XYZ对应的项目有_________，A->X·YZ，A->XY·Z和_________。（2分） 8、对于文法G，仅含终结符号的句型称为_____________。（2分）
9、文法的符号属性分为___________________和__________________。（2分）
第 2 页 共 8 页
评阅人 得分 三、简答题（共四题，共 30 分）
1、给出生成下述语言的上下文无关文法：（6分） （1）{ anbnambm| n，m>=0} （3分）
（2）为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。（3分） 答案：G[S]: S->S+D|S-D|D
D->0|1|2|3|4|5|6|7|8|9答案： （１）S→AA
A→aAb|ε
2、一个上下文无关文法生成句子abbaa 的推导树如下：（12分）
(1)给出串abbaa 最左推导、最右推导。（4分）
(2)该文法的产生式集合P 可能有哪些元素？（4分） (3)找出该句子的所有短语、直接短语、句柄。（4分） 答案：(1)串abbaa 最左推导:
S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa
最右推导：S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa
第 3 页 共 8 页