编译原理习题答案.ppt

习题16 试用各种不同的形式表示法描述1 的一切精度的近似值集合 解 省略表示法 1 3 1 33 1 333 描述表示法 1 3i i 1 或 1 3i i 1 错误 x x 1 3 10 i i 1 因为形式表示不应涉及任何含义 错误 G N N 1 MM M3M 3 因为文法仅一组重写规则 不是语言 若给出答案 L G N 正确 但不简洁 7 设字母表x 0 1 2 3 4 5 6 7 X 与X 各是什么 各举出4个不同长度的符号串作为例子 解 X是字母表x的正闭包 X 是字母表的闭包 X X X 0 1 00 01 123 345 1234 2345 因此是一切可能带前导0的八进制数的集合X 0 1 00 01 12 345 3456 X 0 1 00 123X 1 00 123 习题22 设文法G 的规则是 a b c a c 0 1试写出VT与VN 并对下列符号串a ab0 a0c01 0a 11与aaa给出可能的推导 解 VT a b c 0 1 VN a aab0 0不能直接推导出b0 因此不能直接推导出ab0 不能写 0 b0不能推导出ab0 a0c01 1 01 c01 0c01 a0c010a a不能直接推导出0a 不能写 a 0a不能推导出0a 11 1不能直接推导出11 不能写 1 11不能推导出11 aaa a aa aaa 3 设G E E T E T E TT F T F T FF E i1 试给出关于 i i i i与 i i i的推导 2 证明E T F i I是该文法的句型 然后列出它的一切短语与简单短语 解 1 给出推导E T F E T F i 不能写 E T F E i 可以写 E T F E i E E T T T T F T F F T i F T i i T i i F i i i 最左推导 或E E T E F E i T i T F i T i i F i i i i i 最右推导 E T T F F F E F E T F T T F F T F i T F i F F i i F i i i 最左推导 或E T T F T i F i E i E T i E F i E i i T i i F i i i i i 最右推导 2 证明E T F i i是该文法的句型 E E T E T T E T F T E T F F T E T F i T E T F i F E T F i i或E E T E F E i E T i E T F i E T i i E T F i i即 E E T F i i 所以是该文法的句型 因为E EE E T F i iE E iE E T F iE E T iT T F iE E T F i TT iE E T i iT T FE E T F F FF i 包括 所以句型E T F i i中相对于E的短语有E T F i i和E T F i相对于T的短语有T F i T F和i相对于F的短语有i所以句型E T F i i中相对于T的简单短语有T F相对于F的简单短语有i 不能用画语法分析树的方法来寻找短语 因按教学进度 还未讲到语法分析树 简单短语可如下寻找 首先寻找与规则右部相同的子符号串 把它归约成相应的非终结符号后 看是否是句型 如果仍是 则此子符号串是简单短语 否则不是 例如 子符号串E T 可归约成E 但归约后成为E F i i 显然不是句型 所以 E T不是简单短语 对于短语 类似地寻找 即 先找子符号串 看它能否归约到某个非终结符号 再看归约后得到的新符号串是否是句型 是 则是短语 否则 不是短语 当在学习了语法分析树之后 可以也应该使用语法分析树来寻找短语与简单短语 2 ambn n m 0 解 可把ambn n m 0 写成ambmbn m 易见可有文法G S S Sb AbA ab aAb也可以写出下列文法 G S S ab2 Sb aSb或G S S aSb aBbB Bb b可见给定一个语言 可以为它构成若干个不同的文法 习题34 通常程序设计语言包含一些嵌套结构 例如 平衡的括号对 以及对应的if与else等 试简要说明为什么这些结构不能用正则文法描述 答 通常程序设计语言必定包含一些嵌套结构 例如 平衡的括号对 以及对应的if与else等 它们的存在必定因下列规则的必定存在 E E T TT T F FF E i以及S if E SelseS因此 E xEyx y 与S uSvu v 即 E与S等必定是具有自嵌套特性的非终结符号 因此通常的程序设计语言的文法必具有自嵌套特性的非终结符号 也就是说不可能是正则文法 5 下列文法中哪一个是自嵌套的 请说明理由 对于非自嵌套文法给出等价的正则文法 G1 A B C a b P1 A P1 A CB bB CAC AB a答 因存在自嵌套的非终结符号B B CA ABA即 B ABA A 所以文法G1是自嵌套的 G2 A B C a b P2 A P2 A CB CaB bCC aB b答 因不可能得到推导 A xAy 其中 对于B与C 情况类似 所以A B与C都不是自嵌套的非终结符号 文法G2是非自嵌套的文法 为构造等价的正则文法 首先确定相应语言 C aB abC abaB ababC ab iC ab ib 即 C ab ibB bC baB ba iB ba ibC ba ib ab jb即 B ba ib ab jbA CB ab ib ba jb ab kb又 A Ca ab iba即 A ab iba 所以 L G2 ab ib ba jb ab kb i j k 0 ab iba i 0 对于文法G2 可以采用图示法给出相应的正则文法abab abba可给出如下的规则 AA aA BaB AbBC BbS CaABCS 显然 S Ca Bba Abba Babba Ababba Bababba B ab i 1ba ab iba即 S ab iba i 1 为使i 0 让C b 因此 对于 ab iba i 0 有下列规则 S CaC Bb bB AbA Ba a对于 ab ib ba jb ab kb i j k 0 可类似地给出一组规则 这里不拟详细给出 只是请注意 可利用前面的规则以减少规则的个数 习题44 试用不同的方法消去文法G I Ia Ib c的规则左递归 解 步骤1判定文法是规则左递归步骤2消去规左递归 步骤3方法1改写规则左递归成右递归 等价文法G 为 I cI I a b I 方法2改写成扩充BNF表示法 应用规则1提因子有 I I a b c 应用规则2有I c a b 等价文法G 为 I c a b 5 试消去文法G W W A0A A0 W1 0的文法左递归与规则左递归 解 步骤1判定文法是文法左递归还是规则左递归步骤2判定文法是文法左递归 所以按相应算法消去文法左递归如下 步骤2 1 把终结符排序成U1 W U2 A n 2 步骤2 2 执行循环i 1j 1 j i 1不执行关于j的循环 且关于U1 W不存在规则左递归 i 2j 1 有规则A W1 A0 0形如U2 U1 把U1 r1 即 把W A0代入得 A A01 A0 0即 A A 01 0 0j 2 j i 1消去关于U2 A的规则左递归有A 0A A 01 0 A 步骤3最后得到消去左递归的等价文法G W W A0A 0A A 01 1 A 说明 如果在第二步中 把原文法等价变换成扩充表示法 则最终的等价文法是G W W A0A 0 01 0 6 试消去文法G S S Qc Rd cQ Rb Se bR Sa Qf a解 步骤1首先判定是文法左递归还是规则左递归步骤2是文法左递归 按相应算法处理如下 步骤2 1把非终结符号排序成U1 SU2 QU3 R n 3 步骤2 2执行循环 i 1j 1 j i 1 不执行关于j的循环 且关于U1 S不存在规则左递归 i 2j 1 有规则Q Se Rb b 形如U2 U1 把U1 r1即 把S Qc Rd c代入 得 Q Qc Rd c e Rb b 整理后Q Qce Rde Rb ce bj 2 j i 1对U2其消去规则左递归 得Q R de b ce b Q Q ceQ 按扩充表示法 有Q Rb Rde ce b ce i 3j 1 有规则R Sa Qf a 形如U3 U1 形 把U1 r1 即 S Qc Rd c代入 R Qc Rd c a Qf a 整理后 R Rda Qca Qf ca a注意 j循环还未结束 不能消去Ui R的规则左递归 j 2 有规则R Rda Qca Qf ca a 形如U3 U2 把U2 r2 即 把Q R b de ce b Q 代入 按扩充表示法代入的是Q Rb Rde ce b ce 所以R Rda R b de ce b Q ca f ca a 整理 R R b de Q ca f da ce b Q ca f ca aj 3 j i 1消去关于U3 R的规则左递归 得 R ce b Q ca f ca a R R b de Q ca f da R 当按扩充表示法时是 R ce b Q ca f ca a b de Q ca f da 步骤3最后消去了左递归的等价文法G S S Qc Rd cQ R b de ce b Q Q ceQ R b ce Q ca f ca a R R b de Q ca f da R 按扩充表示法时是G S S Qc Rd cQ Rb Rde ce b ce R ce b Q ca f ca a b de Q ca f da 习题51 设有文法G S S aAcB BdSB aScA cAB bA BaB aBc a试对下列符号串 1 aabcccab2 ababccbb进行句型分析 识别是否是文法G S 的句子 当是句子时 给出最左推导 最右推导与相应的语法分析树 解 1 建立最左推导如下 S aAcB aaBccB aabccB aabcccAB aabcccaB aabcccab即 S aabcccab因此 aabcccab是该文法的句子 最右推导如下 S aAcB aAccAB aAccAb aAccab aaBcccab aabcccab语法分析树 画语法分析树并不一定要先写出推导 事实上 根据所给符号串的形式来选择合适的规则便可 例如 输入符号串是 i 不包含if 自然选择I E 之后 因有 与 自然选E E 等等 对于输入符号串ifithenielse i 自然选择I ifBT 其他情况类似 3 为题2中的状态转换图写出相应的有穷状态自动机 它能接受字符串0011011吗 解 这是一个确定有穷状态自动机 因此可写出DFAD如下 DFAD K 0 1 M A E F 其中K A B C D E F M M A 0 BM B 0 DM B 1 CM C 0 AM C 1 FM D 0 AM D 1 CM E 0 DM E 1 CM F 0 EM F 1 A M M A 0 BM B 0 DM B 1 CM C 0 AM C 1 FM D 0 AM D 1 CM E 0 DM E 1 CM F 0 EM F 1 A对输入字符串0011011运行该DFA M A 0011011 M M A 0 011011 M M B 0 11011 M M D 1 1011 M M C 1 011 M M F 0 11 M M E 1 1 M C 1 F因为F E F 所以字符串0011011可以被该DFA所接受 注意 在一般情况下 必须首先判别是确定的FA 还是非确定的FA 然后再写出相应的FA 6 设有NFA 其状态转换图如图所示 试为其构造DFA 解 步骤1首先写出NFA 然后再确定化 NFAN S V M U Z 0 1 M S Z 其中 M M S 0 V M M S 1 M U M V 0 Z M V 1 M M 0 V M M M 1 M U M U 0 M U 1 Z M Z 0 Z M Z 1 Z 步骤3构造DFA如下 DFAN K 0 1 M S F 其中 K S MV MU MUZ MVZ M M S 0 VM M S 1 MU M MV 0 MVZ M MV 1 MU M MU 0 MV M MU 1 MUZ M MVZ 0 MVZ M MVZ 1 MUZ M MUZ 0 MVZ M MUZ 1 MUZ F MVZ MUZ 注意 1 DFAN 的状态名必须用方括号对 与 括住 且状态名中所包含的字母必须按字典顺序排列 数字也一样 2 终止状态之名则必须包含原NFA中终止状态名 如 新终止状态名 MVZ 中包含了原终止状态名Z 7 设有NFAA q0 q1 q2 a b M q0 q1 其中M为 M q0 a q1 q2 M q0 b q0 M q1 a q0 q1 M q1 b M q2 a q0 q2 M q2 b q 试为其构造DFA 它能接受bababab与abababb吗 解 首先写出状态转换矩阵如下 ab q0 q1 q2 q0 q1 q2 q0 q1 q2 q1 q0 q1 q2 q0 q1 q2 q0q1 q1 q0q1 q0 q1 q0 q1 q2 q0 所以DFAA K a b M q0 F 其中 K q0 q1 q0q1 q1q2 q0q1q2 M M q0 a q1q2 M q0 b q0 M q1q2 a q0q1q2 M q1q2 b q1 M q0q1q2 a q0q1q2 M q0q1q2 b q0q1 M q1 a q0q1 M q0q1 a q0q1q2 M q0q1 b q0 F q1 q1q2 q0q1 q0q1q2 运行DFAA 输入字符串babababM q0 bababab M M q0 b ababab M M q0 a babab M M q1q2 b abab M M q1 a bab M M q0q1 b ab M M q0 a b M q1q2 b q1 因为 q1 F 所以 输入字符串bababab可为该DFAA 所接受 输入字符串abababbM q0 abababb M M q0 a bababb M M q1q2 b ababb M M q1 a babb M M q0q1 b abb M M q0 a bb M M q1q2 b b M q1 b 因为M q1 b 不存在 所以 输入字符串abababb不可为DFAA 所接受 运行状态转换图时请注意 1 必须说明最终的状态属于终止状态集 才说可接受 2 不要写成 M q1 b 只能写成 M q1 b 不存在 因而不可接受 习题77 试为文法G S S SaB bBA S aB Ac构造预测分析表 并识别输入符号串bacaac是否该文法的句子 解 首先判别文法是否满足两个先决条件 因为不满足 进行文法等价变换 消去左递归 得到等价文法如下 S bBS S aBS A S aB Ac为其构造预测分析表 现构造如下 abc SS bBS S S aBS S S AA aA SBB AcB Ac abc SS bBS S S aBS S S AA aA SBB AcB Ac 所以输入符号串bacaac是该文法的句子 习题81 根据下列语法分析树 确定全部简单优先关系 以矩阵形式给出 解 E简单优先矩阵如下 ETFi ETE TFT T FiF F E i iT F I 习题103 试为文法G Z Z A A Ai B B i构造算符优先关系 解 易见 构造优先关系 寻找规则U VT 的规则 由规则Z A 因A A i以及A 所以 i 类似地 由A Ai以及A B 有 i ii i i i 以及i 算符优先矩阵如右所示 i 当然 也可以利用语法分析树寻找优先关系 习题114 试利用表5 10中的分析表识别符号串 i i i i是否是文法G5 5的句子 给出识别过程 注意 请指出每步动作 解 题目要求指明每个分析步的动作 因此以表的形式给出分析过程 文法G5 5 E 1 E E T2 E T3 T T F4 T F5 F E 6 F i分析过程见下面 最终结果表明 输入符号串 i i i i是文法G5 5的句子 分析表 所以输入符号串 i i i i是该文法的句子 习题121 根据例6 2中所给语法制导定义 关于输入符号串inti j构造注释分析数 解 语法制到定义如下 可画出注释分析树如下 习题131 为下列类型写出类型表达式 1 指向实型数据的指针数组 该数组的上下界分别为100与1 2 一个函数 实参为一个整型数 返回值为一个指针 它指向由一个整型数和一个字符组成的结构体 解 1 按约定 相应的类型表达式是 array 1 100 pointer real 2 按约定 相应的类型表达式是 integer pointer record i integer c char 2 设有C语言程序片段如下 structcell inta intb typedefstructcell pcell cellBuf 200 pcellhandle intx celly 试给出标识符Buf与Handle所关联的类型表达式 解 Buf所关联的类型表达式是 array 0 199 cell 其中cell所关联的类型表达式是 record a integer b integer Handle所关联的类型表达式是 integer cell Pcell其中Pcell所关联的类型表达式是 pointer cell 习题141 试为下列赋值语句x a b c d e f 生成目标代码 其中用变量名表示存储地址 且假定有三个寄存器可用 解 目标代码如下 MOVb r1ADDc r1MOVa r2DIVr1 r2MOVe r1ADDf r1MOVd r3DIVr1 r3SUBr3 r2MOVr2 x 3 试应用6 3 3 2节中关于条件语句的翻译方案 给出下列条件语句的目标代码 if a0 x b a elsex a b 解 MOVa t2MOVa t4CMPt5 1CMPt2 bCMPt4 0CJ l1CJ 8GOTOL2GOTO 12GOTO 12L1 MOVb t6MOV 1 t1MOV 1 t3SUBa t6GOTO 8GOTO 8MOVt6 xMOV 0 t1MOV 0 t3GOTOL3MOVt1 t5L2 MOVa t7ANDt3 t5SUBb t7MOVt7 xL3 5 试给出赋值语句序列 n 1 while 2 n 1 2 n 1 399 n n 1 的目标代码 解 L1 MOV 2 t1L2 MOVn t4MPYn t1ADD 1 t4SUB 1 t1MOVt4 nMOV 2 t2GOTOL1MPYn t2L0 ADD 1 t2MPYt2 t1MOVt1 t3CMPt3 399CJ L2GOTOL0 习题152 试把表达式 a b c d a b c 翻译成 1 逆波兰表示 2 四元式序列 3 三元式序列解 1 逆波兰表示 ab cd ab c 2 四元式序列 3 三元式序列 abt1 ab cdt2 cd t1t2t3 abt4 ab t4ct5 c t3t5t6 3 试把逆波兰表示abc de f 还原成中缀表达式解 还原成 a b c d e f6 试写出题4中程序片段的四元式表示 解 positive 0 negative 0 先展开循环如下 zero 0 i 1 for i 1 i100 gotoFINISH if A i 0 if A i 0 positive positive 1 positive positive 1 elseif A i 0 elseif A i 0 zero zero 1 zero zero 1 elseelsenegative negative 1 negative negative 1 i i 1 gotoLOOP FINISH 四元式序列如下 1 0positive 14 go 18 2 0negative 15 zero1t3 3 0zero 16 t3zero 4 1i 17 go 20 5 i100 23 18 negative1t4 6 Ait1 19 t4negative 7 t10 9 20 i1t5 8 go 12 21 t5i 9 positive1t2 22 go 5 10 t2positive 23 11 go 20 12 Ait2 13 t20 15 9 试给出赋值语句A i B i C A k D i j 的三元式表示 解 Bi Ak C ij D Ai 习题171 设有计算z ab的C程序如下 x a y b z 1 while y 0 if y 2 1 z z x y y 2 x x x 其中a和b都是整型变量 1 试办为其构造四元式序列 2 从四元式序列构造流图 并指明它由哪几个基本块组成 解 先把循环结构展开成由条件语句和goto语句组成的结构 然后再写出四元式序列 8 设有C程序如下 definem30main intI n t intA 100 n 50 k 1 for i k ik m 1 gotoFINISH t A i A i A i n A i n t i i 1 gotoLOOP FINISH 四元式序列如下 50n 1k ki kmt1 和 是循环不变表达式可外提 t11t2 it2 go go 25 2it3可计算强度削减 At3t4 t4t int5 2t5t6 At6t7 2it8公共子表达式可消去 与 At8t9对t8的复写传播可删除无用代码 t7t9t9对t10情况相同 int10公共子表达式可消去 与 2t10t11可计算强度削减 20 At11t12 21 tt12t12 22 i1t13 23 t13i 24 go 4 25