语义分析和中间代码生成.ppt

1、第七章 语义分析和中间代码生成,本章内容 介绍几种常用的中间表示：后缀表示、图形表示和三地址代码 用语法制导定义和翻译方案的方法来说明程序设计语言的结构怎样被翻译成中间形式,7.1 中 间 语 言,7.1.1 后缀式 表达式E的后缀式可以如下递归定义 如果E是变量或常数，那么E的后缀式就是E本身,7.1 中 间 语 言,7.1.1 后缀表示 表达式E的后缀表示可以如下递归定义 如果E是变量或常数，那么E的后缀表示就是E本身。 如果E是形式为E1 opE2的表达式，那么E的后缀式是E1 E2 op，其中E1和E2分别是E1和E2的后缀式,7.1 中 间 语 言,7.1.1 后缀式 表达式E的后缀

2、式可以如下递归定义 如果E是变量或常数，那么E的后缀式就是E本身。 如果E是形式为E1 opE2的表达式，那么E的后缀式是E1 E2 op，其中E1和E2分别是E1和E2的后缀式。 如果E是形式为(E1)的表达式，那么E1的后缀表示也是E的后缀式,7.1 中 间 语 言,后缀式表示法是波兰逻辑学家卢卡西维奇（Lukasiewicz）发明的一种表示表达式的方法因此又称逆波兰表示法。这种表示法是把运算量（操作数）写在前面把算符写在后面（后缀,7.1 中 间 语 言,把表达式翻译为后缀式的语义规则描述 产 生 式 语 义 规 则 EE1op E2 E.code :E1.code | E2.code

3、| op E（E1） Ecode := E1.code Eid Ecode :id,7.1 中 间 语 言,后缀式不需要括号 (8 4) + 2 的后缀表示是8 4 2 + 后缀式的最大优点是便于计算机处理表达式 后缀式很容易拓广到含一元算符的表达式 后缀式也可以拓广到表示赋值语句和控制语句，但很难用栈来描述它的计算,7.1 中 间 语 言,7.1.2 图形表示 图表示法包括DAG与抽象语法树 语法树是一种图形化的中间表示,7.1 中 间 语 言,7.1.2 图形表示 语法树是一种图形化的中间表示 有向无环图也是一种中间表示,7.1 中 间 语 言,构造赋值语句语法树的语法制导定义,7.1 中

4、 间 语 言,7.1.3 三地址代码 一般形式：x := y op z 表达式x + y z翻译成的三地址语句序列是 t1 := y z t2 := x + t1,7.1 中 间 语 言,三地址代码是语法树或DAG的一种线性表示 a := (b + cd ) + cd 语法树的代码DAG的代码 t1 := bt1 := b t2 := c dt2 := c d t3 := t1 + t2t3 := t1 + t2 t4 := c dt4 := t3 + t2 t5 := t3 + t4 a := t4 a := t5,7.1 中 间 语 言,本书常用的三地址语句 赋值语句x := y op z

5、， x := op y， x := y 无条件转移goto L 条件转移if x relop y goto L 过程调用param x 和call p , n 过程返回 return y 索引赋值x := yi和 xi := y 地址和指针赋值x := D D id : T enter ( , T.type, offset); offset := offset + T.width T integer T.type := integer; T.width := 4 T real T.type := real; T.width := 8 T array num of T1 T.typ

