习题课 2017-11-23
H7 4.12(b) 文法如下： S→ 𝐿 | 𝑎 L →𝐿,𝑆 | 𝑆 (1)写一个翻译方案，它打印出每个a在句子中是第几个字符。例如，当 句子是(a,(a,(a,a),(a)))时，打印的结果是2， 5， 8， 10， 14。 (2)写出相应的语法制导定义 (3)写出相应的预测翻译器 (4)写出自下而上分析的栈操作代码
概念区分 语义规则和产生式相联系的两种方式 语法制导定义 将文法符号和某些属性相关联，并通过语义规则来描述如何计算属性 的值，没有描述这些规则的计算时机 语法制导的翻译方案 在产生式的右部的适当位置，插入相应的语义动作，按照分析的进程， 执行遇到的语义动作，从而明确了语法分析过程中属性的计算时机。
H7 a自身的信息无法确定a在序列中的位置，因此必须要借助继承属性。 方法一： 继承属性 in：该文法符号推出的字符序列的前面已经有多少字符 4.12(b) 文法如下： S→ 𝐿 | 𝑎 L →𝐿,𝑆 | 𝑆 (1)写一个翻译方案，它打印出每个a 在句子中是第几个字符。例如，当句 子是(a,(a,(a,a),(a)))时，打印的结果是2， 5， 8， 10， 14。 H7 a自身的信息无法确定a在序列中的位置，因此必须要借助继承属性。 方法一： 继承属性 in：该文法符号推出的字符序列的前面已经有多少字符 综合属性 out：该文法符号推出的字符序列的最后一个字符在序列中是第几 个字符 S’ → { S.in = 0; } S S → { L.in = S.in +1; } (L) { S.out = L.out + 1; } S → a { S.out = S.in + 1; print (S.out); } L → { L1.in = L.in; } L1, { S.in = L1.out + 1; } S {L.out = S.out; } L → { S.in = L.in; } S { L.out = S.out; }
H7 a自身的信息无法确定a在序列中的位置，因此必须要借助继承属性。 方法二： 继承属性 in：该文法符号推出的字符序列的前面已经有多少字符 4.12(b) 文法如下： S→ 𝐿 | 𝑎 L →𝐿,𝑆 | 𝑆 (1)写一个翻译方案，它打印出每个a 在句子中是第几个字符。例如，当句 子是(a,(a,(a,a),(a)))时，打印的结果是2， 5， 8， 10， 14。 H7 a自身的信息无法确定a在序列中的位置，因此必须要借助继承属性。 方法二： 继承属性 in：该文法符号推出的字符序列的前面已经有多少字符 综合属性 total：该文法符号推出的字符序列所包含的字符总数 S’ → { S.in = 0; } S S → { L.in = S.in +1; } (L) { S.total = L.total + 2; } S → a { S.total = 1; print (S.in + 1); } L → { L1.in = L.in; } L1, { S.in = L1.in + L1.total + 1; } S {L.total = L1.total +S.total + 1; } L → { S.in = L.in; } S { L.total = S.total; }
H7 a自身的信息无法确定a在序列中的位置，因此必须要借助继承属性。 方法一的语法制导定义： 4.12(b) 文法如下： S→ 𝐿 | 𝑎 L →𝐿,𝑆 | 𝑆 写出相应的语法制导定义 H7 a自身的信息无法确定a在序列中的位置，因此必须要借助继承属性。 方法一的语法制导定义： 继承属性 in：该文法符号推出的字符序列的前面已经有多少字符 综合属性 out：该文法符号推出的字符序列的最后一个字符在序列中是第几 个字符 产生式 语义规则 S’ → S S.in = 0; S → (L) L.in = S.in +1; S.out = L.out + 1; S → a S.out = S.in + 1; print (S.out); L → L1, S L1.in = L.in; S.in = L1.out + 1; L.out = S.out; L → S S.in = L.in; L.out = S.out;
H7 消除左递归 S’ → S S → (L) S → a L → ST T → ,ST | 𝜀 产生式 语义规则 S’ → S 4.12(b) 文法如下： S→ 𝐿 | 𝑎 L →𝐿,𝑆 | 𝑆 写出相应的预测翻译器 H7 消除左递归 S’ → S S → (L) S → a L → ST T → ,ST | 𝜀 产生式 语义规则 S’ → S S.in = 0; S → (L) L.in = S.in +1; S.out = L.out + 1; S → a S.out = S.in + 1; print (S.out); L → ST S.in = L.in; T.in = S.out; L.out = T.out; T → ,ST1 S.in = T.in + 1; T1.in = S.out; T.out = T1.out T → 𝜀 T.in = T.out 构造预测分析器时要消除左递归
H7 int S’(){ return S(0); } int S(int b){ int in, out; 产生式 语义规则 S’ → S S.in = 0; S → (L) L.in = S.in +1; S.out = L.out + 1; S → a S.out = S.in + 1; print (S.out); L → ST S.in = L.in; T.in = S.out; L.out = T.out; T → ,ST1 S.in = T.in + 1; T1.in = S.out; T.out = T1.out T → 𝜀 T.in = T.out H7 int S(int b){ int in, out; if(lookahead == ‘(’){ in = b + 1; match(‘(’); out = L(in) + 1; match(‘)’) }else { match(‘a’); out = b + 1; print(out); } return out; int S’(){ return S(0); }
H7 int L(int b){ int out; out = S(b); out = T(out); return out; } 产生式 语义规则 S’ → S S.in = 0; S → (L) L.in = S.in +1; S.out = L.out + 1; S → a S.out = S.in + 1; print (S.out); L → ST S.in = L.in; T.in = S.out; L.out = T.out; T → ,ST1 S.in = T.in + 1; T1.in = S.out; T.out = T1.out T → 𝜀 T.in = T.out H7 int T(int b) { int out; if(lookahead == ‘,’){ match(‘,’); out = S(b+1); out = T(out); }else{ out = b; } return out; int L(int b){ int out; out = S(b); out = T(out); return out; }
H7 引入标记非终极符M,N,R,P 产生式 语义规则 栈操作代码 S’ → MS S.in = M.out 4.12(b) 文法如下： S’ → S S → (L) S → a L → ST T → ,ST | 𝜀 写出自下而上分析的栈操作代码 H7 引入标记非终极符M,N,R,P 产生式 语义规则 栈操作代码 S’ → MS S.in = M.out Stack[top - 1] = Stack[top] M → 𝜀 M.out = 0 Stack[top + 1] = 0 S → (NL) N.in = S.in + 1, L.in = N.out; S.out = L.out + 1; Stack[top - 3] = Stack[top - 1] + 1 N → 𝜀 N.out = N.in Stack[top + 1] = Stack[top - 1] + 1 S → a S.out = S.in + 1; print (S.out); Stack[top] = Stack[top - 1] + 1 L → SRT S.in = L.in; R.in = S.in; T.in = R.out, L.out = T.out; Stack[top - 2] = Stack[top] R → 𝜀 R.out = R.in Stack[top + 1] = Stack[top - 1] T → ,SPT1 S.in = T.in + 1; P.in = S.in; T1.in = P.out; T1.out = S.out; Stack[top - 3] = Stack[top] P → 𝜀 P.out = P.in Stack[top + 1] = Stack[top] T → 𝜀 T.out = T.in Stack[top] = Stack[top - 1]
H8 5.5 假如有下列C的声明: typedef struct{ int a, b; } CELL, *PCELL; CELL foo[100]; PCELL bar(x, y) int x; CELL y; {} 为变量foo和函数bar的类型写出类型表达式。
H8 CELL foo[100]; array(Range ?, TypeOfElement ?) typedef struct{ int a, b; } CELL, *PCELL; CELL foo[100]; PCELL bar(x, y) int x; CELL y; {} 为变量foo和函数bar的类型写出类型表达式。 CELL foo[100]; array(Range ?, TypeOfElement ?) array(0..99, TypeOfElement ?) array(0..99, CELL) array(0..99, record((int a) ×(int b))) array(0..99, record((a × integer) ×(b × integer)))
H8 PCELL bar(x, y) int x; CELL y; {} typedef struct{ int a, b; } CELL, *PCELL; CELL foo[100]; PCELL bar(x, y) int x; CELL y; {} 为变量foo和函数bar的类型写出类型表达式。 PCELL bar(x, y) int x; CELL y; {} TypeOfParameters? -> TypeOfReturnValue? (int ×CELL) -> PCELL (integer ×record((a × integer) ×(b × integer))) -> PCELL (integer ×record((a × integer) ×(b × integer))) -> pointer(record((a × integer) ×(b × integer)))
H8 5.12 拓展5.3.3节的类型检查，使之能包含记录。有关记录部分的 类型和记录域引用表达式的语法如下： T→ 𝒓𝒆𝒄𝒐𝒓𝒅 𝑓𝑖𝑒𝑙𝑑𝑠 𝐞𝐧𝐝 𝑓𝑖𝑒𝑙𝑑𝑠→ 𝑓𝑖𝑒𝑙𝑑𝑠;𝑓𝑖𝑒𝑙𝑑 | 𝑓𝑖𝑒𝑙𝑑 𝑓𝑖𝑒𝑙𝑑→𝐢𝐝 :𝑇 𝐸→𝐸.𝐢𝐝
H8 5.12 拓展5.3.3节的类型检查，使之能包含记录。有关记录部分的 类型和记录域引用表达式的语法如下： T→ 𝒓𝒆𝒄𝒐𝒓𝒅 𝑓𝑖𝑒𝑙𝑑𝑠 𝐞𝐧𝐝 {T.type = record(fields.type)} 𝑓𝑖𝑒𝑙𝑑𝑠→ 𝑓𝑖𝑒𝑙𝑑𝑠;𝑓𝑖𝑒𝑙𝑑 {fields.type = fields.type × field.type} 𝑓𝑖𝑒𝑙𝑑𝑠→ 𝑓𝑖𝑒𝑙𝑑 {fields.type = field.type} 𝑓𝑖𝑒𝑙𝑑→𝐢𝐝 :𝑇 {field.type = id.name × T.type} 𝐸→ 𝐸 1 .𝐢𝐝 {E.type = if(E1.type == record(t)) lookup(E1.type, id.name) else type_error;}
H8 5.13在文件stdlib.h中，关于qsort的外 部声明如下： #include <stdlib.h> typedef struct{ int Ave; double Prob; }HYPO; HYPO astHypo; int n; int HypoCompare(HYPO stHypo1, HYPO stHypo2) { if (stHypo1->Prob>stHypo2->Prob){ return(-1); }else if (stHypo1->Prob<stHypo2->Prob) { return(1); }else{ return(0); } }/ end of function HypoCompare / main() qsort ( astHypo,n,sizeof(HYPO),HypoCompare); H8 5.13在文件stdlib.h中，关于qsort的外 部声明如下： extern void qsort(void *, size_t, size_t, int (*)(const void *, const void *)); 用SPARC/Solaris C编译器编译下面的C 程序时，错误信息如下： type.c:24: warning: passing argument 4 of `qsort’ from incompatible pointer type 请你对该程序略作修改，使得该警告 错误能消失，并且不改变程序的结果。
H8 5.13在文件stdlib.h中，关于qsort的外 部声明如下： #include <stdlib.h> typedef struct{ int Ave; double Prob; }HYPO; HYPO astHypo; int n; int HypoCompare(HYPO stHypo1, HYPO stHypo2) { if (stHypo1->Prob>stHypo2->Prob){ return(-1); }else if (stHypo1->Prob<stHypo2->Prob) { return(1); }else{ return(0); } }/ end of function HypoCompare / main() qsort ( astHypo, n, sizeof(HYPO), HypoCompare); H8 5.13在文件stdlib.h中，关于qsort的外 部声明如下： extern void qsort(void *, size_t, size_t, int (*)(const void *, const void *)); 问题：qsort的第四个形式参数类型与 函数调用的传参类型不一致
H8 5.13在文件stdlib.h中，关于qsort的外 部声明如下： #include <stdlib.h> typedef struct{ int Ave; double Prob; }HYPO; HYPO astHypo; int n; int HypoCompare(const void stHypo1, const voidstHypo2) { if ((HYPO *)stHypo1->Prob>(HYPO *)stHypo2->Prob){ return(-1); }else if ((HYPO *)stHypo1->Prob<(HYPO *)stHypo2->Prob) { return(1); }else{ return(0); } }/ end of function HypoCompare / main() qsort ( astHypo, n, sizeof(HYPO), HypoCompare); H8 5.13在文件stdlib.h中，关于qsort的外 部声明如下： extern void qsort(void *, size_t, size_t, int (*)(const void *, const void *)); 问题：qsort的第四个形式参数类型与 函数调用的传参类型不一致 方法一：修改HypoCompare函数形式参 数的类型
H8 5.13在文件stdlib.h中，关于qsort的外 部声明如下： #include <stdlib.h> typedef struct{ int Ave; double Prob; }HYPO; HYPO astHypo; int n; int HypoCompare(HYPO stHypo1, HYPO stHypo2) { if (stHypo1->Prob>stHypo2->Prob){ return(-1); }else if (stHypo1->Prob<stHypo2->Prob) { return(1); }else{ return(0); } }/ end of function HypoCompare / main() qsort ( astHypo, n, sizeof(HYPO), int (*)(const void *, const void *) HypoCompare); H8 5.13在文件stdlib.h中，关于qsort的外 部声明如下： extern void qsort(void *, size_t, size_t, int (*)(const void *, const void *)); 问题：qsort的第四个形式参数类型与 函数调用的传参类型不一致 方法二：强制修改qsort函数调用中第 四个参数的类型
H9 5.16对下面的每对表达式， (a) 1 (2 1) 5.16对下面的每对表达式， (a) 1 (2 1) (b) array (1) (pointer (1) 2) (c) 1 2 找出(a) 和 (b) 、(b)和(c)最一般的合一代换：
H9 (a)与(b) S(α1) = array ( β1 ) S(α2) = pointer ( β1 ) 5.16对下面的每对表达式， (a) 1 (2 1) (b) array (1) (pointer (1) 2) (c) 1 2 找出(a) 和 (b) 、(b)和(c)最一般的合一代换： (a)与(b) S(α1) = array ( β1 ) S(α2) = pointer ( β1 ) S(β2) = array ( β1 ) 什么是最一般的合一代换
H9 (b)与(c) S(γ1) = array ( β1 ) S(γ2) = pointer ( β1 ) → β2 5.16对下面的每对表达式， (a) 1 (2 1) (b) array (1) (pointer (1) 2) (c) 1 2 找出(a) 和 (b) 、(b)和(c)最一般的合一代换： (b)与(c) S(γ1) = array ( β1 ) S(γ2) = pointer ( β1 ) → β2
H9 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 ( ) ;
H9 第一步：列出类型声明和要检查的表达式 f : α l : β 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 ( ) ; H9 第一步：列出类型声明和要检查的表达式 f : α l : β if: . boolean list ( ) list ( ) list ( ) null : . list ( ) boolean ; nil : . list ( ) ; cons : . ( list ( ) ) list ( ) ; hd : . list ( ) ; tl : . list ( ) list ( ) ; match( map ( f, l ), if null (l ) then nil else cons (f (hd (l)), map (f, tl (l ) ) ); )
map : . . ( ( ) list ( ) ) list ( ) 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 ( ) ; H9 第二步：代换推导 行 定型断言 代换 规则 1 f : α (Exp Id) 2 l : β 3 map : γ 4 map ( f , l ) : δ γ = ( α β ) → δ (Exp Funcall) 5 null : list (α0) → boolean (Exp Id Fresh) 6 null ( l ) : boolean β = list (α0) (Exp Funcall + (2)) 7 nil : list (α1) 8 l : list (α0) 由（2）可得 9 hd : list (α2) → α2 ML ('Meta Language') is a general-purpose functional programming language.
H9 第二步：代换推导 至此有map : ( (α0→α1) list(α0) )→list(α1) map : . . ( ( ) list ( ) ) list ( ) 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 ( ) ; H9 行 定型断言 代换 规则 9 hd : list (α2) → α2 (Exp Id 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) 14 tl ( l ) : list (α0) α4 = α0 15 map : ((α0→α3) list(α0))→ δ 由（3）可得 16 map ( f , tl ( l ) ) : δ 17 cons : α5 list(α5) → list(α5) 18 cons (…) : list (α3) α5 = α3 , δ=list(α3) 19 if : boolean list(α6) list(α6) →list(α6) 20 if (…) : list (α1) α6 = α1 , α3 = α1 21 match : α7 α7 → α7 22 match (…) : list (α1) α7 = list (α1) 第二步：代换推导 ML ('Meta Language') is a general-purpose functional programming language. 至此有map : ( (α0→α1) list(α0) )→list(α1) 所以map : ∀ α . ∀ β . ( ( α → β ) list ( α ) ) → list ( β )
H9 5.21 使用例5.9的规则，确定下列哪些表达式有唯一类型（假定z 是复数）： (a) 123 (b) 1 (z 2) (c) (1 z ) z
H9 5.21 使用例5.9的规则，确定下列哪些表达式有唯一类型（假定z 是复数）： (a) 123 (b) 1 (z 2) (c) (1 z ) z 运算规则： int int -> int int int -> complex complex complex -> complex
H9 5.21 使用例5.9的规则，确定下列哪些 表达式有唯一类型（假定z是复数）： (a) 123 (b) 1 (z 2) (c) (1 z ) z 运算规则： int int -> int int int -> complex complex complex -> complex H9 1*2*3:{int, complex} 1*2:{int, complex} *: {i i -> i, i i -> c, c c -> c} 3:{int, complex} 1:{int, complex} 2:{int, complex} 类型不唯一 *: {i i -> i, i i -> c, c c -> c}
H9 5.21 使用例5.9的规则，确定下列哪些 表达式有唯一类型（假定z是复数）： (a) 123 (b) 1 (z 2) (c) (1 z ) z 运算规则： int int -> int int int -> complex complex complex -> complex H9 1 (z 2) :{complex} 1:{int} *: {i i -> i, i i -> c, c c -> c} z*2:{complex} z:{complex} *: {i X i -> i, i X i -> c, c X c -> c} 2:{int, complex} 类型唯一
H9 5.21 使用例5.9的规则，确定下列哪些 表达式有唯一类型（假定z是复数）： (a) 123 (b) 1 (z 2) (c) (1 z ) z 运算规则： int int -> int int int -> complex complex complex -> complex H9 (1 z ) z:{complex} 1*z:{complex} *: {i i -> i, i i -> c, c c -> c} z:{complex} 1:{int, complex} *: {i i -> i, i i -> c, c c -> c} z:{complex} 类型唯一