南京工业大学继续教育学院编译原理期末考试试卷
(2012-2013学年)
A卷
一、选择题（每题2分，共20分） 得分 1. 一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个_____，以及一组产生式。
A． 字符串 B． 运算符号 C． 开始符号 D． 文法
2.程序的基本块是指_____。
A． 一个子程序 B． 一个仅有一个入口和一个出口的语句 C． 一个没有嵌套的程序段 D． 一组顺序执行的程序段，仅有一个入口和一
个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于_____分析方法。
A． 自左向右 B． 自顶向下 C． 自底向上 D． 自右向左
4．经过编译所得到的目标程序是_____。
A． 四元式序列 B． 间接三元式序列
C． 二元式序列 D． 机器语言程序或汇编语言程序 5．运行阶段的存储组织与管理的目的是_____。
① 提高编译程序的运行速度 ② 节省编译程序的存储空间 ③ 提高目标程序的运行速度 ④ 为运行阶段的存储分配做准备 A. ①② B. ②③ C. ③④ D. ④② 6．词法分析器的输出结果是_____。
A．( ) 单词的种别编码 B．( ) 单词在符号表中的位置 C．( ) 单词的种别编码和自身值 D．( ) 单词自身值 7．正规式 M 1 和 M 2 等价是指_____。
A．( ) M1和M2的状态数相等 B．( ) M1和M2的有向边条数相等
C．( ) M1和M2所识别的语言集相等 D．( ) M1和M2状态数和有向边条数相等
8．文法G：S→xSx|y所识别的语言是_____。
A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 9．语言是_____。
A．句子的集合 B．产生式的集合 C．符号串的集合 D．句型的集合 10．编译程序前三个阶段完成的工作是 A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析
C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化
二、名词解释（每题2分，共20分） 得分 1.最左推导：
2.语法：
3.文法：
4.基本块：
5.语法制导翻译：
6.短语：
7.规范句型：
8.扫描器：
9.超前搜索：
10.语义：
三、填空题（每空1分，共10分） 得分 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为_______________和 _______________ 。 2. 规范规约是最_______________规约。
3. 编译程序的工作过程一般划分为5个阶段：词法分析、_______________ 、语义分析与中间代码生成，代码优化及_______________ 。另外还有_______________和出错处理。
4.符号表中的信息栏中登记了每个名字的有关的性质，如_______________等等。 5.一个过程相应的DISPLAY表的内容为________________________。 6.一个句型的最左直接短语称为句型的_________________________。 7.对于文法G，仅含终结符号的句型称为________________________。
四、简答题（每题10分，共50分） 得分 1.（10分）简述编译程序的工作过程。
2． （共10分）已知文法G[E]:
E→ETE|（E）|i T→*|+
（1） 将文法G改造成LL（1）文法；（3分）
（2） 构造文法G中每个非终结符的FIRST集合及FOLLOW集合；（3分） （3） 构造LL（1）分析表。（4分）
3． （共10分）给定文法G[S]：S→S(S)|ε
（1） 给出句子(()())()()的规范推导过程；（3分） （2） 指出每步推导所得句型的句柄；（3分） （3） 画出该句子的语法推导树。（4分）
4.（10分）写一个文法G, 使其语言为 不以0开头的偶数集。
5.（10分）已知文法G(S)：
S→bAa A→(B | a B→Aa)
写出句子b(aa)b的规范归约过程。
编译原理考试试卷
