编译原理(清华大学-第2版)课后习题答案

1 第三章第三章 N D N D 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 N ND NDDN ND NDD L aL a a 0 1 3 9 a 0 1 3 9 n n 且且 n 1 n 1 0 1 3 9 0 1 3 9 n n 且且 n 1n 1 ab ab a an nb bn n n 1n 1 第第 6 6 题题 1 1 i i 2 2 i i 3 3 i i i i 4 4 i i ii i i 5 5 i i i i i i i i i i i i i i i i 6 6 i i i i i i i i ii i i 第第 7 7 题题 i i i i i i 2 i i i i i i 第第 9 9 题题 语法树语法树 s ss ss a aa 推导 S SS SS S aa a 11 11 推导推导 E E T E T F E E T E T F 语法树语法树 E E T TF 短语短语 T FT F E T FE T F 直接短语直接短语 T FT F 句柄句柄 T FT F 1212 3 短语 短语 直接短语 直接短语 句柄 句柄 13 1 13 1 最左推导 最左推导 S S ABSABS aBSaBS aSBBS aSBBS aBBSaBBS abBSabBS abbSabbS abbAaabbAa abbaaabbaa 最右推导 最右推导 S S ABSABS ABAaABAa ABaaABaa ASBBaaASBBaa ASBbaaASBbaa ASbbaaASbbaa AbbaaAbbaa a1b1b2a2a3a1b1b2a2a3 2 2 文法 文法 S S ABSABS S S AaAa S S A A a a B B b b 3 3 短语 短语 a1a1 b1b1 b2 b2 a2a2 bbbb aaaa abbaa abbaa 直接短语 直接短语 a1a1 b1b1 b2 b2 a2a2 句柄 句柄 a1a1 1414 1 1 S S ABAB A A aAbaAb B B aBbaBb 2 2 S S 1S01S0 S S A A A A 0A10A1 第四章第四章 1 1 1 1 构造下列正规式相应的构造下列正规式相应的 DFADFA 1 1 1 0 1 1011 0 1 101 NFANFA 0123 1101 0 1 4 2 2 1 1010 1 010 1 01 1010 1 010 1 0 NFANFA 4 2 00 0 4 0 0 0 0 10 11 1 01 0 1 0 3 NFA 3 NFA 4 NFA 01 b 3 6 a 2 bb 4 a b 5 b 2 2 解 构造解 构造 DFADFA 矩阵表示矩阵表示 0 01 1 X X 0 0 Z Z X X Z Z X Z X Z Y Y X Z X Z X Z X Z X Y X Y Y Y X Y X Y 01 a 3 4 b a b 2 aa b 5 X Y X Y X Y Z X Y Z X X X Y Z X Y Z X Y Z X Y Z X Y X Y 其中其中 0 表示初态 表示初态 表示终态表示终态 用用 0 0 1 1 2 2 3 3 4 4 5 5 分别代替分别代替 X Z Z X Z X Z Y Y X Y X Y X Y Z X Y Z 得得 DFADFA 状态图为 状态图为 3 50 2 1 1 4 0 0 1 0 0 1 1 0 1 0 3 3 解 构造 解 构造 DFADFA 矩阵表示矩阵表示 构造构造 DFADFA 的矩阵表示的矩阵表示 0 01 1 S S 0 0 V Q V Q Q U Q U V Q V Q Z V Z V Q U Q U Q U Q U V V Q U Z Q U Z Z V Z Z Z Z V V Z Z Q U Z V Z V Z Q U Z Q U Z Z Z Z Z Z Z 其中其中 0 表示初态 表示初态 表示终态表示终态 替换后的矩阵替换后的矩阵 0 01 1 0 00 01 12 2 1 13 32 2 2 24 45 5 3 6 66 6 4 46 6 5 3 35 5 6 66 66 6 构造构造 DFADFA 状态转换图 略 状态转换图 略 4 4 1 1 解 解 构造状态转换矩阵 构造状态转换矩阵 6 a ab b 0 0 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 转换为转换为 a ab b 0 0 1 12 2 1 1 1 12 2 2 20 0 2 2 3 3 0 0 1 1 2 2 3 a 0 3 3 a 0 3 2 3 0 1 2 3 0 1 0 1 a 1 1 0 1 a 1 1 0 1 b 2 2 0 1 b 2 2 2 2 解 首先把 解 首先把 M M 的状态分为两组 终态组的状态分为两组 终态组 0 0 和非终态组 和非终态组 1 1 2 2 3 3 4 5 4 5 此时此时 G G 0 0 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 a a 1 3 0 5 1 3 0 5 1 2 3 4 5 1 2 3 4 5 b b 4 3 2 5 4 3 2 5 由于由于 4 4 a a 0 0 1 2 3 5 1 2 3 5 a a 1 3 5 1 3 5 因此应将因此应将 1 2 3 4 5 1 2 3 4 5 划分为划分为 4 1 2 3 5 4 1 2 3 5 G 0 4 1 2 3 5 G 0 4 1 2 3 5 1 2 3 5 1 2 3 5 a a 1 3 5 1 3 5 1 2 3 5 1 2 3 5 b b 4 3 2 4 3 2 因为因为 1 5 1 5 b b 4 4 23 23 b b 2 3 2 3 所以应将所以应将 1 2 3 5 1 2 3 5 划分为划分为 1 5 2 3 1 5 2 3 G 0 1 5 2 3 4 G 0 1 5 2 3 4 1 5 1 5 a a 1 5 1 5 1 5 1 5 b b 4 4 所以所以 1 5 1 5 不用再划分不用再划分 2 3 2 3 a a 1 3 1 3 2 3 2 3 b b 3 2 3 2 因为因为 2 2 a a 1 1 3 3 a a 3 3 所以所以 2 3 2 3 应划分为应划分为 2 3 2 3 所以化简后为所以化简后为 G G 0 2 3 4 1 5 0 2 3 4 1 5 7 7 去除多余产生式后 构造去除多余产生式后 构造 NFANFA 如下如下 7 S A B D Q Z a b b a b b b a b a b 确定化 构造确定化 构造 DFADFA 矩阵矩阵 a ab b S SA AQ Q A AA AB ZB Z B ZB ZQ QD D Q QQ QD ZD Z D DA AB B D ZD ZA AD D B BQ QD D 变换为变换为 a ab b 0 00 01 13 3 1 11 12 2 2 2 3 34 4 3 33 35 5 4 41 16 6 5 5 1 14 4 6 63 34 4 化简 化简 G 0 1 3 4 6 2 5 G 0 1 3 4 6 2 5 0 1 3 4 6 a 1 3 0 1 3 4 6 a 1 3 0 1 3 4 6 b 2 3 4 5 6 0 1 3 4 6 b 2 3 4 5 6 所以将所以将 0 1 3 4 6 0 1 3 4 6 划分为划分为 0 4 6 1 3 0 4 6 1 3 G 0 4 6 1 3 2 5 G 0 4 6 1 3 2 5 0 4 6 b 3 6 4 0 4 6 b 3 6 4 所以所以 划分为划分为 0 4 6 0 4 6 G 0 4 6 1 3 2 5 G 0 4 6 1 3 2 5 不能再划分 分别用不能再划分 分别用 0 0 4 4 1 1 2 2 代表各状态 构造代表各状态 构造 DFADFA 状态转换图如下 状态转换图如下 8 01 4 a b a a b ba b 2 8 8 代入得 代入得 S S 0 1S 1 0 1S 1 1 0S 0 1 0S 0 01 S 01 S 10 S 10 S 01 10 S 01 10 S 01 10 S 01 10 S 01 10 01 10 01 10 01 10 01 10 01 10 构造构造 NFANFA S A B Z 0 1 0 1 1 0 由由 NFANFA 可得正规式为可得正规式为 01 10 01 10 01 10 01 10 01 10 01 10 9 9 状态转换函数不是全函数状态转换函数不是全函数 增加死状态增加死状态 8 8 G 1 2 3 4 5 8 6 7 G 1 2 3 4 5 8 6 7 1 2 3 4 5 8 1 2 3 4 5 8 a a 3 4 8 3 4 8 3 4 3 4 应分出应分出 1 2 3 4 5 8 1 2 3 4 5 8 b b 2 6 7 8 2 6 7 8 1 2 3 4 5 8 1 2 3 4 5 8 c c 3 8 3 8 1 2 3 4 5 8 1 2 3 4 5 8 d d 3 8 3 8 所以应将所以应将 1 2 3 4 5 8 1 2 3 4 5 8 分为分为 1 2 5 8 1 2 5 8 3 4 3 4 G 1 2 5 8 3 4 6 7 G 1 2 5 8 3 4 6 7 1 2 5 8 a 3 4 8 1 2 5 8 a 3 4 8 8 8 应分出应分出 1 2 5 8 b 2 8 1 2 5 8 b 2 8 1 2 5 8 c 8 1 2 5 8 c 8 1 2 5 8 d 8 1 2 5 8 d 8 G 1 2 5 8 3 4 6 7 G 1 2 5 8 3 4 6 7 1 2 5 a 3 4 8 1 2 5 a 3 4 8 5 5 应分出应分出 G 1 2 G 1 2 3 4 5 3 4 5 6 7 6 7 8 8 去掉死状态去掉死状态 8 8 9 最终结果为最终结果为 1 2 1 2 3 4 3 4 5 6 7 5 6 7 以以 1 3 5 61 3 5 6 代替代替 最简最简 DFADFA 为为 13 a c b b da 5 6 b 正规式正规式 b b a da c a da c bbbb 第五章第五章 1 S a T T T S S a a a S T T S S S a S a T a T S a S S 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 a T T T S T S 消除直接左递归 消除直接左递归 S a T T S T T S T SELECT S a a SELECT S SELECT S T SELECT T S T a SELECT T S T SELECT T FOLLOW T FOLLOW T 构造预测分析表构造预测分析表 a S a T T S T S T S T 10 T S T 分析符号串分析符号串 a a 分析栈分析栈 剩余输入串剩余输入串 所用产生式所用产生式 S a a S T T a a 匹配匹配 T a a T S T T S a a S a T a a a a 匹配匹配 T a T S T T S a 匹配匹配 T S a S a T aa a 匹配匹配 T T 匹配匹配 接受接受 2 E TE E E E T FT T T T F PF F F F P E P a P b P 非终结符名非终结符名是否 是否 FIRST 集集FOLLOW 集集 E否否 a b E 是是 T否否 a b T 是是 a b F否否 a b a b F 是是 a b P否否 a b a b SELECT E TE FIRST TE FIRST T a b SELECT E E SELECT E FOLLOW E SELECT T FT FIRST F a b SELECT T T FIRST T a b SELECT T FOLLOW T SELECT F PF FIRST F a b SELECT F F SELECT F FOLLOW F a b 3 S MH S a H Lso H K dML K L eHf M K M bLM FIRST S FIRST MH FIRST M FIRST H a a d b e 11 FIRST H FIRST L e FIRST K d FIRST M FIRST K b d b FOLLOW S o FOLLOW H FOLLOW S f f o FOLLOW K FOLLOW M e o FOLLOW L FIRST S o FOLLOW K FIRST M FOLLOW M a d b e o FOLLOW M FIRST H FOLLOW S FIRST L e o SELECT S M H FIRST M H FOLLOW S FIRST M FIRST H FOLLOW S d b e o SELECT S a a SELECT H L S o FIRST L S o e SELECT H FOLLOW H f o SELECT K d M L d SELECT K FOLLOW K e o SELECT L e H f e SELECT M K FIRST K FOLLOW M d e o SELECTSELECT M M b b L L M M b b 构造构造 LL 1 分析表分析表 abedfo S a M H M H M H M H M H H L S o K d M L L e H f M b L M K K K K 4 文法含有左公因式 变为文法含有左公因式 变为 S C b a C b A b C a B a A b A A b A a A a A a b A C a b B a B B a B b B b B a b B C a b 5 S A B C D E F S begin A end S begin A end begin A B A B A a if A A B A B A A end B B C CB B C C a a B D B D if C a C a a D E D E D if D E else B D else B else D end E FCE FC if F if b then F if b then if 非终结符是否为空非终结符是否为空 S 否 否 A 否 否 A 是 是 B 否 否 C 否 否 D 否 否 D 是 是 E 否 否 F 否 否 FIRST S begin FIRST A FIRST B FIRST A a if FIRST A FIRST B FIRST C FIRST D a if FIRST C a FIRST D FIRST E if FIRSR D else FIRST E FIRST F if FIRST F if FOLLOW S FOLLOW A end FOLLOW A end FOLLOW B end FOLLOW C end else FOLLOW D end FOLLOW D end FOLLOW E else end FOLLOW F a S A A B C D D E F if then else begin end a b ifthenelsebeginendab S begin A end A B A B A 13 A B A B D C C a D E D D else B D E FC F if b then 6 1 1 S A B 2 A aA a 3 B bB b 提取提取 2 3 左公因子 左公因子 1 S A B 2 A aA 3 A A 4 B bB 5 B B 2 1 S AB 2 A Ba 3 B Db D 4 D d 提取 提取 3 左公因子 左公因子 1 S AB 2 A Ba 3 B DB 4 B b 5 D d 3 1 S aAaB bAbB 2 A S db 3 B bB a 4 1 S i E 2 E E S E S S 提取 提取 2 左公因子 左公因子 1 S i E 2 E SE 3 E SE SE 5 1 S SaA bB 14 2 A aB c 3 B Bb d 消除 消除 1 3 直接左递归直接左递归 1 S bBS 2 S aAS 3 A aB c 4 B dB 5 B bB 6 1 M MaH H 2 H b M M b 消除 消除 1 直接左递归 提取 直接左递归 提取 2 左公因子 左公因子 1 M HM 2 M aHM 3 H bH M 4 H M 7 1 1 A baB 2 A 3 B Abb 4 B a 将将 1 2 式代入式代入 3 式 式 1 A baB 2 A 3 B baBbb 4 B bb 5 B a 提取提取 3 4 式左公因子 式左公因子 1 A baB 2 A 3 B bB 4 B aBbb b 5 B a 3 1 S Aa 2 S b 3 A SB 4 B ab 将将 3 式代入 式代入 1 式 式 1 S SBa 2 S b 3 A SB 4 B ab 15 消除消除 1 式直接左递归 式直接左递归 1 S bS 2 S BaS 3 S b 4 A SB 5 B ab 删除多余产生式删除多余产生式 4 1 S bS 2 S BaS 3 S b 4 B ab 5 1 S Ab 2 S Ba 3 A aA 4 A a 5 B a 提取提取 3 4 左公因子 左公因子 1 S Ab 2 S Ba 3 A aA 4 A A 5 B a 将将 3 代入 代入 1 5 代入 代入 2 1 S aA b 2 S aa 3 A aA 4 A A 5 B a 提取提取 1 2 左公因子左公因子 1 S aS 2 S A b a 3 A aA 4 A A 5 B a 删除多余产生式删除多余产生式 5 1 S aS 2 S A b a 3 A aA 4 A A A A S S 将将 3 代入 代入 4 1 S aS 2 S A b a 3 A aA 16 4 A aA 将将 4 代入 代入 2 1 S aS 2 S aA b 3 S a 4 S b 5 A aA 6 A aA 对对 2 3 提取左公因子提取左公因子 1 S aS 2 S aS 3 S A b 4 S b 5 A aA 6 A aA 删除多余产生式删除多余产生式 5 1 S aS 2 S aS 3 S A b 4 S b 5 A aA 第六章第六章 1 1 S S a a T T T T T T S S S S 解 解 1 1 增加辅助产生式增加辅助产生式 S S S S 求求 FIRSTVTFIRSTVT 集集 FIRSTVTFIRSTVT S S FIRSTVTFIRSTVT S S a a a a FIRSTVTFIRSTVT T T FIRSTVT FIRSTVT S S a a 求求 LASTVTLASTVT 集集 LASTVTLASTVT S S LASTVTLASTVT S S a a LASTVTLASTVT T T a a 2 算符优先关系表算符优先关系表 a a 17 因为任意两终结符之间至多只有一种优先关系成立 所以是算符优先文法因为任意两终结符之间至多只有一种优先关系成立 所以是算符优先文法 3 a F 1 1 1 1 1 1 g 1 1 1 1 1 1 f22 132 1 g22 21 2 1 f33 133 1 g44 41 2 1 f33 133 1 g44 41 2 1 4 栈栈 优先关系优先关系 当前符号当前符号 剩余输入串剩余输入串 移进或规约移进或规约 a a 移进移进 a 规约规约 T a 移进移进 T 规约规约 T T 规约规约 T 移进移进 T 规约规约 T 接受接受 4 扩展后的文法扩展后的文法 S S S S G S G G G T G H H a H S T T S T S 1 FIRSTVT S FIRSTVT G a FIRSTVT G FIRSTVT H a FIRSTCT H a FIRSTVT T FIRSTVT S a LASTVT S LASTVT G a LASTVT G LASTVT H a LASTVT H a LASTVT T LASTVT S a 构造算符优先关系表构造算符优先关系表 a 18 a 因为任意两终结符之间至多只有一种优先关系成立 所以是算符优先文法因为任意两终结符之间至多只有一种优先关系成立 所以是算符优先文法 2 句型句型 a T S H S 的的 短语有 短语有 a T S H S a T S H a T S a T S S H 直接短语有直接短语有 a T S H S 句柄 句柄 a 素短语 素短语 a T S S 最左素短语 最左素短语 a 3 分析分析 a a a 栈栈优先关系优先关系当前符号当前符号剩余输入串剩余输入串移进或规约移进或规约 a a T T T T T T T T a a T T T T T T T T T T T T a a T T T T T T T T T T T T T T T T T T T T a a a a a a a a a a a a a a a a a a a a a a a a a a a a 移进移进 规约规约 移进移进 移进移进 移进移进 规约规约 移进移进 移进移进 规约规约 规约规约 移进移进 规约规约 规约规约 接受接受 分析分析 a a a 栈栈优先关系优先关系当前符号当前符号剩余输入串剩余输入串移进或规约移进或规约 a a T T T T T T a a T T T T T T T T T T a a a a a a a a a a a a a 移进移进 移进移进 规约规约 移进移进 移进移进 规约规约 规约规约 移进移进 规约规约 接受接受 4 19 不能用最右推导推导出上面的两个句子 不能用最右推导推导出上面的两个句子 第七章第七章 1 1 已知文法 已知文法 A A aAd aAb aAd aAb 判断该文法是否是判断该文法是否是 SLRSLR 1 1 文法 若是构造相应分析表 并对输入串 文法 若是构造相应分析表 并对输入串 ab ab 给出分析过程 给出分析过程 解 解 0 A A 1 A aAd 2 A aAb 3 A 构造该文法的活前缀 DFA 由上图可知该文法是 SLR 1 文法 构造 SLR 1 的分析表 ACTIONACTIONGOTOGOTO 状态状态 a ad db b A A 0 0S2S2R3R3R3R3R3R31 1 1 1accacc 2 2S2S2R3R3R3R3R3R33 3 3 3S4S4S5S5 4 4R1R1R1R1R1R1 5 5R2R2R2R2R2R2 输入串 ab 的分析过程 步骤步骤状态栈状态栈符号栈符号栈输入串输入串 ACTIONACTIONGOTOGOTO 1 10 ab S2 2 202 ab R33 3 3023 aAb S5 4 40235 aAb R21 5 501 A acc 3 3 考虑文法 考虑文法 S S AS b AS b A SA aA SA a 1 1 列出这个文法的所有列出这个文法的所有 LRLR 0 0 项目 项目 2 2 按 按 1 1 列出的项目构造识别这个文法活前缀的 列出的项目构造识别这个文法活前缀的 NFANFA 把这个 把这个 NFANFA 确定化为确定化为 DFADFA 说明这个 说明这个 DFADFA 的所有状态全体构成这个文法的的所有状态全体构成这个文法的 LRLR 0 0 规范族 规范族 I0 A A A aAd A aAb A I2 A a Ad A a Ab A aAd A aAb A a I3 A aA d A aA b A I4 A aAd I5 A aAb d b I1 A A A Follow A a a 20 3 3 这个文法是这个文法是 SLRSLR 的吗 若是 构造出它的的吗 若是 构造出它的 SLRSLR 分析表 分析表 4 4 这个文法是这个文法是 LALRLALR 或或 LRLR 1 1 的吗 的吗 解 解 0 S S 1 S AS 2 S b 3 A SA 4 A a 1 列出所有 LR 0 项目 S S S b A a S S S b A a S AS A SA S A S A S A S AS A SA 3 构造该文法的活前缀 NFA I0 S S S AS S b A SA A a I1 S S A S A A SA A a S AS S b SI3 A SA S A S S AS S b A SA A a I5 S AS A S A A SA A a S AS S b I2 S A S S AS S b A SA A a I4 A S A A SA A a S AS S b I6 S b I7 A a A A S AA S A S AS S b a b b b b a a aa a b 由上可知 I1 I3 I5 中存在着移进和归约冲突 在 I1中含项目 S S 归约项 Follow S A a 移进项 Follow S a S b 移进项 Follow S b 在 I3中含项目 A SA 归约项 Follow A a b S b 移进项 Follow A b A a 移进项 Follow A a 在 I5中含项目 S AS 归约项 Follow S a b A a 移进项 Follow S a S b 移进项 Follow S b 由此可知 I3 I5 的移进与归约冲突不能解决 所以这个文法不是 SLR 1 文法 21 4 做 LR 1 项目集规范族 由上可知该文法不是 LR 1 文法 也不是 LALR 1 文法 5 5 一个类 一个类 ALGOLALGOL 的文法如下 的文法如下 Statement Block Block head beginbegin d d Block dhead d S S endend S S Compound Statement beginbegin 试构造其试构造其 LRLR 0 0 分析表 分析表 解 解 设 A B C I1 S S A S A a b A SA a b A a a b S AS a b S b a b I0 S S S AS a b S b a b A SA a b A a a b I2 S A S a b S AS a b S b a b A SA a b A a a b I3 S b a b I4 A a a b I5 I1 A A SA a b S A S a b S AS a b S b a b A SA a b A a a b I6 I1 S A S A a b A SA a b A a a b S AS a b S b a b I7 I2 S S AS a b A S A a b A SA a b A a a b S AS a b S b a b 22 D E A B A C B D E D begin d D D d E s end E s E C begin E 0 A A 1 A B 2 A C 3 B D E 4 D begin d 5 D D d 6 E s end 7 E s E 8 C begin E 构造该文法的活前缀 DFA I0 A A A B A C B D E C begin E D begin d D D d I4 B D E D D d I5 C begin E D begin d E S end E S E I13 E S E E Send E S E I14 E S E I11 D D d I10 B D E I1 A A I2 A B I3 A C I8 C begin E I9 D begin d A D beginbegin BC Ed E d S S E I112 E S end end 构造 LR 0 分析表 ACTIONACTIONGOTOGOTO 状状 态态 beginbegin d dS Sendend A AB BC CD DE E 0 0S5S51 12 23 34 4 1 1accacc 2 2R1R1R1R1R1R1R1R1R1R1R1R1 3 3R2R2R2R2R2R2R2R2R2R2R2R2 4 4S6S6 5 5S9S9S7S78 8 6 6S11S11S7S71010 I6 B D E D D d E S end E S E S I7 E S end E S E 23 7 7S13S13S12S12 8 8R8R8R8R8R8R8R8R8R8R8R8R8 9 9R4R4R4R4R4R4R4R4R4R4R4R4 1010R3R3R3R3R3R3R3R3R3R3R3R3 1111R5R5R5R5R5R5R5R5R5R5R5R5 1212R6R6R6R6R6R6R6R6R6R6R6R6 1313S7S71414 1414R7R7R7R7R7R7R7R7R7rR7rR7R7 6 6 文法 文法 G G U U T T S S a b c d e P S a b c d e P S 其中 其中 P P 为 为 S UTa TbS UTa Tb T S Sc dT S Sc d U US eU US e 1 1 判断判断 G G 是是 LRLR 0 0 SLRSLR 1 1 LALRLALR 1 1 还是 还是 LRLR 1 1 说明理由 说明理由 2 2 构造相应的分析表 构造相应的分析表 解 解 0 S S 1 S UTa 2 S Tb 3 T S 4 T Sc 5 T d 6 U US 7 U e 首先做 LR 0 分析 I0 S S S UTa S Tb U US U e T S T Sc T d I1 S S T S c I1 产生移进 规约冲突 但 Follow S c 可以用 SLR 1 解决 I2 S U Ta U U S S UTa S Tb U US U e T S T Sc T d I3 S T b I4 U e I5 T d I6 T Sc I7 S UT a S T b I8 U US T S T S c 产生移进 规约喝规约 规约冲突 Follow U d e Follow T a b 24 可以用 SLR 1 的方法解决 I9 S UTa I10 S Tb 所以该文法是所以该文法是 SLRSLR 1 1 文法 也是 文法 也是 LALRLALR 1 1 文法 文法 LRLR 1 1 文法 文法 构造 SLR 1 分析表 ACTIONGOTO状态状态 abcde SUT 0S12S11123 1S6acc 2S5S4827 3S10 4R7R7 5R5R5 6R4R4 7S9S10 8R3R3S6R6R6 9R1R1R1R1 10R2R2R2R2 7 7 证明下面文法不是证明下面文法不是 LRLR 0 0 但是 但是 SLRSLR 1 1 S AS A A Ab bBaA Ab bBa B aAc a aAbB aAc a aAb 证明 证明 0 S S 1 S A 2 A Ab 3 A bBa 4 B aAc 5 B a 6 B aAb 构造该文法的活前缀 DFA 25 在 I2项目集中含有 S A 归约项 Follow S A A b 移进项 Follow S b 在 I4项目集中含有 B a 归约项 Follow B a A bBa 移进项 Follow B b 在 I9 项目集中有 B aAb 规约项 Follow B a A Ab 规约项 Follow A b c Follow B Follow A 文法的冲突项可以用 SLR 1 文法来解决 所以该文法是 SLR 1 文法 不是 LR 0 文法 1111 设文法 设文法 G S G S 为 为 S AS S AS A aA bA aA b 1 1 证明证明 G S G S 是是 LRLR 1 1 文法 文法 2 2 构造它的构造它的 LRLR 1 1 分析表 分析表 3 3 给出输入符号串给出输入符号串 abab abab 的分析过程 的分析过程 解 解 0 S S 1 S AS 2 S 3 A aA 4 A b 证明 构造该文法的活前缀 DFA S I0 S S S A A Ab A bBa I2 S A A A b I3 A b Ba B aAc B a B aAb I1 S S I4 B a Ac B a B a Ab A Ab A bBa I7 A Ab I5 A bB a I6 B aA c B aA b A A b I10 B aAc I9 B aAb A Ab I8 A bBa S A b b B a a b A c b 28 I0 S S S AS S A aA a b A b a b I2 S A S S AS S A aA a b A b a b I4 A b a b I6 A a A a b I5 S AS b a A a S A b A a b I0 S S S AS S A aA a b A b a b I2 S A S S AS S A aA a b A b a b I4 A b a b I6 A a A a b I5 S AS b a A a S A b A a b I1 S S I3 A a A a b A aA a b A b a b 29 I0 S S S AS S A aA a b A b a b I2 S A S S AS S A aA a b A b a b I4 A b a b I6 A a A a b I5 S AS b a A a S A b A a b 30 在该文法 I0 I2 中出现了归约 移进冲突 由于归约项目的搜索符集合与移进项目的待移进符号不相 交 所以在 I0 I2中当面临输入符为 时归约 为 a 或 b 时移进 所以该文法是 LR 1 文法 构造它的 LR 1 分析表 ACTIONACTIONGOTOGOTO 状态状态 a ab b S SA A 0 0S3S3S4S4R2R21 12 2 1 1accacc 2 2S3S3S4S4R2R25 52 2 3 3S3S3S4S46 6 4 4R4R4R4R4R4R4 5 5R1R1 6 6R3R3R3R3R3R3 构造输入符号串 abab 的分析过程 步骤步骤状态栈状态栈符号栈符号栈输入串输入串 ACTIONACTIONGOTOGOTO 1 10 0 abab abab S3S3 2 20303 a abab bab S4S4 3 3034034 ab abab ab R4R46 6 4 4036036 aA aAab ab R3R32 2 5 50202 A Aab ab S3S3 6 6023023 Aa Aab b S4S4 7 702340234 Aab Aab R4R46 6 8 802360236 AaA AaA R3R32 2 9 9022022 AA AA R2R25 5 101002250225 AAS AAS R1R15 5 1111025025 AS AS R1R11 1 12120101 S S accacc 1616 给定文法 给定文法 S S dodo S S oror S S dodo S S S S S S actact 1 1 构造识别该文法活前缀的构造识别该文法活前缀的 DFADFA 2 2 该文法是该文法是 LRLR 0 0 吗 是 吗 是 SLRSLR 1 1 吗 说明理由 吗 说明理由 3 3 若对一些终结符的优先级以及算符的结合规则规定如下 若对一些终结符的优先级以及算符的结合规则规定如下 a a oror 优先性大于优先性大于 dodo b b 服从左结合 服从左结合 c c 优先性大于优先性大于 dodo d d 优先性大于优先性大于 oror 请构造该文法的请构造该文法的 LRLR 分析表 分析表 解 解 0 S S 1 S do S or S 2 S do S 3 S S S 4 S act 构造该文法的活前缀 DFA 31 I0 S S S do S or S S do S S S S S act I8 S act I2 S do S or S S do S S do S or S S do S S S S S act I1 S S S S S I3 S S S S do S or S S do S S S S S act I4 S do S or S S do S S S S I5 S S S S S S I6 S do S or S S do S or S S do S S S S S act I7 S do S or S S S S S do actact S do do S act or do S act 由上可知 在 I1中含有项目 S S 归约项目 Follow S S S S 移进项目 Follow S 在 I4中含有项目 S do S 归约项目 Follow s or S do S or S 移进项目 Follow s or S S S 移进项目 Follow s 在 I5中含有项目 S S S 归约项目 Follow s or S S S 移进项目 Follow s 在 I7中含有项目 S do S or S 归约项目 Follow s or S S S 移进项目 Follow s 所以该文法不是 LR 0 也不是 SLR 1 文法 根据算符优先关系构造该文法的 LR 分析表 ACTIONGOTO状态状态 Door act S 0S2S81 1S3acc 2S2S84 3S2S85 4S6S3R2 5R3R3R3 6S2S87 7R1S3R1 对算术表达式文法 对算术表达式文法 i i 32 1 1 构造算符优先关系表和 分析表 并对 进行适合的改写后构造预测分析表 构造算符优先关系表和 分析表 并对 进行适合的改写后构造预测分析表 2 2 分别使用三种表对句子分别使用三种表对句子 i i i i i i 进行分析 进行分析 3 3 对于错误的输入串 对于错误的输入串 i i i i 和和 i i i i 分别查看错误的发现时刻和输入串出错的位置 分别查看错误的发现时刻和输入串出错的位置 解 解 1 1 构造算符优先关系表 文法扩展后为构造算符优先关系表 文法扩展后为 E E E E T E T T T F T F F E F i FirstVT E LastVT E FirstVT E i LastVT E i FirstVT T i LastVT T i FirstVT F i LastVT F i 构造算符优先关系表 i i i i 做做 LRLR 0 0 分析 分析 扩展后的文法为 扩展后的文法为 0 E E 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F i I0 E E E E T E T T T F T F F E F i I1 E E E E T I1 产生移进 规约冲突 但 Follow E 可以用 SLR 1 解决 I2 E T T T F I2 产生移进 规约冲突 但 Follow E 可以用 SLR 1 解决 I3 T F I4 F E E E T E T T T F T F F E F i I5 F i I6 E E T T T F T F F E F i I7 T T F F E F i I8 F E E E T I9 E E T T T F I2 产生移进 规约冲突 但 Follow E 可以用 SLR 1 解决 I10 T T F I11 F E 构造 SLR 1 分析表 ACTION GOTO状态状态 i ETF 0S4S5123 1S6acc 2R2S7R2R2 3R4R4 33 4S4S5823 5R6R6R6R6 6S4S593 7S4S510 8S6S11 9R1S7R1R1 10R3R3R3R3 11R5R5R5R5 做做 LLLL 1 1 分析 分析 消除左递归 文法为 E TE E TE E T FT T FT T F E F i 求 select 集 select E TE first TE first T first FT first F i select E TE SELECT E Follow E Follow E SELECT T FT first F i Select T FT Select T follow T Select F E Select F i i 构造预测分析表 i E TE TE E TE T FT FT T FT F E i 第八章第八章 whilewhile a ba b oror c dc d andand e fe f dodo ifif x yx y thenthen t m nt m n 100100 ifif a ba b gotogoto 106106 34 101 101 gotogoto 102102 102 102 ifif c dc d gotogoto 104104 103 103 gotogoto 111111 104 104 ifif e fe f gotogoto 106106 105 105 gotogoto 111111 106 106 ifif x yxB then while A C do A A B else if D and F then A A 100 100 if A B goto 102 101goto 107 102if A C goto 104 103goto 114 104t1 A B 105A t1 106goto 102 107goto 114 108if D goto 110 109goto 114 110if F 112 111goto 114 112t2 A 100 113 A t2 114114 补充习题补充习题 1 1 对下列各语言写出它们的正规表达式和有限自动机 对下列各语言写出它们的正规表达式和有限自动机 a a 字母表字母表 a b c a b c 上的串 其中第一个上的串 其中第一个 a a 先于第一个先于第一个 b b 解 我们关心的状态是什么时候出现了第一个解 我们关心的状态是什么时候出现了第一个 a a 可以设出现第一个可以设出现第一个 a a 后的状态为后的状态为 1 1 出现第一个出现第一个 a a 之前的之前的 状态为状态为 0 0 必须保证在状态 必须保证在状态 1 1 之前不能出现之前不能出现 b b c c a b ca b c 0 0 a a 1 1 转换为正规式 转换为正规式 c a a b