试卷
答题时限： 分钟 考试形式：闭卷笔试
得分统计表：
一、单项选择题（请从 个备选答案中选择最适合的一项，每小题 分，共 分）
编译程序是对（ ）
汇编程序的翻译 高级语言程序的解释执行
机器语言的执行 高级语言的翻译
词法分析器的输出结果是（ ）
．单词的种别编码 ．单词在符号表中的位置
．单词的种别编码和自身值 ．单词自身值
在规范规约中，用（ ）来刻画可规约串。

．直接短语 ．句柄 ．最左素短语 ．素短语
与正规式 等价的正规式是（ ）
．
．
． ．
若项目集 含有 α·，则在状态 时，仅当面临输入符号 ∈ 时，才采取 α·动作的一定是（ ）
． 文法 ． 文法 ． 文法 ． 文法
四元式之间的联系是通过（ ）实现的。

指示器 临时变量 符号表 程序变量
．文法 ： 所识别的语言是（ ）
． ． ． ≥ ．
有一语法制导翻译如下所示：
若输入序列为 ，且采用自下而上的分析方法，则输出序列为（ ）
． ．
．关于必经结点的二元关系，下列叙述不正确的是（ ）
．满足自反性 ．满足传递性 ．满足反对称型 ．满足对称性
．错误的局部化是指（ ）。

．把错误理解成局部的错误 ．对错误在局部范围内进行纠正
．当发现错误时，跳过错误所在的语法单位继续分析下去
．当发现错误时立即停止编译，待用户改正错误后再继续编译
二、判断题（每小题 分，共 分）
文法 的一个句子对应于多个推导，则 是二义性的。

（× ）
动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。

（√ ） 算符优先文法采用“移进－规约”技术，其规约过程是规范的。

（ × ）
删除归纳变量是在强度削弱以后进行。

（ √ ）
在目标代码生成阶段，符号表用于目标代码生成。

（ × ）
三、简答题（每小题 分，共 分）
构造正规式 相应的正规式并化简。

（共 分）
（ ）根据正规式，画出相应的 （ 分）
（
（ ）化简，并画出 （ 分）
划分为状态： 将这三个状态命名为 ， ， 三个状态
（共 分）
（ ）写出句型 的最右推导并画出语法树（ 分）
＋ ＋
（ ）写出该句型中所有的短语、直接短语、句柄和最左素短语。

（ 分） 短语： 、 、 、 直接短语： 、 句柄： 最左素短语：
将下列语句翻译为逆波兰表示，三元式、间接三元式和四元式表示：（共 分）
逆波兰表示（ 分）
＋
三元式（ 分）
间接三元式（ 分）
间接码表：
四元式（ 分）
－
四、综合题（共 分）
已知文法 ：（共 分）
求文法 的各非终结符号的 和 集合。

（ 分）
构造文法 的优先关系矩阵，并判断该文法是否是算符优先文法。

（ 分）
是一个算符优先文法。

分析句子 ，并写出分析过程。

（ 分）
步骤 符号栈 输入串 输出
已知文法 ：（共 分）
构造该文法的拓广文法。

（ 分）
→
→
→
→
构造其 项目集规范族，并给出识别活前缀的 。

（ 分）
构造其 分析表，并判断该文法是否是 文法。

（ 分）
状态 移进－规约冲突，计算 的 集合： ＝ ，可以采用 冲突消解法，得到如下 分析表：
该文法是 （ ）文法。

设有如下基本块：（共 分）
假设变量 ， ， 在基本块出口之后是活跃的，给出优化后的四元式序列。

（ 分） ＝ ＋
以下程序段是最内循环（共 分）
画出程序流图，并找出回边与循环。

（ 分）
对循环优化（ 分）
代码外提：对于 中的赋值四元式 ，由于循环中没有对 的定值操作，所有对 的定值都在循环外，所以，它是循环中的不变运算，可以进行代码外提。

删除归纳变量：循环中 是基本归纳变量， 是与 同族的归纳变量，两者有如下线性关系： ，则 可以用 替代，相应的 可用
替代，再将新的不变运算提到循环外。

画出优化后的程序流图（ 分）
有一程序如下：
试用图表示 调用 前后活动记录的过程。

（共 分）
安全专项培训
→
的活动记录
（调用 （ ）
→
→
的活动记录
（调用 （ ）之 →。