编译原理习题集

第二章 2 构造产生下列语言的文法 2 anbmcp n m p 0 解 G S S aS X X bX Y Y cY 3 an bn n 0 cn dn n 0 解 G S S X S Y X aXb Y cYd 5 任何不是以0 打头的所有奇整数所组成的集合 解 G S S J IBJ B 0B IB I J 2 4 6 8 J 1 3 5 7 9 6 思考题 所有偶数个0 和偶数个1 所组成的符号串集合 解 对应文法为 S 0A 1B A 0S 1C B 0C 1S C 1A 0B 3 描述语言特点 2 S SS S 1A0 A 1A0 A 解 L G 1n10n11n20n2 1nm0nm n1 n2 nm 0 且n1 n2 nm 不全 为零 该语言特点是 产生的句子中 0 1 个数相同 并且若干相接的1 后必 然紧接数量相同连续的 0 5 S aSS S a 解 L G a 2n 1 n 1 可知 奇数个 a 5 1 解 由于此文法包含以下规则 AA 所以此文法是 0 型文法 7 解 1 aacb 是文法 G S 中的句子 相应语法树是 最右推导 S aAcB aAcb aacb 最左推导 S aAcB aacB aacb 3 aacbccb 不是文法G S 中的句子 aacbccb 不能从 S 推导得到时 它仅是文法 G S 的一个句型的一部分 而不 是一个句子 11 解 最右推导 1 S AB AaSb Aacb bAacb bbAacb bbaacb 上面推导中 下划线部分为当前句型的句柄 对应的语法树为 短语直接短语句柄 a1 对 A1 b1a1 对 A2 b2b1a1 对 A3 c 对 S1 a2cb3对 B bbaacb 对 S2 第三章 3 假设M 人 W 载狐狸过河 G 载山羊过河 C 载白菜过河 6 根据文法知其产生的语言是 L ambnci m n i 1 可以构造如下的文法VN S A B C VT a b c P S aA A aA A bB B bB B cC C cC C c 其状态转换图如下 7 1 其对应的右线性文法是 A 0D B 0A B 1C C 1 1F C 1 0A F 0 0E 1A D 0B 1C E 1C 0B 2 最短输入串011 3 任意接受的四个串 011 0110 0011 000011 4 任意以 1 打头的串 9 对于矩阵 iii 1 状态转换图 2 3 型文法 正规文法 S aA a bB A bA b aC a B aB bC b C aC a bC b 3 用自然语言描述输入串的特征 以a 打头 中间有任意个 包括0个 b 再跟a 最后由一个a b 所组成的任 意串结尾或者以b 打头 中间有任意个 包括0个 a 再跟b 最后由一个a b 所 组成的任意串结尾 12 1 确定化 ab S S S A A S A A S A A A B B A B B B C A B B B C B C 以上为第一次作业 最小化 0 0 S A S A B C B C 因为 S b A b B 所以 S A S A S A S A 因为 C b B b B 所以 B C B C B C B C 1 1 S A B C S A B C 原原DFADFA已为最小已为最小DFADFA 10 1 G1 的状态转换图 或或 2 G1 等价的左线性文法G1 F F Dd Bb D C B S Ab Db A Sa a C Bc S Eb E Aa 或G1 F F Dd Bb D C B S Ab Db A Sa a C Bc S Aab 21 求出描述习题3 12中图 2 3 所给出有限自动机所识别语言的正规式 2 a ba b 或 ab ab 3 a b aa a 以上为第二次作业 22 1 0 1 1 0 NFA 确定化 Q 0 1 S A B S S A B C A B B S A B C A S A B C A B B B B S A B C A B B 第四章 1 2 将间接左递归转换成直接左递归 将A SA A a 代入S AS 由原文法得 S SAS aS b 消除左递归 S aSS bS S ASS 4 0 1 10 ASB 0 1 1 0 A S B C C C C 0 ASB A A 0 10 1 1 又 属于First S First S Follow S 又 属于First A First A Follow A 又 属于First B First A Follow A 所以此文法为LL 1 文法 8 1 a 消除左递归 S Sb Ab b S AbS bS S bS A Aa a A aA A aA 文法G S AbS bS S bS A aA A aA b 判断G 是否为LL 1 文法 FirstFollow S AbS a S bS b S bS b S A aA a b A aA a A b 没有冲突 所以文法G 为LL 1 文法 补充题 若有文法G S S AB cC A b B aC C aS c 判断文法G是否为LL 1 文法 写出理由 分别求所有非终结符的First和Follow集 若为LL 1 文法 给出其预测分析表 分析句子caac是否符合该文法 答案 无左递归 无左公因子 First A b First B a 因First A 含 First AB First A First B a b First cC c Follow S Follow C Follow A First B Follow S a Follow B Follow S Follow C Follow B Follow S 对S First AB First cC 对A First b First 因First A 含 First A Follow A b a 对B First aC First 因First B 含 First B Follow B a 对C First aS First c 所以 文法G是LL 1 文法 First集 abc S A B C Follow集 abc S A B C 预测分析表 abc SS ABS ABS cCS AB AA A b A BB aC B CC aS C c 分析句子caac 栈输入缓冲区 动作 S caac Cccaac S cC Caac Saaac C aS Sac BAac S AB Bac A Caac B aC Cc cc C c 成功 以上为第三次作业 16 对于如下文法G VAR i real integer Boolean char 1 将G改造为等价的算符优先文法G 令 S VAR v A B C real r integer g Boolean b char c 文法G 可改写为 S vA B A A C C C i B r g b c 该文法是算符文法 2 求出G 的全部优先关系 求FirstVT 得 virgbc S A C B 求LastVT 得 virgbc S A C B 优先关系表 virgbc v r g b c cA S ccB A cA A a B ccB B b 解 拓展文法得文法列表 0 S S 1 S cA 2 S ccB 3 A cA 4 A a 5 B ccB 6 B b I0 S S S cA S ccB I1 S S S I2 S c A S c cB A cA A a c I3 S cA A I4 S cc B A c A B ccB B b A cA A a c I5 A a a I6 S ccB B I7 A cA A I8 B c cB A c A A cA A a c a I9 B b b c a A I10 B cc B A c A B ccB B b A cA A a B A c b a I11 B ccB 37 判断下面的文法是哪 一类LR文法 并构造LR分析表 S SR S a R SR R 解 拓展文法得文法列表 0 S S 1 S SR 2 S a 3 R SR 4 R 项目集规范族 I0 S S S SR S a I1 S S S I2 S SR S SR S a I4 S S R R SR R S I6 R SR S SR S a I3 S a a I5 S SR R I7 R R I8 R S R R SR R S a I9 R SR a 分析表 ActionGOTO a SR 0 S2 1 1 Acc 2S3S2 4 3r2r2r2r2r2 4 S6S7 5 5r1r1r1r1r1 6S3S2 8 7r4r4r4r4r4 8 S6S7 9 9r3r3r3r3r3 无冲突 为LR 0 文法 补充题1 对下列文法G S D R R R P P P S iD i 求出每个非终结符的FIRSTVT集和LASTVT集 并构造算符优先关系矩阵 解 文法G每个非终结符的FIRSTVT集合 FIRSTVT S i FIRSTVT R I FIRSTVT P i FIRSTVT D i 文法G的每个非终结符的LASTVT集合 LASTVT S LASTVT R i LASTVT P i LASTVT D i 优先关系矩阵优先关系矩阵 i i S 1 S A 2 A AB 3 A 4 B aB 5 B b 构造 LR 1 项目集族 I0 S S S A A AB a b A a b I1 S S I2 S A A A B a b B aB a b B b a b I3 A AB a b B a S A I4 B a B a b B aB a b B b a b I5 B b a b b I6 B aB a b a B b LR 1 分析表 ActionGOTO ab SAB 0R3R3R312 1 acc 2S4S5R1 3 3R2R2R2 4S4S5 6 5R5R5R5 6R4R4R4 分析符号串 abab 序号栈 输入 动作 00abab R3 A 102 abab S4 A 2024bab S5 Aa 30245ab R5 B b Aab 40246ab R4 B aB AaB 5023ab R2 A AB AB 602ab S4 A 7024b S5 Aa 80245 R5 B b Aab 90246 R4 B aB AaB 10023 R2 A AB AB 1102 R1 S A A 1201 acc S 以上为第四 五次作业 5 4 解 1 A BC DE 2 ad c d e f g 3 ax 4 cd3 4 abcdef 0 a b 0 a 0 4 if a b x a b c