编译原理考试习题及答案.pptVIP

程序设计语言 Chapter3 词法分析 编译原理参考答案 2020 3 15 CH 3 练习题8 P64 8 给出下面的正规表达式 1 以01结尾的二进制数串 正规式 0 1 01 2 能被5整除的十进制整数 允许任意0开头 0 1 2 3 4 5 6 7 8 9 0 5 不允许0开头 0本身除外 0 5 1 2 3 9 0 1 2 3 9 0 5 2020 3 15 CH 3 练习题7 P64 7 1 1 0 1 101构造DFA 解1 正规式对应的NFA 1 正规式1 0 1 101 DFA 1 正规式1 0 1 101 DFA 2020 3 15 CH 3 练习题7 P64 7 构造下列正规式相应的DFA 1 1 0 1 101解2 正规式对应的NFA 0 4 1 2 3 1 1 0 1 1 0 DFA 2020 3 15 7 构造下列正规式相应的NFA P64 2 1 1010 1 010 1 0 2020 3 15 7 构造下列正规式相应的NFA P64 2 1 1010 1 010 1 0 7 2 1 1010 1 010 1 0的NFA 2020 3 15 CH 3 练习题14 P64 1 正规式 10 0 2 NFA 确定化 DFA 2020 3 15 CH 3 练习题14 P64 1 正规式 10 0 2 NFA DFA 构造一个DFA 它接受S 0 1 上所有满足如下条件的字符串 每个1都有0直接跟在右边 DFA 最简 程序设计语言 Chapter2 高级语言及其语法描述 编译原理参考答案 CH 2 练习题6 P36 6 令文法G6为 N D NDD 0 1 2 3 4 5 6 7 8 9 1 G6的语言L G6 是什么 注意 集合的写法不正确解 L G6 0 1 2 3 4 5 6 7 8 9 0 9数字构成的所有数字串 可以0开头 2 给出句子0127 34和568的最左和最右推导 注意 1 步骤 和 的区别 2 不能写为 解 0127的最左推导 N ND NDD NDDD DDDD 0DDD 01DD 012D 01270127的最右推导 N ND N7 ND7 N27 ND27 N127 D127 0127 CH 2 练习题8 P36 8 令文法为E T E T E TT F T F T FF E i 1 给出i i i i i i 的最左推导和最右推导 解 此处仅以i i i 为例给出答案 最左推导E T T F F F i F i E i E T i T T i F T i i T i i F i i i 最右推导E T T F T E T E T T E F T E i T T i T F i T i i F i i i i i CH 2 练习题8 P36 8 令文法为E T E T E TT F T F T FF E i i i i的语法树 2 给出i i i i i i和i i i的语法树 i i i的语法树 i i i的语法树 注意 树枝和符号均不可随意增减 2020 3 15 CH 2 练习题9 P36 9 证明下面的文法是二义的 S iSeS iS i证明 因为存在句子iiiei 它对应两棵不同的语法树 如右图 所以该文法是二义文法 说明 按定义只要能给出一个反例即可 iiiei不是唯一的反例 编译原理参考答案 程序设计语言 Chapter5 自下而上语法分析 2020 3 15 CH 5 练习题1 P133 1 令文法G1为 E E T TT T F FF E i证明E T F是它的一个句型 指出这个句型的所有短语 直接短语和句柄 证明1 存在从开始符号E出发到E T F的推导 E E T E T F E T F是G1的一个句型 短语 E T F是句型相对于非终结符E的短语 T F是句型相对于非终结符T的短语 直接短语 T F是句型相对于规则T T F的直接短语句柄 T F 2020 3 15 CH 5 练习题1 P133 1 令文法G1为 E E T TT T F FF E i证明E T F是它的一个句型 指出这个句型的所有短语 直接短语和句柄 证明2 可构造出E T F的语法树 如右图所示 E T F是G1的一个句型 证明3 也可用归约来证明 概念熟悉后 短语 直接短语和句柄可直接列出而不用说明 短语 E T F T F直接短语 T F句柄 T F 2020 3 15 CH 5 练习题2 P133 2 考虑下面的表格结构文法G2 S a T T T S S 1 给出 a a a 的最左和最右推导 1 解 a a a 的最左推导 S T T S S S a S a T a T S a S S a a S a a a 最右推导 S T T S T T T T S T T a T S a T a a S a a a a a 2020 3 15 CH 5 练习题2 P133 2 2 指出 a a a 的规范归约及每一步的句柄 根据这个规范归约 给出 移进 归约 的过程 并给出它的语法树自下而上的构造过程 2020 3 15 CH 5 练习题2 P133 2 2 给出 a a a 移进 归约 的过程 2 解 a a a 的 移进 归约 过程 步骤符号栈输入串动作句柄1 a a a a2 a a a 移进 3 a a a 移进a4 S a a 归约S aS5 T a a 归约T Sa6 T a a 移进 7 T a a 移进 8 T a a 移进a 2020 3 15 CH 5 练习题2 P133 2 2 给出 a a a 移进 归约 的过程 2 解 a a a 的 移进 归约 过程 步骤符号栈输入串动作句柄9 T S a 归约S aS10 T T a 归约T Sa11 T T a 移进 12 T T a 移进a13 T T S 归约S aT S14 T T 归约T T S T 15 T T 移进 16 T S 归约S T T S 2020 3 15 CH 5 练习题2 P133 2 2 给出 a a a 移进 归约 的过程 2 解 a a a 的 移进 归约 过程 步骤符号栈输入串动作句柄17 T 归约T T S T 18 T 移进 19 S 归约S T 20成功 分析结束 接受输入串 2020 3 15 CH 5 练习题2 P133 2 2 给出 a a a 的语法树自下而上构造过程 2 解 a a a 的语法树自下而上构造过程 用序号表示 2020 3 15 CH 5 练习题3 P133 3 1 计算练习2文法G2的FIRSTVT和LASTVT S a T T T S S 1 解 执行相应的算法可求得 FIRSTVT S a FIRSTVT T a LASTVT S a LASTVT T a 2020 3 15 CH 5 练习题3 P133 3 2 计算文法G2的优先关系 G2是一个算符优先文法吗 S a T T T S S 2 解 FIRSTVT S a FIRSTVT T a LASTVT S a LASTVT T a 逐一考察S T 和T T S两两相邻的符号 得到算符优先关系 如右图 G2是算符优先文法 2020 3 15 3 4 给出输入串 a a a 的算符优先分析过程 S a T T T S S 最左素短语 2020 3 15 3 4 给出输入串 a a a 的算符优先分析过程 S a T T T S S 最左素短语 2020 3 15 5 1 考虑文法S AS bA SA a列出这个文法的所有LR 0 项目 CH 5 练习题5 P134 解 1 拓广文法 加入S S拓广文法的LR 0 项目有 S SS S S ASS A SS AS S bS b A SAA S AA SA A aA a 2020 3 15 5 2 构造文法S AS bA SA a的LR 0 项目集规范族及识别活前缀的DFA 1 拓广文法 加入S S 2 画出DFA 5 2 构造文法S AS bA SA a的LR 0 项目集规范族及识别活前缀的DFA 0 S SS ASS bA SAA a 5 A SA S A SS ASS bA SAA a 7 S AS A S AA SAA aS ASS b 1 S S A S AA SAA aS ASS b 3 S b 4 A a 2 S A SS ASS bA SAA a 6 A S AA SAA aS ASS b S b a A A S b a A S a b S a b A S A b a S a b A 2020 3 15 33 可编辑 2020 3 15 5 3 文法S AS bA SA a是LR 0 文法吗 不是LR 0 文法 因为存在冲突 例如状态1 状态5 编译原理参考答案 程序设计语言 Chapter4 自上而下语法分析 2020 3 15 CH 4 练习题1 P81 1 考虑下面文法G1 S a T T T S S 1 消去G1的左递归 然后对每个非终结符 写出不带回溯的递归子程序 解 1 消左后的文法G1 S a T T ST T ST CH 4 练习题1 P81 解 1 不带回溯的递归子程序 S a T ProcedureS Beginifsym a orsym thenadvanceelseifsym thenbeginadvance T ifsym thenadvanceelseerrorendelseerrorEnd CH 4 练习题1 P81 解 1 不带回溯的递归子程序 T ST ProcedureT BeginS T end 解 1 不带回溯的递归子程序 T ST procedureT beginifsym thenbeginadvance S T endEnd 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 3 15 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 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 分析成功 结束分析 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 文法 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 文法 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 文法 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 3 15 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 3 15 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 3 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 3 15 A B C D 的三地址码 k5 uminusk3k6 k5 k4k7 k2 k6k1 k7 k1K2k3k4k5k6k7 符号表 参看p179的语义子程序 2020 3 15 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 3 15 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 3 15 CH8 CH11 1 什么是符号表 符号表有哪些重要作用 2 符号表的表项常包括哪些部分 各描述什么 3 有哪些存储分配策略 并叙述何时用何种存储分配策略 4 代码优化的常用措施和优化的三个层次 编译原理参考答案 程序设计语言 补充题 2020 3 15 补充题 1 画出编译程序的总体逻辑结构图 简述各部分的主要功能 2020 3 15 补充题 2 已知文法G Z Z 0U 1VU 1Z 1V 0Z 0请写出此文法描述的只含有 个符号的全部句子 G Z 产生的语言是什么 该文法在Chomsky文法分类中属于几型