6、e := array (num.val, T1.type); T.width := num.val T1.width T T1 T.type := pointer (T1.type); T.width := 4,7.2 说 明 语 句,7.2.2 作用域信息的保存 所讨论语言的文法 P D S D D ; D | id : T | proc id ; D ; S 语义动作用到的函数 mktable(previous) enter(table, name, type, offset) addwidth(table, width) enterproc(table, name, newtable,7

7、.2 说 明 语 句,处理嵌套过程中的说明语句 P M D addwidth (top (tblptr), top (offset) ); pop(tblptr); pop (offset) M t := mktable (nil); push(t, tblprt); push (0, offset) D D1 ; D2 D proc id ; N D1; S t := top(tblptr); addwidth(t, top(offset) ); pop(tblptr); pop(offset); enterproc(top(tblptr), , t ) Did : T ent

8、er(top(tblptr), , T.type, top(offset); top(offset) := top(offset) + T.width N t := mktable(top(tblptr) ); push(t, tblptr); push(0, offset),1） program sort(input,output) （2） var a: array0.10 of integer; （3） x: integer; （4） procedure readarray （5） var i: integer; （6） beginaendreadarray （7） proc

9、edure exchange(i,j:integer); （8） begin （9） x:=ai; ai:=aj; aj:=x （10） end exchange; （11） procedure quicksort(m,n;integer); （12） var k,v: integer; （13） function partition(y,z:integer):integer; （14） var i,j: integer; （15） begina （16） v （17） exchange(i,j); （18） end partition; （19） begin end quicksort; （

10、20） beginend sort,7.2 说 明 语 句,7.2 说 明 语 句,7.2.3 记录的域名 T record D end T record L D end T.type := record (top(tblptr) ); T.width := top(offset); pop(tblptr); pop(offset) L t := mktable (nil); push(t, tblprt); push(0, offset),7.3 赋 值 语 句,7.3.1 简单算术表达式及赋值语句 S id := E p := lookup(); if p nil then

11、emit ( p，:=, E.place) else error E E1 + E2 E.place := newtemp; emit (E.place, :=, E1.place, +, E2.place),7.3 赋 值 语 句,7.3.1 简单算术表达式及赋值语句 E E1 E.place := newtemp; emit (E.place, :=, uminus, E1.place) E (E1) E.place := E1.place E id p := lookup(); if p nil then E.place := p else error,7.3 赋 值 语

12、句,7.3.2数组元素的地址计算 一维数组A的第i个元素的地址计算 base + ( i low ) w,7.3 赋 值 语 句,7.3.3 数组元素的地址计算 一维数组A的第i个元素的地址计算 base + ( i low ) w 重写成 i w + (base low w,7.3 赋 值 语 句,二维数组 列为主 A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 3,7.3 赋 值 语 句,二维数组 列为主 A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 3 行为主 A1, 1, A1, 2, A1, 3, A2, 1, A2, 2

13、, A2, 3,7.3 赋 值 语 句,二维数组 列为主 A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 3 行为主 A1, 1, A1, 2, A1, 3, A2, 1, A2, 2, A2, 3 base + ( (i1 low1) n2 + (i2 low2 ) ) w （其中n2 = high2 low2 + 1,7.3 赋 值 语 句,二维数组 列为主 A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 3 行为主 A1, 1, A1, 2, A1, 3, A2, 1, A2, 2, A2, 3 base + ( (i1 low

14、1) n2 + (i2 low2 ) ) w （其中n2 = high2 low2 + 1） ( (i1 n2 ) + i2 ) w + (base ( (low1 n2 ) + low2 ) w,7.3 赋 值 语 句,多维数组 Ai1, i2, ., ik 的地址表达式 ( ( ( (i1 n2 + i2 ) n3 + i3 ) ) nk + ik) w + base ( ( ( (low1 n2 + low2) n3 + low3) ) nk + lowk ) w,7.3 赋 值 语 句,7.3.4 数组元素地址计算的翻译方案 下标变量访问的产生式 L id Elist | id Eli

15、st Elist, E | E 改成 L Elist | id Elist Elist, E | id E,7.3 赋 值 语 句,所有产生式 S L := E E E + E E (E ) E L L Elist L id Elist Elist, E Elist id E,7.3 赋 值 语 句,L id L.place := id.place; L.offset := null,7.3 赋 值 语 句,L id L.place := id.place; L.offset := null Elist id E Elist.place := E.place; Elist.ndim := 1;

16、 Elist.array := id.place,7.3 赋 值 语 句,L id L.place := id.place; L.offset := null Elist id E Elist.place := E.place; Elist.ndim := 1; Elist.array := id.place Elist Elist1, E t := newtemp; m := Elist1.ndim + 1; emit (t, :=, Elist1.place, , limit(Elist1.array, m) ); emit (t, :=, t, +, E.place); Elist.ar

17、ray := Elist1.array; Elist.place := t; Elist.ndim := m,7.3 赋 值 语 句,L id L.place := id.place; L.offset := null Elist id E Elist.place := E.place; Elist.ndim := 1; Elist.array := id.place Elist Elist1, E t := newtemp; m := Elist1.ndim + 1; emit (t, :=, Elist1.place, , limit(Elist1.array, m) ); emit (t

18、, :=, t, +, E.place); Elist.array := Elist1.array; Elist.place := t; Elist.ndim := m L Elist L.place := newtemp; emit(L.place,:=,base(Elist.array),C); /*C= invariant (Elist.array)*/ L.offset := newtemp; emit (L.offset, :=, Elist.place, , w),7.3 赋 值 语 句,E L if L.offset = null then / L是简单变量 / E.place

19、:= L.place else begin E.place := newtemp; emit (E.place, :=, L.place, , L.offset, ) end,7.3 赋 值 语 句,E Lif L.offset = null then / L是简单变量 / E.place := L.place else begin E.place := newtemp; emit (E.place, :=, L.place, , L.offset, ) end E E1 + E2E.place := newtemp; emit (E.place, :=, E1.place , +, E2.p

20、lace),7.3 赋 值 语 句,E Lif L.offset = null then / L是简单变量 / E.place := L.place else begin E.place := newtemp; emit (E.place, :=, L.place, , L.offset, ) end E E1 + E2E.place := newtemp; emit (E.place, :=, E1.place , +, E2.place) E (E1 )E.place := E1.place,7.3 赋 值 语 句,E Lif L.offset = null then / L是简单变量 /

21、 E.place := L.place else begin E.place := newtemp; emit (E.place, :=, L.place, , L.offset, ) end E E1 + E2E.place := newtemp; emit (E.place, :=, E1.place , +, E2.place) E (E1 )E.place := E1.place S L := Eif L.offset = null then / L是简单变量 / emit (L.place, := , E.place) else emit (L.place , , L.offset,

22、 , :=, E.place),7.3 赋 值 语 句,7.3 赋 值 语 句,t1 := y 20 t1 := t1 + z,7.3 赋 值 语 句,t1 := y 20 t1 := t1 + z,t2 :=A 84 t3 := 4 t1,7.3 赋 值 语 句,t1 := y 20 t1 := t1 + z,t2 :=A 84 t3 := 4 t1,t4 := t2 t3,7.3 赋 值 语 句,t1 := y 20 t1 := t1 + z,t2 :=A 84 t3 := 4 t1,t4 := t2 t3,x := t4,7.3 赋 值 语 句,7.3.5 类型转换 x := y + i

23、 j （x和y的类型是real，i和j的类型是integer） 中间代码 t1 := i int j t2 := inttoreal t1 t3 := y real+ t2 x := t3,7.3 赋 值 语 句,E E1 + E2 E.place := newtemp if E1.type = integer and E2.type = integer then begin emit (E.place, :=, E1.place, int+, E2.place); E.type = integer end else if E1.type = integer and E2.type = rea

24、l then begin u := newtemp; emit (u, :=, inttoreal, E1.place); emit (E.place, :=, u, real+, E2.place); E.type := real end . .,7.4 布尔表达式的翻译,布尔表达式有两个基本目的 计算逻辑值 在控制流语句中用作条件表达式,7.4 布尔表达式的翻译,布尔表达式有两个基本目的 计算逻辑值 在控制流语句中用作条件表达式 布尔表达式的完全计算 布尔表达式的“短路”计算 E1 or E2 定义成 if E1 then true else E2 E1 and E2 定义成 if E1

25、then E2 else false,7.4 布尔表达式的翻译,7.4.1 布尔表达式的翻译 E E or E | E and E | not E | ( E ) | id relop id | true | false a b的翻译 100: if a b goto 103 101: t := 0 102: goto 104 103: t := 1 104,7.4 布尔表达式的翻译,E E1 or E2 E.place := newtemp; emit (E.place, :=, E1.place, or E2.place) E id1 relop id2 E.place := newtem

26、p; emit (if, id1.place, relop.op, id2.place, goto, nextstat+3 ); emit (E.place, :=, 0 ); emit (goto, nextstat + 2 ); emit (E.place, :=, 1 ),7.4 布尔表达式的翻译,表达式 a b or c d and e f 的代码是： 100 if a b goto 103 107 T2 :=1 101 T1 :=0 108 if e f goto 111 102 goto 104 109 T3:=0 103 T1 :=1 110 goto 112 104 if c

27、d goto 107 111 T3:=1 105 T2 :=0 112 T4:= T2 and T3 106 goto 108 113 T5:= T1 or T4,7.4 布尔表达式的翻译,E E1 or E2 E1.true := E.true; E1.false := newlabel; E2.true := E.true; E2.false := E.false; E.code := E1.code | gen(E1.false, :) | E2.code,7.4 布尔表达式的翻译,E E1 or E2 E1.true := E.true; E1.false := newlabel; E

28、2.true := E.true; E2.false := E.false; E.code := E1.code | gen(E1.false, :) | E2.code E not E1 E1.true := E.false; E1.false := E.true; E.code := E1.code,7.4 布尔表达式的翻译,E E1 and E2 E1.true := newlabel; E1.false := E.false; E2.true := E.true; E2.false := E.false; E.code := E1.code | gen(E1.true, :) | E2

29、.code,7.4 布尔表达式的翻译,E E1 and E2 E1.true := newlabel; E1.false := E.false; E2.true := E.true; E2.false := E.false; E.code := E1.code | gen(E1.true, :) | E2.code E (E1 ) E1.true := E.true; E1.false := E.false; E.code := E1.code,7.4 布尔表达式的翻译,E id1 relop id2 E.code := gen(if, id1.place, relop.op, id2.pla

30、ce, goto, E.true) | gen(goto, E.false),7.4 布尔表达式的翻译,E id1 relop id2 E.code := gen(if, id1.place, relop.op, id2.place, goto, E.true) | gen(goto, E.false) E true E.code := gen(goto, E.true) E false E.code := gen(goto, E.false,7. 5 控制语句的翻译,7.5.1 控制流语句的翻译 S if E then S1 | if E then S1 else S2 | while E

31、do S1 | S1; S2,7. 5 控制语句的翻译,7. 5 控制语句的翻译,S if E then S1 E.true := newlabel; E.false := S.next; S1.next := S.next; S.code := E.code | gen(E.true, :) | S1.code,7. 5 控制语句的翻译,S if E then S1 else S2 E.true := newlabel; E.false := newlabel; S1.next := S.next; S2.next := S.next; S.code := E.code | gen(E.tr

32、ue, :) | S1.code | gen(goto, S.next) | gen(E.false, :) | S2.code,7. 5 控制语句的翻译,S while E do S1 S.begin:= newlabel; E.true := newlabel; E.false := S.next; S1.next := S.begin; S.code := gen(S.begin, :) | E.code | gen(E.true, :) | S1.code | gen(goto, S.begin),7. 5 控制语句的翻译,S S1; S2 S1.next := newlabel; S

33、2.next := S.next; S.code := S1.code | gen(S1.next, :) | S2.code,while ab do if cd then x:=y+z else x:= y-z 根据上述属性文法和赋值语句的翻译模式，将生成下列代码,L1: if ab goto L2 goto Lnext L2: if cd goto L3 goto L4 L3: T1 :=y+z x:=T1 goto L1 L4: T1:=y-z x:= T2 goto L1 Lnext,100 (j, a, b, 102) while ab do 101 (j, -, -, 107) i

34、f cd then 102 (j, c, d,104) x:=y+z 103 (j, -, -, 100) 104 (+, y, z, T) 105 (:=, T, -, x) 106 (j, -, -, 100) 107,7. 5 控制语句的翻译,7.5.2 布尔表达式的控制流翻译 如果E是a b的形式， 那么代码是： if a b goto E.true goto E.false,7. 5 控制语句的翻译,7.5.3 开关语句的翻译 switch E begin case V1: S1 case V2: S2 . . . case Vn - 1: Sn 1 default: Sn end,

35、7. 5 控制语句的翻译,分支数较少时 t := E的代码 | Ln-2: if t Vn-1 goto Ln-1 if t V1 goto L1 | Sn -1的代码 S1的代码 | goto next goto next | Ln-1: Sn的代码 L1:if t V2 goto L2 | next: S2的代码 goto next L2:. . . . .,7. 5 控制语句的翻译,分支较多时，将分支测试的代码集中在一起， 便于生成较好的分支测试代码。 t := E的代码| Ln:Sn的代码 goto test | goto next L1:S1的代码 |test: if t = V1

36、goto L1 goto next| if t = V2 goto L2 L2:S2的代码 | . . . goto next|if t = Vn-1 goto Ln-1 . . . |goto Ln Ln-1:Sn -1的代码| next: goto next,7. 5 控制语句的翻译,中间代码增加一种case语句，便于代码生成器 对它进行特别处理 test:case V1 L1 case V2 L2 . . . case Vn-1 Ln-1 case t Ln next,7.6 过程调用的处理,过程调用的翻译 S call id (Elist) for 队列queue中的每一项p do e

37、mit（param p）； emit （callid.Place） Elist Elist, E 将E.Place加入到queeue的队尾 Elist E 初始化queue仅包含E.place,7.4 布尔表达式和控制流语句,过程调用id(E1, E2, , En)的中间代码结构 E1.place := E1的代码 E2.place := E2的代码 . . . En.place := En的代码 param E1.place param E2.place . . . param En.place call id.place, n,7.4 布尔表达式和控制流语句,S call id (Elis

38、t) 为长度为n的队列中的每个E.place， emit(param, E.place); emit(call, id.plase, n) Elist Elist, E 把E.place放入队列末尾 Elist E 将队列初始化，并让它仅含E.place,7.7 类型检查,静态检查中最典型的部分 类型检查： 类型系统、类型检查、多态函数、重载。 忽略其它的静态检查：控制流检查、唯一性检查 、关联名字检查,7.7.1 类型系统 变量的类型 变量在程序执行期间的取值范围 类型化语言 变量都被给定类型的语言 未类型化的语言 不限制变量值范围的语言 一个运算可以作用到任意的运算对象，其结果可能是一个有

39、意义的值、一个错误、一个异常或一个未做说明的结果,类型系统的根本目的是防止程序运行时出现执行错误 类型可靠的语言 粗略地说，所有程序运行时都没有执行错误出现 类型系统的形式化 类型表达式、定型断言、定型规则、类型检查算法 显式类型化的语言 类型是语法的一部分 隐式类型化的语言, 执行错误和安全语言 执行错误 会被捕获的错误（trapped error） 例：非法指令错误、非法内存访问、除数为零 引起计算立即停止 不会被捕获的错误（untrapped error） 例：下标变量的访问越过数组末端的数据 例：跳到一个错误的地址，该地址开始的内存正好代表一个指令序列,类型可靠的语言 所

40、有合法的程序都是良行为的 又称为强检查的语言 未类型化语言通过彻底的运行时详细检查来排除所有的禁止错误，如LISP语言 也可以通过静态检查来拒绝不良行为的程序 类型系统就是用来支持这种静态检查的 这种检查叫做类型检查 这样的类型化语言，又称强类型化的语言,一些实际使用的语言是弱类型化语言 Pascal语言 无标志的变体记录类型 函数型参数,一些实际使用的语言是弱类型化语言 Pascal语言 无标志的变体记录类型 函数型参数 C语言 有很多不安全的并且被广泛使用的特征，如： 指针算术运算 类型强制 参数个数可变,在语言设计的历史上，安全性考虑不足是出于效率上的原因,在语言设计的历史上，安全性考虑

41、不足是出于效率上的原因 在语言设计中的，安全性的位置越来越重要 C的一些问题已经在C+中得以缓和 更多一些问题在Java中已得到解决 ML是一个类型化的安全语言, 类型化语言的优点 从工程的观点看，类型化语言有下面一些优点 开发的实惠 较早发现错误 类型信息还具有文档作用, 类型化语言的优点 从工程的观点看，类型化语言有下面一些优点 开发的实惠 较早发现错误 类型信息还具有文档作用 编译的实惠 程序模块可以相互独立地编译, 类型化语言的优点 从工程的观点看，类型化语言有下面一些优点 开发的实惠 较早发现错误 类型信息还具有文档作用 编译的实惠 程序模块

42、可以相互独立地编译 运行的实惠 可得到更有效的空间安排和访问方式,7.7.2 类型检查器的规格说明,一个简单的语言 P D ; S D D ; D | id : T T boolean | integer | array num of T | T | T T S id := E | if E then S | while E do S | S ; S E truth | num | id | E mod E | E E | E | E (E,7.7.2 类型检查器的规格说明,类型检查声明语句 D D; D D id : T addtype (id.entry, T.type) T boolea

43、n T.type := boolean T integer T.type := integer T T1 T.type := pointer(T1.type,7.7.2 类型检查器的规格说明,类型检查声明语句 D D; D D id : T addtype (id.entry, T.type) T boolean T.type := boolean T integer T.type := integer T T1 T.type := pointer(T1.type) T array num of T1 T.type := array(num.val, T1.type,7.7.2 类型检查器的规

44、格说明,类型检查声明语句 D D; D D id : T addtype (id.entry, T.type) T boolean T.type := boolean T integer T.type := integer T T1 T.type := pointer(T1.type) T array num of T1 T.type := array(num.val, T1.type) T T1 T2 T.type := T1.type T2.type,7.7.2 类型检查器的规格说明,类型表达式的抽象语法 基本类型 boolean, char, integer, real 构造类型 数组类

45、型array(I, T) 指针类型pointer(T) 积类型T1 T2 函数 T1 T2 记录（例）record(address integer) (lexeme array(1.10, char) 类型表达式中还可以出现类型名字和类型变量,7.7.2 类型检查器的规格说明,类型检查表达式 E truthE.type := boolean E numE.type := integer E idE.type := lookup(id.entry,7.7.2 类型检查器的规格说明,类型检查表达式 E truthE.type := boolean E numE.type := integer E

46、idE.type := lookup(id.entry) E E1 mod E2 E.type := if E1.type = integer and E2. type = integer then integer else type_error,7.7.2 类型检查器的规格说明,类型检查表达式 E E1 E2 E.type := if E2. type = integer and E1. type = array(s, t) then t else type_error,7.7.2 类型检查器的规格说明,类型检查表达式 E E1 E2 E.type := if E2. type = inte

47、ger and E1. type = array(s, t) then t else type_error E E1 E.type := if E1.type = pointer(t) then t else type_error,7.7.2 类型检查器的规格说明,类型检查表达式 E E1 E2 E.type := if E2. type = integer and E1. type = array(s, t) then t else type_error E E1 E.type := if E1.type = pointer(t) then t else type_error E E1 (E

48、2 ) E. type := if E2 . type = s and E1. type = s t then t else type_error,7.7.2 类型检查器的规格说明,类型检查语句 S id := E S. type := if id. type = E. type then void else type_error,7.7.2 类型检查器的规格说明,类型检查语句 S id := E S. type := if id. type = E. type then void else type_error S if E then S1 S. type := if E. type = b

49、oolean then S1. type else type_error,7.7.2 类型检查器的规格说明,类型检查语句 S while E do S1 S.type := if E.type = boolean then S1. type else type_error,7.7.2 类型检查器的规格说明,类型检查语句 S while E do S1 S.type := if E.type = boolean then S1. type else type_error S S1; S2 S. type := if S1. type = void and S2. type = void then

50、 void else type_error,7.7.2 类型检查器的规格说明,类型检查程序 P D; S P. type := if S. type = void then void else type_error,7.7.2 类型检查器的规格说明,类型转换 E E1 op E2 E.type := if E1.type = integer and E2.type = integer then integer else if E1.type = integer and E2.type = real then real else if E1.type = real and E2.type = i

51、nteger then real else if E1.type = real and E2.type = real then real else type_error,7.7.3 多态函数, 为什么要使用多态函数 例：用Pascal语言写不出求表长度的通用程序 type link = cell ; cell = record info : integer; next : link end,7.7.3 多 态 函 数,function length(lptr : link) : integer; var len : integer; begin len := 0; while l

52、ptr nil do begin len := len + 1; lptr := lptr. next end; length := len end,7.7.3 多 态 函 数,用ML语言很容易写出求表长度的程序而不必管表元的类型。 fun length (lptr) = if null (lptr) then 0 else length (tl (lptr) + 1,7.7.3 多 态 函 数,用ML语言很容易写出求表长度的程序而不必管表元的类型。 fun length (lptr) = if null (lptr) then 0 else length (tl (lptr) + 1; le

53、ngth ( “sun”, “mon”, “tue” ) length ( 10, 9, 8 ) 都等于3,7.7.3 多 态 函 数,多态函数 允许变元有不同的类型,7.7.3 多 态 函 数,多态函数 允许变元有不同的类型 体中的语句可以在变元类型不同的情况下执行（区别于重载的特征,7.7.3 多 态 函 数,多态函数 允许变元有不同的类型 体中的语句可以在变元类型不同的情况下执行（区别于重载的特征） 多态算符 用于以不同类型的变元执行的代码段,7.7.3 多 态 函 数,多态函数 允许变元有不同的类型 体中的语句可以在变元类型不同的情况下执行（区别于重载的特征） 多态算符 用于以不同类型

54、的变元执行的代码段 例如：数组索引,7.7.3 多 态 函 数,多态函数 允许变元有不同的类型 体中的语句可以在变元类型不同的情况下执行（区别于重载的特征） 多态算符 用于以不同类型的变元执行的代码段 例如：数组索引、函数作用,7.7.3 多 态 函 数,多态函数 允许变元有不同的类型 体中的语句可以在变元类型不同的情况下执行（区别于重载的特征） 多态算符 用于以不同类型的变元执行的代码段 例如：数组索引、函数作用、通过指针间接访问,7.7.3 多 态 函 数,多态函数 允许变元有不同的类型 体中的语句可以在变元类型不同的情况下执行（区别于重载的特征） 多态算符 用于以不同类型的变元执行的代码

55、段 例如：数组索引、函数作用、通过指针间接访问 C语言手册中关于指针 E - 引入类型变量、 D D; D | id : Q - 笛卡儿积类型、 Q type-variable. Q | T -多态函数 T T T | T T | unary-constructor ( T ) | basic-type | type-variable | ( T ) E E (E ) | E, E | id,7.7.3 多 态 函 数,代换、实例和合一 代换: 类型表达式中的类型变量用其所代表的类型表达式去替换,7.7.3 多 态 函 数,代换、实例和合一 代换: 类型表达式中的类型变量用其所代表的类型表达式

56、去替换 function subst (t : type_expression ) : type_expression; begin if t是基本类型 then return t else if t是类型变量then return S (t) else if t 是t1 t2 then return subst (t1) subst(t2) end,7.7.3 多 态 函 数,实例 把subst函数用于t后所得的类型表达式是t的一个实例，用S (t)表示。 例子（s t 表示s是t 的实例） pointer ( integer ) pointer ( ) pointer ( real ) p

57、ointer ( ) integer integer pointer ( ),7.7.3 多 态 函 数,下面左边的类型表达式不是右边的实例 integerreal 代换不能用于基本类型 integer real 的代换不一致 integer 的所有出现都应该代换,7.7.3 多 态 函 数,合一 如果存在某个代换S使得S (t1) = S (t2)，那么这两个表达式t1和t2能够合一 最一般的合一代换 S(t1) = S(t2)； 对任何其它满足S(t1) = S(t2)的代换S，代换S(t1)是S (t1)的实例,7.7.3 多 态 函 数,多态函数的类型检查 多态函数和普通函数在类型检查

58、上的区别 (1)同一多态函数的不同出现无须变元有相同类型,7.7.3 多 态 函 数,2)必须把类型相同的概念推广到类型合一,7.7.3 多 态 函 数,2)必须把类型相同的概念推广到类型合一 (3)要记录表达式合一的结果,7.7.3 多 态 函 数,检查多态函数的翻译方案 EE1 (E2 ) p := mkleaf (newtypevar); unify (E1. type, mknode ( , E2.type, p) ); E. type := p E E1, E2 E. type := mknode ( , E1.type , E2.type) E id E. type := fres

59、h (lookup(id.entry,7.7.3 多 态 函 数,7.7.3 多 态 函 数,确定表长度的ML函数 fun length (lptr) = if null (lptr) then 0 else length (tl (lptr) + 1,7.7.3 多 态 函 数,length : ; lptr : ; if : . boolean ; null : . list () boolean ; tl : . list () list () ; 0 : integer ; 1 : integer ; + : integer integer integer ; match : . ;

60、match ( length (lptr), if (null (lptr), 0, length (t1(lptr) +1),7.7.3 多 态 函 数,7.7.3 多 态 函 数,7.7.3 多 态 函 数,7.7.3 多 态 函 数,fun length (lptr) = if null (lptr) then 0 else length (tl (lptr) + 1; length函数的类型是 . list () integer,7.7.4 函数和运算符的重载,重载符号 有多个含义，但在引用点的含义都是唯一的 例如 加法算符+可用于不同类型，是不同的函数 在Ada中，( ) 是重载的，