编译原理答案(部分).pdf

编译原理第三章词法分析作业答案编译原理第三章词法分析作业答案 说明 以下答案仅供同学们参考 有问题的地方欢迎指正 同时 我们希望同学们更好的通 过网上答疑资源与我们进行讨论 7 构造下列正规式相应的 DFA 1 1 1 0 1 101 解 首先构造 NFA 如下 判断 由状态 1 接受字符 1 后可能会到状态 1 或状态 2 故上述状态图为 NFA 现在将其 确定化 引进新的初态节点 X 和终态节点 Y 从 X 到状态 1 以及从状态 4 到 Y 均连一条 箭弧 I I0 I1 X 0 0 1 1 1 1 1 1 1 2 2 1 2 2 1 3 3 1 2 2 1 3 3 1 1 1 2 4 Y 4 1 2 4 Y 4 1 3 3 1 2 2 则 DFA 如下 2 2 1 1010 1 010 1 0 解 构造 NFA 如下 I I0 I1 1 1 2 2 2 2 9 4 3 3 3 3 4 7 5 2 6 6 9 4 4 7 5 2 5 8 7 2 6 6 9 4 3 3 2 5 8 7 2 3 8 9 8 3 3 2 3 8 9 8 2 4 7 8 9 9 2 3 6 14 2 4 7 8 9 9 2 8 9 10 2 3 5 8 11 2 8 9 10 2 8 9 10 3 3 2 3 5 8 11 2 3 4 7 8 9 12 3 3 2 3 4 7 8 9 12 2 4 7 8 9 9 2 3 5 6 8 13 2 3 5 6 8 13 2 3 4 7 8 9 12 2 3 6 14 2 3 6 14 4 9 15 2 3 6 14 4 9 15 5 16 5 16 3 3 DFA 构造如下 注 本题可能会有多种解法 上述答案仅供参考 另外 有兴趣的同学可对上述所得到的 DFA 进行化简 从而可得最简答案 3 0 10 10 10 解 构造状态图如下 经观察可知 上述状态图即为 DFA 4 00 11 01 10 00 11 01 10 00 11 解 构造 NFA 如下 其中没有标明接受字符的线上均为 对上述 NFA 进行确定化并最小化后 最终结果为 具体解题过程从简 8 1 0 1 01 8 4 A a B b Z z 9 1 0 1 010 0 1 9 2 1 0 111 1 12 将图 2 16 所示的状态转换图表示的 FA 分别确定化和最小化 01 a a b b 1 02 45 3 a b a b a b b b b a a a b 图 2 16 状态转换图 解 1 对图 a 1 确定化过程为 closure 0 0 A 初态 closure smove A a 0 1 B closure smove A b 1 C closure smove B a 0 1 B closure smove B b 0 1 B closure smove C b 0 A DFA 如图 最小化 DFA 过程 C a a b BA b b 初始划分为 A B C C 自身一组 不能再分 AB 在一组 查看它们的状态转移 move A a B move A b C move B a B move B b B A B 可区分 新的划分为 A B C 即最后划分 此 DFA 已经是最小化的 2 对图 b 经观察 原图即为确定化的 DFA 最小化 DFA move 0 a 1 move 0 b 2 move 1 a 1 move 1 b 4 move 2 a 1 move 2 b 3 move 3 a 3 move 3 b 2 move 4 a 0 move 4 b 5 move 5 a 5 move 5 b 4 初始划分为 P0 0 1 2 3 4 5 观察第一个子集 0 1 在读入 a 后 都到达同一个状态 1 第二个子集 2 3 4 5 在读入输入符号 a 后 状态 2 和 4 分别转换为第一个子集中的状态 1 和 0 状态 3 和 5 分别转换为第二个状态中的 3 和 5 这就意味着 2 4 中的状态和 3 5 中的状态在读 入 a 后到达了不等价的状态 因此得到了新的划分 P1 如下 P1 0 1 2 4 3 5 观察 P1 中的第一个子集 0 1 在读入 b 后分别到达第二个子集中的状态 2 和 4 第二个子集 2 4 在读入 b 后分别到达第三个子集中的状态 3 和 5 第三个子集 3 5 在读入 b 后分别到达第二个子集中的状态 2 和 4 经过考察 P1 已经不能在化分了 令 1 代表 0 1 消去 0 令 2 代表 2 4 消去 4 令 3 代表 3 5 消去 5 最后得到最小化的 DFA 如下 01 a b a 2 b b a 14 0 10 编译原理第四章语法分析 自上而下分析作业参考答案 说明 以下答案仅供同学们参考 有问题的地方欢迎指正 同时 我们希望同学们更好的通 过网上答疑资源与我们进行交流讨论 1 文法 文法 G1 S a T T T S S 1 1 消去文法 G 的左递归后得 文法 G1 S a T T aT T T T T ST 每个非终结符递归子程序如下 PROCEDURE S if sym a then advance else if sym then advance else if sym then begin advance T if sym then advance else error end else error PROCEDURE T if sym a then begin advance T end else if sym then begin advance T end else if sym then begin advance T if sym then begin advance T end else error end else error PROCEDURE T if sym then begin advance T end 2 2 对文法 G1 进行分析 可知 G1 中不含有左递归 First i First j First A Follow A 因此 文法 G1 是 LL 1 文法 文法 G1 的预测分析表如下 a S S a S S T T T aT T T T T T T T ST T 上述预测分析表不含多重定义入口 因此 文法 G1 为 LL 1 文法 2 文法 文法 G E TE E E T FT T T F PF F F P E a b 1 注解 F A 代表 FIRST A FO A 代表 FOLLOW A 以下均同 F E a b F E F T a b F T a b F F a b F F F P a b FO E FO E FO T FO T FO F a b FO F a b FO P a b 3 3 对文法 G 进行分析 可知 G 中不含有左递归 First i First j First A Follow A 只 需 要 检 测 F E FO E F T FO T F P FO P 即可 因此 文法 G 是 LL 1 文法 3 文法 G 的预测分析表如下 a b E E TE E TE E TE E TE E E E E E T T FT T FT T FT T FT T T T T T T T T T T T T F F PF F PF F PF F PF F F F F F F F F F F P P P a P b P E 上述预测分析表不含多重定义入口 因此 文法 G 为 LL 1 文法 4 4 PROCEDURE E BEGIN T E END PROCEDURE E IF SYM THEN BEGIN ADVANCE E END PROCEDURE T BEGIN F T END PROCEDURE T BEGIN T END PROCEDURE F BEGIN P F END PROCEDURE F IF SYM THEN BEGIN ADVANCE F END PROCEDURE P IF SYM THEN BEGIN ADVANCE E IF SYM THEN ADVANCE ELSE error END ELSE IF SYM a THEN ADVANCE ELSE IF SYM b THEN ADVANCE ELSE IF SYM THEN ADVANCE ELSE error 3 下面文法中 哪些是 下面文法中 哪些是 LL 1 的 说明理由 的 说明理由 其中 1 3 4 题中文法是 LL 1 文法 2 题中文法不是 LL 1 的 4 文法 文法 Expr Expr Expr Expr Var ExprTail ExprTail Expr Var id VarTail VarTail Expr id Expr Expr Expr Expr Expr Expr Var ExprTail ExprTail ExprTail Expr ExprTail ExprTail Var Var id VarTail VarTail VarTail VarTail Expr VarTail VarTail 2 句子 id id id 的分析过程如下 步骤 符号栈 输入串 所用产生式 0 1 2 3 Expr ExprTail Var ExprTail VarTail id ExprTail VarTail id id id id id id id id id id id Expr Var ExprTail Var id VarTail 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ExprTail Expr Expr Expr Expr ExprTail Var ExprTail VarTail id ExprTail VarTail ExprTail Expr ExprTail Expr ExprTail Expr ExprTail Expr ExprTail ExprTail Var ExprTail ExprTail VarTail id ExprTail ExprTail VarTail ExprTail ExprTail ExprTail ExprTail ExprTail id id id id id id id id id id id id id id id id id id id id id VarTail ExprTail Expr Expr Expr Expr Var ExprTail Var id VarTail VarTail Expr Expr Expr Expr Var ExprTail Var id VarTail VarTail ExprTail ExprTail 1 1 因为 E E T E T F 所以 E T F 是文法 G1 的一个句型 短语有 T F E T F 直接短语 T F 句柄 T F 2 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 对于 a a a a 的最左推导 S T T S S S T S T S S T S S S S S S S T S S S T S S S S S S S S S a S S S S a a S S S a a S S a a T S a a S S a a a S a a a a 最右推导 S T T S T a S a T a T S a T T a T S a T a a T S a a T a a S a a T a a T S a a T a a a S a a a a a a a 2 句 型 归约规则 句 柄 a a a a S a a S a a a T S S T a a a S a a T S a a T T S T S T a a S T T S a a T S S T a a S T S a a T T S T S T a a S a a T S a T S S T T a S T T T S a T T S T S T a S T T S a T S S T a S a a T S T T S T S T S T T S 移进 规约 过程 步骤 符号栈 输入串 动作 0 a a a a 预备 1 a a a a 移进 2 a a a a 移进 3 a a a a 移进 4 a a a a 移进 5 S a a a 归约 S a 6 T a a a 归约 T S 7 T a a a 移进 8 T a a a 移进 9 T S a a 归约 S a 10 T a a 归约 T T S 11 T a a 移进 12 S a a 归约 S T 13 T a a 归约 T S 14 T a a 移进 15 T a a 移进 16 T S a a 归约 S 17 T a a 归约 T T S 18 T a a 移进 19 T a a 移进 20 T a a 移进 21 T S a 归约 S a 22 T T a 归约 T S 23 T T a 移进 24 T S a 归约 S T 25 T a 归约 T T S 26 T a 移进 27 S a 归约 S T 28 T a 归约 T S 29 T a 移进 30 T a 移进 31 T S 归约 S a 32 T 归约 T T S 33 T 移进 34 S 归约 S T 35 S 接受 3 1 FIRSTVT S a FIRSTVT T a LASTVT S a LASTVT T a 2 a a 优先表没有多重出口 故该文法是算符优先文法 3 构造文法 G2 的优先函数如下 a f 6 6 2 6 4 2 g 7 7 7 2 3 2 4 输入串 a a a 的算符优先分析过程如下 步骤 符号栈 输入串 动作 规约规则 说明 1 a a a 移进 2 a a a 移进 又 a 最左素 短语为 a 4 S a a 移进 5 S a a 移进 又 a 最左素 短语为 a 7 S S a 移进 且 且 且 且 且 最左 素 短语为 T 又 停 11 S 结束 结束 编译原理第七章参考答案 1 给出下面表达式的逆波兰表示 ab c abcde a bc d A not C D not or not or A B and C not D or or A B or C D not E and or and x y z p1 jnz a b c p2 jump p1 a b c p2 3 表达式 a b c d a b c 三元式表 1 a b 2 1 3 c d 4 2 3 5 a b 6 5 c 7 4 6 间接三元式 1 a b 2 1 3 c d 4 2 3 5 1 c 6 4 5 间接代码 1 2 3 4 1 5 6 四元式表 1 a b T1 2 T1 T2 3 c d T3 4 T2 T3 T4 5 T1 c T5 6 T4 T5 T6 4 赋值句 A B C D 的自下而上语法制导翻译过程如下 输入 栈 place 四元式 A B C D i A B C D i A B C D i i A B C D i E A B C D i E A B C D i E A B C D i E A B C D i E i A B C D i E E A B C C T1 D i E E A B T1 D i E E A B T1 D i E E i A B T1 D i E E E A B T1 D T1 D T2 i E E A B T2 i E E A B T2 i E E A B T2 B T2 T3 i E A T3 T3 A A 6 布尔式 A or B and not C or D 的四元式序列如下 100 jnz A 0 101 j 102 102 jnz B 104 103 j 0 104 jnz C 0 105 j 106 106 jnz D 0 107 j 0 其中 真 出口有 100 与 107 假 出口有 103 104 与 106 7 语句 while A C and B D do if A 1 then C C 1 else while A D do A A 2 的四元式序列如下 100 j A C 102 101 j 0or114 102 j B D 104 103 j 0or114 104 j A 1 106 105 j 109 106 C 1 T1 107 T1 C 108 j 100 109 j MaxSize 如果当前数组已满 出错 Error Return false L Length 修改当前链表长度 L L Length name item 将 item 插入到当前链表中 L L Length info null L L Length link L First L First L Length 修改线性表第一项指针 Return true 注意问题 在给出算法时 一定要注意修改自适应链中 link 域的内容 5 设计一个算法 它将按字典顺序输出二叉树上各结点的名字 定义结点结构如下 struct Node ITEM item Node left right 在采用二叉树方法组织符号表时 要求为 任何节点 p 右枝的所有节点值 均应小于结点 p 的值 而左枝的任何节点值均应大于结点 p 的值 因此 按照字典顺序输出二叉树上各结点的内容时 正确顺序为 先输出右枝节 点的内容 然后是根节点的内容 最后是左枝节点的内容 即 按照中序 算法遍历二叉树 并输出 算法如下 设二叉树 T 根节点指针 root void Inorder BiTree T Node root if root null return Inorder T root rig