《编译原理》习题参考答案(六).pdf

编译原理 习题参考答案 六 编译原理 习题参考答案 六 第五章第五章 5 4 为下列类型写类型表达式 为下列类型写类型表达式 a 指向实数的指针数组 数组的下标从指向实数的指针数组 数组的下标从 1 到到 100 b 两位数组 即数组的数组 他的行下标从两位数组 即数组的数组 他的行下标从 1 到到 10 列下标从 列下标从 1 到到 20 c 函数 他的定义域是从整数到整数的指针的函数 它的值域是从 一个整数和一个字符组成的纪录 函数 他的定义域是从整数到整数的指针的函数 它的值域是从 一个整数和一个字符组成的纪录 Solution a array 1 100 pointer real b array 1 10 array 1 20 type c integer pointer integer record i integer c char 假定作为值域的记录类型的两个域分别叫假定作为值域的记录类型的两个域分别叫 i 和和 c 5 6 下列文法定以字面常量表的表 符号的解释和图下列文法定以字面常量表的表 符号的解释和图 5 2 文法的那些 相同 增加了类型 文法的那些 相同 增加了类型 list 它表示类型 它表示类型 T 的元素表 的元素表 P D E D D D id T T list of T char integer E L literal num id L E L E 写一个类似写一个类似 5 3 节中的翻译方案 以确定表达式节中的翻译方案 以确定表达式 E 和表和表 L 的类型 的类型 Solution P D E D D D D id T addtype id entry T type T char T type char T integer T type integer T list of T1 T type list T1 type E literal E type char E num E type integer E id E type lookup id entry E L E type list L type L E L type E type L E L1 L type if L1 type E type then E type else type error 5 16 对下面的每对表达式 找出最一般的合一代换 对下面的每对表达式 找出最一般的合一代换 a 1 2 1 b array 1 pointer 1 2 c 1 2 d 1 1 2 Solution a b S 1 array 1 S 2 pointer 1 S 2 array 1 a c S 1 1 S 2 2 1 a d S 1 S 2 S 1 S 2 b c S 1 array 1 S 2 pointer 1 2 b d 无无 c d S 1 1 S 2 1 2 5 17 仿效例仿效例 5 5 推到下面 推到下面 map 的多态类型的多态类型 map list list map 的的 ML 定义是定义是 fun map f l if null l then nil else cons f hd l map f tl l 在这个函数体中 内部定义的标识符的类型是 在这个函数体中 内部定义的标识符的类型是 null list boolean nil list cons list list hd list tl list list Solution 行行 定型断言定型断言 代换代换 规则规则 1 f Exp Id 2 l Exp Id 3 map Exp Id 4 map f l Exp Funcall 5 null list 0 boolean Exp Id 和和 Type Fresh 6 null l boolean list 0 Exp Funcall 7 nil list 1 Exp Id 和和 Type Fresh 8 l list 0 由 由 2 可得 可得 9 hd list 2 2 Exp Id 和和 Type Fresh 10 hd l 0 2 0 Exp Funcall 11 f hd l 3 0 3 Exp Id 12 f 0 3 由 由 1 可得 可得 13 tl list 4 list 4 Exp Id 和和 Type Fresh 14 tl l list 0 4 0 Exp Funcall 15 map 0 3 list 0 由 由 3 可得 可得 16 map f tl l Exp Funcall 17 cons 5 list 5 list 5 Exp Id 和和 Type Fresh 18 cons list 3 5 3 list 3 Exp Funcall 19 if boolean 6 6 6 Exp Id 和和 Type Fresh 20 if list 1 6 1 3 1 Exp Funcall 21 match 7 7 7 Exp Id 和和 Type Fresh 22 match list 1 7 list 1 Exp Funcall 至此有至此有 map 0 1 list 0 list 1 所以所以 map list list 5 18 假定类型名假定类型名 link 和和 cell 如如 5 5 节那样定义 下面的表达式中 那些结构等价 那些名字等价 节那样定义 下面的表达式中 那些结构等价 那些名字等价 a