编译原理(模拟试卷-更新中)1

编译原理 模拟试卷更新中 1 9 四川理工学院试卷四川理工学院试卷 2015 至至 2016 学年第学年第 2 学期学期 课程名称 编译原理 模拟试卷更新中 命题教师 黎远松 适用班级 软件 2013 级 1 5 班 考试 2016 年 5 月 17 日 12 周二下午 3 00 5 00 共 6 页 注意事项 注意事项 1 满分 100 分 要求卷面整洁 字迹工整 无错别字 2 考生必须将姓名 班级 学号完整 准确 清楚地填写在试卷规定的地方 否则视为废卷 3 考生必须在签到单上签到 若出现遗漏 后果自负 4 如有答题纸 答案请全部写在答题纸上 否则不给分 考完请将试卷和答题 卷分别一同交回 否则不给分 试试 题 模拟更新中 题 模拟更新中 一 选择题 共 10 个小题 每个小题 2 分 共 20 分 1 词法分析器的输入是 A 符号串 B 源程序 C 语法单位 D 目标程序 2 语言是 A 句子的集合 B 产生式的集合 C 符号串的集合 D 句型的集合 3 一个句型中称为句柄的是该句型的最左 A 非终结符号 B 短语 C 句子 D 直接短语 题号一二三四五六七八评阅 统分 教师 得分202018868128黎远松 得分评阅教师 系系 专业专业 级级 班班 学号学号 姓名姓名 密 封 线 密 封 线 内 不 要 答 题 编译原理 模拟试卷更新中 2 9 4 扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小 语法单位即 A 字符 B 单词 C 句子 D 句型 5 构造编译程序应掌握 A 源程序 B 目标语言 C 编译方法 D 以上三项都是 6 正规式 M1 和 M2 等价是指 A M1 和 M2 的状态数相等 B M1 和 M2 的有向边条数相等 C M1 和 M2 所识别的语言集相等 D M1 和 M2 状态数和有向边条数相等 7 代码优化的目的是 A 节省时间 B 节省空间 C 节省时间和空间 D 把编译程序进行等价交换 8 生成中间代码时所依据的是 A 语法规则 B 词法规则 C 语义规则 D 等价变换规则 9 下推自动机识别的语言是 A 0 型语言 B 1 型语言 C 2 型语言 D 3 型语言 10 对应 Chomsky 四种文法的四种语言之间的关系是 A L0 L1 L2 L3 B L3 L2 L1 L0 C L3 L2 L1 L0 D L0 L1 L2 L3 二 是非题 共 10 个小题 每个小题 2 分 共 20 分 下列各题 你认为正确的 请在题 干的括号内打 错的打 1 一个上下文无关文法的开始符 可以是终结符或非终结符 2 一个句型的直接短语是唯一的 3 已经证明文法的二义性是可判定的 得分评阅教师 编译原理 模拟试卷更新中 3 9 4 每个基本块可用一个 DAG 表示 5 每个过程的活动记录的体积在编译时可静态确定 6 2 型文法一定是 3 型文法 7 一个句型一定句子 8 算符优先分析法每次都是对句柄进行归约 9 采用三元式实现三地址代码时 不利于对中间代码进行优化 10 编译过程中 语法分析器的任务是分析单词是怎样构成的 三 回答下列问题 共 3 个小题 每个小题 6 分 共 18 分 1 对于下面程序段 program test input output var i j integer procedure CAL x y integer begin y y y x x y y y x end begin i 2 j 3 CAL i j writeln j end 若参数传递的方法分别为 1 传值 2 传地址 3 传名 请写出程序执行的输出结果 答 答 1 3 2 16 3 16 每个值 2 分 2 计算文法 G M 的每个非终结符的 FIRST 和 FOLLOW 集合 并判断该文法是否是 LL 1 的 请说明理由 G M M TB T Ba B Db eT D d 解答 计算文法的 FIRST 和 FOLLOW 集合 4 分 FIRST M a b e d FIRST T a b e d FIRST B b e d FIRST D d FOLLOW M FOLLOW T a b e d FOLLOW B a FOLLOW D b 得分评阅教师 编译原理 模拟试卷更新中 4 9 检查文法的所有产生式 我们可以得到 1 该文法不含左递归 2 该文法中每一个非终结符 M T B D 的各个产生式的候选首符集两两 不相交 3 该文法的非终结符 T B 和 D 它们都有 候选式 而且 FIRST T FOLLOW T a b e d 所以该文法不是 LL 1 文法 2 分 编译原理 模拟试卷更新中 5 9 3 考虑下面的属性文法 产 生 式 语 义 规 则 S ABC A a B b C c B u S u A u B v C v S v A v A v 3 A u B v B u C v 1 1 画出字符串 abc 的语法树 2 对于该语法树 假设 S u 的初始值为 5 属性计算完成后 S v 的值为多少 答 1 2 分 2 S v 的值为 18 2 分 四 8 分 构造一个 DFA 它接受 a b 上所有包含 ab 的字符串 答案 2 分 构造相应的正规式 a b ab a b 3 分 a a a b b b 3 分 确定化 I 0 I 1 I 0 1 2 1 2 3 1 2 得分评阅教师 S ABC abc 0123 6 45 编译原理 模拟试卷更新中 6 9 1 2 3 1 2 3 1 2 4 5 6 1 2 1 2 3 1 2 1 2 4 5 6 1 2 3 5 6 1 2 5 6 1 2 3 5 6 1 2 3 5 6 1 2 4 5 6 1 2 5 6 1 2 3 5 6 1 2 5 6 b b b a a a a a a b b b 最小化 0 1 2 3 4 5 0 2 1 3 4 5 五 6 分 写一个文法使其语言为 L G anbncm m n 1 n 为奇数 m 为偶数 文法 G S ccCcc cc C b aaAbb a A ACS 六 8 分 对于文法 G S 得分评阅教师 得分评阅教师 012 34 5 b a a 01 b 3 b a 编译原理 模拟试卷更新中 7 9 Ma L a L M bMb S 1 写出句型 b Ma b 的最右推导并画出语法树 2 写出上述句型的短语 直接短语和句柄 答 答 1 4 分 bMabLbbbMbS 2 4 分 短语 Ma Ma b Ma b 直接短语 Ma 句柄 Ma S bM T Ma b L 编译原理 模拟试卷更新中 8 9 七 12 分 对文法 G S S a T T T S S 1 构造各非终结符的 FIRSTVT 和 LASTVT 集合 2 构造算符优先表 3 是算符优先文法吗 4 构造优先函数 答 答 1 4 分 aTLASTVT aSLASTVT aTFIRSTVT aSFIRSTVT 2 4 分 a a 3 是算符优先文法 因为任何两个终结符之间至多只有一种优先关系 1 分 4 优先函数 3 分 a F44244 G55523 得分评阅教师 编译原理 模拟试卷更新中 9 9 八 8 分 文法 G S 及其 LR 分析表如下 请给出串 baba 的分析过程 1 S DbB 2 D d 3 D 4 B a 5 B Bba 6 B LR 分析表 ACTIONGOTO bda SBD 0r3s312 1acc 2s4 3r2 4r6S5r66 5r4r4 6s7r1