北方工业大学
序号 《编译原理》课程期末复习题（答案）
2016年春季学期
开课学院
考试方式：闭卷
A卷
考试时间：120 分钟
班级 姓名 学号 题 号 得 分 阅卷人 装
一 二 三 四 五 六 七 八 九 十 总 分 一判断题（每个小题1分，共10分）
1. 程序语言主要由语法和语义两方面定义。 （ ） 2. 自上而下分析方法会遇到的主要问题有左递归和回溯。 （ ） 3. 已知文法G：E?i | EAE，A?+|* ，其中的终结符号集包括{i，+}。（ ） 4. 编译程序是将高级语言程序翻译成机器语言程序。 （ ） 5. 只含有综合属性的属性文法称为S-属性文法。 （ ）
订
6. LL(1)文法中第一个L的含义是从左到右扫描输入串。 （ ） 7. 在编译中进行语法检查的目的是为了发现程序中所有错误。 （ ） 8. 一个语义子程序描述了一个文法所对应的翻译工作。 （ ） 9. 一个句型的直接短语是唯一的。 （ ） 10. 确定的自动机以及不确定的自动机都能正确地识别正规集。 （ ） 解：1.√ 2.√ 3.× 4.× 5.√ 6.√ 7.× 8.× 9.× 10.√
二、选择题（每个小题1分，共20分）
线
1. 文法分为四种类型，即0型、1型、2型、3型。其中3型文法是____。 A. 短语文法 B. 正规文法 C. 上下文有关文法 D. 上下文无关文法 2. 不可能是目标代码。
A. 汇编指令代码 B. 可重定位指令代码 C. 绝对指令代码 D. 中间代码 3. 将编译程序分成若干个“遍”是为了 。
A. 提高程序的执行效率 B. 利用有限的机器内存并提高机器的执行效率 C. 使程序的结构更加清晰 D. 利用有限机器内存但降低了机器的执行效率 4. 后缀式ab+cd+/可用表达式 来表示。
北方工业大学试卷 第1页 共12页
A. a+b/c+d B. (a+b)/(c+d) C. a+b/(c+d) D. a+b+c/d 5. 文法G：S→xSx|y所识别的语言是 。
A. xyx
B. (xyx)*
6. 文法G[E]： E→E+T|T T→T*P|P P→(E)|i
则句型P+T+i的句柄和最左素短语为 。
A. P+T和i
B. P和P+T C. i和P+T+i D. P和T
7. 设有文法G[E]： E→E*T|T T→T+i|i
句子1+2*8+6按该文法G归约，其值为 。 A. 42 B. 23 C. 30 D. 17 8. 规范归约指 。 A. 最右推导的逆过程 9. 词法分析所依据的是 。 A. 语义规则
B. 构词规则
C. 语法规则
D. 等价变换规则
10. 状态转换图（见下图）接受的集合为 。
0 X 1 Y 0
C. xnyxn(n≥0) D. x*yx*
B. 最左推导的逆过程
C. 规范推导 D. 最左归约的逆过程
A. 以 0开头的二进制数组成的集合 B. 以0结尾的二进制数组成的集合 C. 含奇数个0的二进制数组成的集合 D. 含偶数个0的二进制数组成的集合 11. 词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此， 。 A. 词法分析器作为子程序较好 B. 词法分析器并不作为一个独立的阶段 C. 词法分析器分解为多个过程，由语法分析器选择使用 D. 词法分析器应作为独立的一遍
12. 若a为终结符，则A→α·aβ为 项目。 A. 移进
B. 归约
C. 接受
C. 语义规则
D. 等价变换规则 D. 待约
13. 中间代码生成所依据的是 。 A. 语法规则
B. 词法规则
北方工业大学试卷 第2页 共12页
14. 终结符具有 属性。 A. 传递
B. 继承
C. 抽象
D. 综合
15. 下推自动机识别的语言是 。 16. 常用的中间代码形式不含 。
A. 三元式 B. 四元式 C. 逆波兰表达式 D. 语法树 17. 算符文法是指 的文法。
A. 没有形如U→...VW...的产生式（U、V、W?VN） B. VT中任意两个符号之间至多存在一种算符优先关系 C. 没有相同右部的产生式 D. 没有形如U→ε的产生式
18. 下述语句类中，____________在编译阶段通常不产生可执行代码。 A. 变量说明语句 B. 流程控制语句 C. 输入输出语句 D. 赋值语句 19. 文法所描述的语言是 的集合。 A. 文法的字母表中符号组成的符号串 B. 文法的字母表中终结符号组成的符号串 C. 由文法开始符号推导的符号串 D. 由文法开始符号推导的终结符号串
20. 符号串ab1b2是文法G[A]：A→aB, B→bB|b的句子，该句子的句柄是________。 A. b1 B. b2 C. a D. b1b2 解：1. B 2. D 3. C 4. B 5. C
6. B 7. A 8. A 9. B 10. D 11. A 12. A 13. C 14. D 15. C 16. D 17. A 18. A 19. D 20. B
三、已知文法G的产生式为：
E?T|E+T|E-T
T?F|T*F (2-1) F? (E)|i
试求：
（1）消除该文法的左递归；（5分）
（2）利用(1)得到的文法G’(2-1)，求(i+i*i)的最左推导和语法分析树。（5分） 解：（1）
E?TE’
E’?+TE’|-TE’ |ε T?FT’|
北方工业大学试卷 第3页 共12页
A. 0型语言 B. 1型语言 C. 2型语言 D. 3型语言