编译原理试题及答案(二)PPT课件

编译原理参考答案 程序设计语言 Chapter4 自上而下语法分析 2020 4 14 2 CH 4 练习题1 P81 1 考虑下面文法G1 S a T T T S S 1 消去G1的左递归 然后对每个非终结符 写出不带回溯的递归子程序 解 1 消左后的文法G1 S a T T ST T ST 3 CH 4 练习题1 P81 解 1 不带回溯的递归子程序 S a T ProcedureS Beginifsym a orsym thenadvanceelseifsym thenbeginadvance T ifsym thenadvanceelseerrorendelseerrorEnd 4 CH 4 练习题1 P81 解 1 不带回溯的递归子程序 T ST ProcedureT BeginS T end 解 1 不带回溯的递归子程序 T ST procedureT beginifsym thenbeginadvance S T endEnd 5 CH 4 练习题1 P81 2 经改写后的文法是否是LL 1 的 给出它的预测分析表 消左后的文法G1 S a T T ST T ST 2 因为G1 文法不含左递归 对S a T FIRST a a FIRST FIRST T 集合互不相交且不含 对T ST FIRST ST FIRST 其交集为空 但 FIRST T FIRST ST FIRST 然而 FOLLOW T FIRST T 两者不相交 所以 G1 是LL 1 文法 2020 4 14 6 CH 4 练习题1 P81 2 构造G1 的预测分析表 对S a T 对T ST FIRST a a FIRST ST a FIRST 对T ST FIRST T FIRST ST 预测分析表 FOLLOW T 7 CH4 1 3 给出对符号串 a 的分析过程 步骤符号栈输入串动作 所用产生式 0 S a 初始 用S 查表1 T a S T 展开S2 Ta 匹配 用T a查表3 T Sa T ST 展开T 用S a查表4 T aa S a 展开S5 T 匹配a 用T 查表6 T S T ST 展开T 7 T S 匹配 用S 查表8 T S 展开S9 T 匹配 用T 查表10 T 展开T 11 匹配 12 分析成功 结束分析 8 CH 4 练习题3 P82 3 下面文法中 哪些是LL 1 的 说明理由 1 S ABcA a B b 解 因为FOLLOW S 文法不含左递归 FIRST S a b c 对A a 候选式的FIRST集合互不相交 FIRST A 但 FOLLOW A b c FIRST A a 两者不相交 B b 其候选式的FIRST集合互不相交 FIRST B 但 FOLLOW B c FIRST B b 两者也不相交 所以 文法是LL 1 文法 9 CH 4 练习题3 P82 3 下面文法中 哪些是LL 1 的 说明理由 2 S AbA a B B b 解 1 因为FOLLOW S 对A a B FIRST S a b FIRST B b 与FIRST 相交 所以文法不是LL 1 文法 解 2 对A a 因为 FIRST A a b FOLLOW A b FOLLOW和FIRST两者相交 所以文法不是LL 1 文法 10 CH 4 练习题3 P82 3 下面文法中 哪些是LL 1 的 说明理由 3 S ABBAA a B b 解 虽然FOLLOW S 文法不含左递归 FIRST S a b 对A a 其候选式的FIRST集合不相交 对B b 其候选式的FIRST集合也不相交 但对A a 由B b 出发证明也可 FOLLOW A a b FIRST A a 两者相交 所以 文法不是LL 1 文法 11 CH 4 练习题3 P82 3 下面文法中 哪些是LL 1 的 说明理由 4 S aSe BB bBe CC cCe d 解 因为 文法不含左递归 对S aSe B B bBe C和C cCe d各产生式的候选式的FIRST集合均不相交 即FIRST aSe FIRST B FIRST bBe FIRST C FIRST cCe FIRST d FIRST S a b c d FIRST B b c d FIRST C c d 均不含 所以 文法是LL 1 文法 编译原理参考答案 程序设计语言 Chapter7 语义分析和中间代码产生 2020 4 14 13 P217 1 a b c 后缀式 ab c a b c d e 后缀式 abcde a b c d 后缀式 a bc d notAornot CornotD 后缀式 AnotCDnotornotor AandB or notCorD 后缀式 ABandCnotDoror 2020 4 14 14 P217 3 a b c d a b c 的四元式序列 1 a b T1 2 T1 T2 3 c d T3 4 T2 T3 T4 5 a b T5 6 T5 c T6 7 T4 T6 T7 2020 4 14 15 P218 4 自下而上分析过程中把赋值语句A B C D 翻译成三地址码的步骤 参看p179的语义子程序 语法分析翻译过程 A B C D A E1 C D E1 place k2A E1 E2 D E2 place k3A E1 E3 D A E1 E3 E4 A E1 E5 A E1 E6A E7S 产生一个新的中间变量T1E3 place k5产生代码k5 uminusk3 k1K2k3k4k5k6k7 符号表 2020 4 14 17 A B C D 的三地址码 k5 uminusk3k6 k5 k4k7 k2 k6k1 k7 k1K2k3k4k5k6k7 符号表 参看p179的语义子程序 2020 4 14 18 P218 6 用7 4 2节的办法 把Aor Bandnot CorD 翻译成四元式序列 100 jnz A 0 101 j 102 102 jnz B 104 103 j 0 104 jnz C 105 j 106 106 jnz D 107 j 2020 4 14 19 P218 7 100 j A C 102 101 j 115 102 j B D 104 103 j 115 104 j A 1 106 105 j 109 106 C 1 T1 107 T1 C 108 j 100 109 j A D 111 110 j 100 111 A 2 T2 112 T2 A 113 j 109 114 j 100 115 用7 5 1节的办法 把下面的语句翻译成四元式序列 whileA CandB DdoifA 1thenC C 1elsewhileA DdoA A 2 编译原理参考答案 程序设计语言 Chapter8 Chapter11 2020 4 14 21 CH8 CH11 1 什么是符号表 符号表有哪些重要作用 2 符号表的表项常包括哪些部分 各描述什么 3 有哪些存储分配策略 并叙述何时用何种存储分配策略 4 代码优化的常用措施和优化的三个层次 编译原理参考答案 程序设计语言 补充题 2020 4 14 23 补充题 1 画出编译程序的总体逻辑结构图 简述各部分的主要功能 2020 4 14 24 补充题 2 已知文法G Z Z 0U 1VU 1Z 1V 0Z 0请写出此文法描述的只含有 个符号的全部句子 G Z 产生的语言是什么 该文法在Chomsky文法分类中属于几型文法 2020 4 14 25 解 1 0101 0110 1010 1001 2 分析G Z 所推导出的句子的特点 由Z开始的推导不外乎图1所示的四种情形 由Z推导出10或01后就终止或进入递归 而Z的每次递归将推导出相同的符号串 10或01 所以G Z 产生的语言L G Z x x 10 01 3 该文法属于3型文法 Z 0U 1VU 1Z 1V 0Z 0 2020 4 14 26 补充题 3 已知文法和它的LR分析表如下 给出串dbdb 的LR分析过程 G S 1 S AdB 2 A a 3 A 4 B b 5 B Bdb 6 B LR分析表 2020 4 14 27 解 串dbdb 的LR分析过程如下 28 补充题 4 给定文法和语义动作如下 A aB print 0 A c print 1 B Ab print 2 问 按照以上的语义子程序 aacbb经翻译后的输出结果是什么 请给出翻译过程 29 aacbb翻译后的输出结果是打印出下面的字符串 12020 A aB print 0 A c print 1 B Ab print 2 2020 4 14 30 翻译过程和翻译结果 语法分析 aacbbaaAbb 1 aaBb 2 aAb 3 aB 4 A