编译原理试题A(含答案).pdf

学院 姓名 学号 任课老师 考场教室 选课号 座位号 密 封 线 以 内 答 题 无 效 第 1 页 共 页 电子科技大学电子科技大学 2010 2010 20112011 学年第学年第 2 2 学期期学期期 末末 考试考试 A A 卷卷 答案及评分细则答案及评分细则 课程名称 编译原理 考试形式 闭卷 考试日期 2011 年 6 月 21 日 考试时长 120 分钟 一 选择题 共 10 分 共 10 题 每题 1 分 1 编译程序是将高级语言程序翻译成 D 程序的翻译程序 A 机器语言 B 汇编语言 C 中间语言 D 低级语言 2 强制式语言的理论基础是 A A 冯 诺依曼体系结构 B 数学函数 C 数理逻辑谓词演算 D 抽象数据类型 3 C 语言的以下哪种数据类型属于用户定义类型 C A 整型 B 实型 C 数组型 D 字符型 4 以下哪种数据类型是抽象数据类型 D A Pascal 的变体记录 B C 语言的结构 C Java 的数组 D C 的类 5 从文法开始符推导出的任意符号串是该文法的 C A 短语 B 句子 C 句型 D 句柄 6 一个句型对应的语法树中 有且仅有 2 层的子树的边缘 称为该句型的 A A 直接短语 B 短语 C 素短语 D 活前缀 7 在自上而下的分析过程中 下列哪种情况不会产生回溯 C A 公共左因子 B 左递归 C 右递归 D 产生式 8 下列哪种语法分析法适用于分析 LL 1 文法 A A 预测分析法 B LR 分析法 C 算符优先分析法 D 递归下降分析法 9 项目 A B 称为 C 其中 B VN A 移进项目 B 归约项目 C 待约项目 D 接受项目 10 代码生成时 节省一条指令 MOV Ri x 节省的执行代价为 C A 0 B 1 C 2 D 3 学院 姓名 学号 任课老师 考场教室 选课号 座位号 密 封 线 以 内 答 题 无 效 第 2 页 共 页 二 简答题 共 30 分 共 6 题 每题 5 分 1 什么是绑定 静态绑定和动态绑定有什么区别 绑定 一个对象 或事物 与其各种属性属性建立起某种联系的过程 3 分 分 静态绑定 凡是在编译时编译时 运行前 能确定的属性称为静态属性 实体与静态属性之间的绑定在编译时 运行前 完成 运行时不改变 称为静态绑定 1 分 分 动态绑定 凡是在运行时运行时才能确定的属性称为动态属性 实体与动态属性之间的绑定在运行时完成 称 为动态绑定 1 分 分 评分标准 答出关键词属性 编译时 运行时即可得分 评分标准 答出关键词属性 编译时 运行时即可得分 2 举例说明用户定义类型的 6 种聚合方法 笛卡尔积 PASCAL 的记录 C 的结构 有限映像 数组 序列 串 顺序文件 递归 指针 判定或 PASCAL 的变体记录 C 的联合 幂集 PASCAL 的集合 评分标准 评分标准 答出答出 6 种方式种方式可得可得 4 分分 举例酌情给分 举例酌情给分 3 简述编译的 5 大步骤的功能 以及各步骤的输入与输出 1 词法分析 根据词法规则 进行合法性检查 从构成源程序的字符串中识别出单词符号 字符串 单 词符号串 单词串 符号串 2 语法分析 根据语法规则 进行合法性检查 将单词符号串组合成各类语法单位 构造语法树 单词 符号串 语法树 3 语义分析与中间代码生成 根据语义规则 进行合法性检查 进行初步的翻译 生成中间代码 语法 树 中间代码 4 优化 对中间代码进行等价变换 使代码的效率更高 中间代码 优化后的中间代码 5 目标代码生成 将中间代码翻译成目标代码 目标程序 中间代码 目标程序 评分标准 每个阶段各评分标准 每个阶段各 1 分 分 4 若算符文法算符文法 G 的任何两个终结符 a 和 b 没有优先关系 或者至多至多只有 中的一个优先关系 则称 G 为算符优先文法 评分标准 算符文法 至多 评分标准 算符文法 至多 各各 1 分 分 5 简述循环优化的 3 种方法 各举一个例子 1 代码外提 对 x op y 或 x y op z 如果 y z 均为循环不变量 常数或定值点在 L 之外 则该运算 为循环不变运算 优化时将该运算提到循环入口结点之前所增设的结点中去 2 分 分 2 强度削弱 基本归纳变量 i 每循环一次增加或减少 c 与 i 同族的归纳变量 j 相应增加或减少 c1 c 计 算 j 的乘法可由加法来代替 j j c1 c c1 c 为常数 2 分 分 3 删除归纳变量 用同族归纳变量作为判断条件 如基本归纳变量别无它用 则可将其删除 1 分 分 例如 j 10 i 5 判断条件为 i 10 则 将 i 10 改为 j 105 同时删除 i 相关的语句 学院 姓名 学号 任课老师 考场教室 选课号 座位号 密 封 线 以 内 答 题 无 效 第 3 页 共 页 6 简述存储分配的 3 种方式 各举一个例子 1 静态分配 变量与存储区域的绑定关系在编译时便可建立 并完成存储分配 例如 静态变量的分配 2 分 分 2 栈式分配 当一个程序单元被激活时 在栈顶分配其活动记录 当程序单元退出时 在栈顶将其活动 记录撤销 例如 半静态变量的分配 2 分 分 3 堆分配 由于动态变量的首地址 长度 类型等在编译时无法确定 在执行过程中也可能改变 对于 这些变量 必须分配在堆上 例如 C 中通过 malloc 分配的变量 某些语言中的动态变量等 1 分 分 三 已知文法 共 12 分 E T E T E T T F T F T F F E i 1 证明 i E T F 是该文法的一个句型 3 分 2 给出句型 i E T F 的推导树 3 分 3 指出该句型的所有短语 直接短语和句柄 6 分 答案答案 1 E E T E T F E F F E E F E E T F T E T F F E T F i E T F 3 3 分分 2 3 3 分分 3 短语 i 是关于 F T E 的短语 E T 是关于 E 的短语 E T 是关于 F T 的短语 E T F 是关于 T 的短语 i E T F 是关于 E 的短语 3 3 分分 直接短语 i 是关于 F 的直接短语 E T 是关于 E 的直接短语 2 2 分分 句柄 i 1 1 分分 E E T T F T F i F E T E 学院 姓名 学号 任课老师 考场教室 选课号 座位号 密 封 线 以 内 答 题 无 效 第 4 页 共 页 四 给出下面语句 WhileWhile a b do ifif a 0 thenthen a a 1 elseelse b b 1 翻译得到的中间代码序列 地址从 100 开始 一条代码占 1 个字节 10 分 答案答案 写成三地址代码也可 错一个扣写成三地址代码也可 错一个扣 1 1 分 直到扣完分 直到扣完 100 j a b 102 101 j 110 102 j a 0 104 103 j 107 104 a 1 t1 105 t1 a 106 j 100 107 b 1 t2 108 t2 b 109 j 100 110 五 给出下述语句 if then else 语句 的翻译方案 语义子程序 共 8 分 S if B then M S1 else N S2 3 3 分 分 backpatch B T M CODE backpatch B F N CODE S CHAIN merge S1 CHAIN N CHAIN S2 CHAIN M 2 分 分 M CODE ip N 3 分 分 N CHAIN ip emit goto 0 N CODE ip 六 已知文法 G E 共 15 分 E F e F FT f T ET 1 消除文法的左递归得文法 G 1 分 2 求 G 中各非终结符的的 FIRST 集 FOLLOW 集 8 分 3 构造预测分析表 4 分 4 该文法是不是 LL 1 文法 为什么 2 分 答 1 1 1 分 分 G E E F e F f F F T F T ET 学院 姓名 学号 任课老师 考场教室 选课号 座位号 密 封 线 以 内 答 题 无 效 第 5 页 共 页 2 FIRST 集和 FOLLOW 集 每个集合 每个集合 1 分 分 FIRST FOLLOW E e F f F T 3 预测分析表 每行 每行 1 分 分 e f E E e E F F F f F F F T F F T T ET 4 因为预测分析表无多重定义入口 所以文法 G 是 LL 1 文法 2 分 分 七 设有文法 G E 共 15 分 E L a L L E E 1 列出 G E 的 LR 0 项目集规范族 8 分 2 构造此相应的 SLR 1 分析表 5 分 3 该文法是否为 SLR 1 文法 为什么 2 分 答案答案 1 拓广文法 1 分 分 0 E E 1 E L 2 E a 3 L LbE 4 L E FOLLOW 集如下 1 1 分 分 FOLLOW E FOLLOW E b FOLLOW L b LR 0 项目集规范族 6 6 分 分 I I0 0 I I2 2 I I4 4各各 1 1 分 其余各分 其余各 0 50 5 分 分 I0 closure E E E E E L E a I1 GO I0 E E E I2 GO I0 E L L LbE L E E L E a GO I2 GO I7 I3 GO I0 a E a GO I2 a GO I7 a I4 GO I2 L E L L L bE I5 GO I2 E L E I6 GO I4 E L I7 GO I4 b L Lb E E L E a I8 GO I7 E L Lb E 学院 姓名 学号 任课老师 考场教室 选课号 座位号 密