語義分析和中間代碼生成.ppt

1、第七章 語義分析和中間代碼生成,本章內(nèi)容 介紹幾種常用的中間表示：后綴表示、圖形表示和三地址代碼 用語法制導(dǎo)定義和翻譯方案的方法來說明程序設(shè)計(jì)語言的結(jié)構(gòu)怎樣被翻譯成中間形式,7.1 中 間 語 言,7.1.1 后綴式 表達(dá)式E的后綴式可以如下遞歸定義 如果E是變量或常數(shù)，那么E的后綴式就是E本身,7.1 中 間 語 言,7.1.1 后綴表示 表達(dá)式E的后綴表示可以如下遞歸定義 如果E是變量或常數(shù)，那么E的后綴表示就是E本身。 如果E是形式為E1 opE2的表達(dá)式，那么E的后綴式是E1 E2 op，其中E1和E2分別是E1和E2的后綴式,7.1 中 間 語 言,7.1.1 后綴式 表達(dá)式E的后綴

2、式可以如下遞歸定義 如果E是變量或常數(shù)，那么E的后綴式就是E本身。 如果E是形式為E1 opE2的表達(dá)式，那么E的后綴式是E1 E2 op，其中E1和E2分別是E1和E2的后綴式。 如果E是形式為(E1)的表達(dá)式，那么E1的后綴表示也是E的后綴式,7.1 中 間 語 言,后綴式表示法是波蘭邏輯學(xué)家盧卡西維奇（Lukasiewicz）發(fā)明的一種表示表達(dá)式的方法因此又稱逆波蘭表示法。這種表示法是把運(yùn)算量（操作數(shù)）寫在前面把算符寫在后面（后綴,7.1 中 間 語 言,把表達(dá)式翻譯為后綴式的語義規(guī)則描述 產(chǎn) 生 式 語 義 規(guī) 則 EE1op E2 E.code :E1.code | E2.code

3、| op E（E1） Ecode := E1.code Eid Ecode :id,7.1 中 間 語 言,后綴式不需要括號(hào) (8 4) + 2 的后綴表示是8 4 2 + 后綴式的最大優(yōu)點(diǎn)是便于計(jì)算機(jī)處理表達(dá)式 后綴式很容易拓廣到含一元算符的表達(dá)式 后綴式也可以拓廣到表示賦值語句和控制語句，但很難用棧來描述它的計(jì)算,7.1 中 間 語 言,7.1.2 圖形表示 圖表示法包括DAG與抽象語法樹 語法樹是一種圖形化的中間表示,7.1 中 間 語 言,7.1.2 圖形表示 語法樹是一種圖形化的中間表示 有向無環(huán)圖也是一種中間表示,7.1 中 間 語 言,構(gòu)造賦值語句語法樹的語法制導(dǎo)定義,7.1 中

4、 間 語 言,7.1.3 三地址代碼 一般形式：x := y op z 表達(dá)式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 無條件轉(zhuǎn)移goto L 條件轉(zhuǎn)移if x relop y goto L 過程調(diào)用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 語義動(dòng)作用到的函數(shù) 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 簡單算術(shù)表達(dá)式及賦值語句 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 簡單算術(shù)表達(dá)式及賦值語句 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數(shù)組元素的地址計(jì)算 一維數(shù)組A的第i個(gè)元素的地址計(jì)算 base + ( i low ) w,7.3 賦 值 語 句,7.3.3 數(shù)組元素的地址計(jì)算 一維數(shù)組A的第i個(gè)元素的地址計(jì)算 base + ( i low ) w 重寫成 i w + (base low w,7.3 賦 值 語 句,二維數(shù)組 列為主 A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 3,7.3 賦 值 語 句,二維數(shù)組 列為主 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 賦 值 語 句,二維數(shù)組 列為主 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 賦 值 語 句,二維數(shù)組 列為主 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 賦 值 語 句,多維數(shù)組 Ai1, i2, ., ik 的地址表達(dá)式 ( ( ( (i1 n2 + i2 ) n3 + i3 ) ) nk + ik) w + base ( ( ( (low1 n2 + low2) n3 + low3) ) nk + lowk ) w,7.3 賦 值 語 句,7.3.4 數(shù)組元素地址計(jì)算的翻譯方案 下標(biāo)變量訪問的產(chǎn)生式 L id Elist | id Eli

15、st Elist, E | E 改成 L Elist | id Elist Elist, E | id E,7.3 賦 值 語 句,所有產(chǎn)生式 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 類型轉(zhuǎn)換 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 布爾表達(dá)式的翻譯,布爾表達(dá)式有兩個(gè)基本目的 計(jì)算邏輯值 在控制流語句中用作條件表達(dá)式,7.4 布爾表達(dá)式的翻譯,布爾表達(dá)式有兩個(gè)基本目的 計(jì)算邏輯值 在控制流語句中用作條件表達(dá)式 布爾表達(dá)式的完全計(jì)算 布爾表達(dá)式的“短路”計(jì)算 E1 or E2 定義成 if E1 then true else E2 E1 and E2 定義成 if E1

25、then E2 else false,7.4 布爾表達(dá)式的翻譯,7.4.1 布爾表達(dá)式的翻譯 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 布爾表達(dá)式的翻譯,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 布爾表達(dá)式的翻譯,表達(dá)式 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 布爾表達(dá)式的翻譯,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 布爾表達(dá)式的翻譯,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 布爾表達(dá)式的翻譯,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 布爾表達(dá)式的翻譯,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 布爾表達(dá)式的翻譯,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 布爾表達(dá)式的翻譯,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 根據(jù)上述屬性文法和賦值語句的翻譯模式，將生成下列代碼,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 布爾表達(dá)式的控制流翻譯 如果E是a b的形式， 那么代碼是： if a b goto E.true goto E.false,7. 5 控制語句的翻譯,7.5.3 開關(guān)語句的翻譯 switch E begin case V1: S1 case V2: S2 . . . case Vn - 1: Sn 1 default: Sn end,

35、7. 5 控制語句的翻譯,分支數(shù)較少時(shí) 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 控制語句的翻譯,分支較多時(shí)，將分支測試的代碼集中在一起， 便于生成較好的分支測試代碼。 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語句，便于代碼生成器 對它進(jìn)行特別處理 test:case V1 L1 case V2 L2 . . . case Vn-1 Ln-1 case t Ln next,7.6 過程調(diào)用的處理,過程調(diào)用的翻譯 S call id (Elist) for 隊(duì)列queue中的每一項(xiàng)p do e

37、mit（param p）； emit （callid.Place） Elist Elist, E 將E.Place加入到queeue的隊(duì)尾 Elist E 初始化queue僅包含E.place,7.4 布爾表達(dá)式和控制流語句,過程調(diào)用id(E1, E2, , En)的中間代碼結(jié)構(gòu) E1.place := E1的代碼 E2.place := E2的代碼 . . . En.place := En的代碼 param E1.place param E2.place . . . param En.place call id.place, n,7.4 布爾表達(dá)式和控制流語句,S call id (Elis

38、t) 為長度為n的隊(duì)列中的每個(gè)E.place， emit(param, E.place); emit(call, id.plase, n) Elist Elist, E 把E.place放入隊(duì)列末尾 Elist E 將隊(duì)列初始化，并讓它僅含E.place,7.7 類型檢查,靜態(tài)檢查中最典型的部分 類型檢查： 類型系統(tǒng)、類型檢查、多態(tài)函數(shù)、重載。 忽略其它的靜態(tài)檢查：控制流檢查、唯一性檢查 、關(guān)聯(lián)名字檢查,7.7.1 類型系統(tǒng) 變量的類型 變量在程序執(zhí)行期間的取值范圍 類型化語言 變量都被給定類型的語言 未類型化的語言 不限制變量值范圍的語言 一個(gè)運(yùn)算可以作用到任意的運(yùn)算對象，其結(jié)果可能是一個(gè)有

39、意義的值、一個(gè)錯(cuò)誤、一個(gè)異?；蛞粋€(gè)未做說明的結(jié)果,類型系統(tǒng)的根本目的是防止程序運(yùn)行時(shí)出現(xiàn)執(zhí)行錯(cuò)誤 類型可靠的語言 粗略地說，所有程序運(yùn)行時(shí)都沒有執(zhí)行錯(cuò)誤出現(xiàn) 類型系統(tǒng)的形式化 類型表達(dá)式、定型斷言、定型規(guī)則、類型檢查算法 顯式類型化的語言 類型是語法的一部分 隱式類型化的語言, 執(zhí)行錯(cuò)誤和安全語言 執(zhí)行錯(cuò)誤 會(huì)被捕獲的錯(cuò)誤（trapped error） 例：非法指令錯(cuò)誤、非法內(nèi)存訪問、除數(shù)為零 引起計(jì)算立即停止 不會(huì)被捕獲的錯(cuò)誤（untrapped error） 例：下標(biāo)變量的訪問越過數(shù)組末端的數(shù)據(jù) 例：跳到一個(gè)錯(cuò)誤的地址，該地址開始的內(nèi)存正好代表一個(gè)指令序列,類型可靠的語言 所

40、有合法的程序都是良行為的 又稱為強(qiáng)檢查的語言 未類型化語言通過徹底的運(yùn)行時(shí)詳細(xì)檢查來排除所有的禁止錯(cuò)誤，如LISP語言 也可以通過靜態(tài)檢查來拒絕不良行為的程序 類型系統(tǒng)就是用來支持這種靜態(tài)檢查的 這種檢查叫做類型檢查 這樣的類型化語言，又稱強(qiáng)類型化的語言,一些實(shí)際使用的語言是弱類型化語言 Pascal語言 無標(biāo)志的變體記錄類型 函數(shù)型參數(shù),一些實(shí)際使用的語言是弱類型化語言 Pascal語言 無標(biāo)志的變體記錄類型 函數(shù)型參數(shù) C語言 有很多不安全的并且被廣泛使用的特征，如： 指針?biāo)阈g(shù)運(yùn)算 類型強(qiáng)制 參數(shù)個(gè)數(shù)可變,在語言設(shè)計(jì)的歷史上，安全性考慮不足是出于效率上的原因,在語言設(shè)計(jì)的歷史上，安全性考慮

41、不足是出于效率上的原因 在語言設(shè)計(jì)中的，安全性的位置越來越重要 C的一些問題已經(jīng)在C+中得以緩和 更多一些問題在Java中已得到解決 ML是一個(gè)類型化的安全語言, 類型化語言的優(yōu)點(diǎn) 從工程的觀點(diǎn)看，類型化語言有下面一些優(yōu)點(diǎn) 開發(fā)的實(shí)惠 較早發(fā)現(xiàn)錯(cuò)誤 類型信息還具有文檔作用, 類型化語言的優(yōu)點(diǎn) 從工程的觀點(diǎn)看，類型化語言有下面一些優(yōu)點(diǎn) 開發(fā)的實(shí)惠 較早發(fā)現(xiàn)錯(cuò)誤 類型信息還具有文檔作用 編譯的實(shí)惠 程序模塊可以相互獨(dú)立地編譯, 類型化語言的優(yōu)點(diǎn) 從工程的觀點(diǎn)看，類型化語言有下面一些優(yōu)點(diǎn) 開發(fā)的實(shí)惠 較早發(fā)現(xiàn)錯(cuò)誤 類型信息還具有文檔作用 編譯的實(shí)惠 程序模塊

42、可以相互獨(dú)立地編譯 運(yùn)行的實(shí)惠 可得到更有效的空間安排和訪問方式,7.7.2 類型檢查器的規(guī)格說明,一個(gè)簡單的語言 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 類型檢查器的規(guī)格說明,類型檢查聲明語句 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 類型檢查器的規(guī)格說明,類型檢查聲明語句 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 類型檢查器的規(guī)

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 類型檢查器的規(guī)格說明,類型表達(dá)式的抽象語法 基本類型 boolean, char, integer, real 構(gòu)造類型 數(shù)組類

45、型array(I, T) 指針類型pointer(T) 積類型T1 T2 函數(shù) T1 T2 記錄（例）record(address integer) (lexeme array(1.10, char) 類型表達(dá)式中還可以出現(xiàn)類型名字和類型變量,7.7.2 類型檢查器的規(guī)格說明,類型檢查表達(dá)式 E truthE.type := boolean E numE.type := integer E idE.type := lookup(id.entry,7.7.2 類型檢查器的規(guī)格說明,類型檢查表達(dá)式 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 類型檢查器的規(guī)格說明,類型檢查表達(dá)式 E E1 E2 E.type := if E2. type = integer and E1. type = array(s, t) then t else type_error,7.7.2 類型檢查器的規(guī)格說明,類型檢查表達(dá)式 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 類型檢查器的規(guī)格說明,類型檢查表達(dá)式 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 類型檢查器的規(guī)格說明,類型檢查語句 S id := E S. type := if id. type = E. type then void else type_error,7.7.2 類型檢查器的規(guī)格說明,類型檢查語句 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 類型檢查器的規(guī)格說明,類型檢查語句 S while E do S1 S.type := if E.type = boolean then S1. type else type_error,7.7.2 類型檢查器的規(guī)格說明,類型檢查語句 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 類型檢查器的規(guī)格說明,類型檢查程序 P D; S P. type := if S. type = void then void else type_error,7.7.2 類型檢查器的規(guī)格說明,類型轉(zhuǎn)換 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 多態(tài)函數(shù), 為什么要使用多態(tài)函數(shù) 例：用Pascal語言寫不出求表長度的通用程序 type link = cell ; cell = record info : integer; next : link end,7.7.3 多 態(tài) 函 數(shù),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 多 態(tài) 函 數(shù),用ML語言很容易寫出求表長度的程序而不必管表元的類型。 fun length (lptr) = if null (lptr) then 0 else length (tl (lptr) + 1,7.7.3 多 態(tài) 函 數(shù),用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 多 態(tài) 函 數(shù),多態(tài)函數(shù) 允許變元有不同的類型,7.7.3 多 態(tài) 函 數(shù),多態(tài)函數(shù) 允許變元有不同的類型 體中的語句可以在變元類型不同的情況下執(zhí)行（區(qū)別于重載的特征,7.7.3 多 態(tài) 函 數(shù),多態(tài)函數(shù) 允許變元有不同的類型 體中的語句可以在變元類型不同的情況下執(zhí)行（區(qū)別于重載的特征） 多態(tài)算符 用于以不同類型的變元執(zhí)行的代碼段,7.7.3 多 態(tài) 函 數(shù),多態(tài)函數(shù) 允許變元有不同的類型 體中的語句可以在變元類型不同的情況下執(zhí)行（區(qū)別于重載的特征） 多態(tài)算符 用于以不同類型

54、的變元執(zhí)行的代碼段 例如：數(shù)組索引,7.7.3 多 態(tài) 函 數(shù),多態(tài)函數(shù) 允許變元有不同的類型 體中的語句可以在變元類型不同的情況下執(zhí)行（區(qū)別于重載的特征） 多態(tài)算符 用于以不同類型的變元執(zhí)行的代碼段 例如：數(shù)組索引、函數(shù)作用,7.7.3 多 態(tài) 函 數(shù),多態(tài)函數(shù) 允許變元有不同的類型 體中的語句可以在變元類型不同的情況下執(zhí)行（區(qū)別于重載的特征） 多態(tài)算符 用于以不同類型的變元執(zhí)行的代碼段 例如：數(shù)組索引、函數(shù)作用、通過指針間接訪問,7.7.3 多 態(tài) 函 數(shù),多態(tài)函數(shù) 允許變元有不同的類型 體中的語句可以在變元類型不同的情況下執(zhí)行（區(qū)別于重載的特征） 多態(tài)算符 用于以不同類型的變元執(zhí)行的代碼

55、段 例如：數(shù)組索引、函數(shù)作用、通過指針間接訪問 C語言手冊中關(guān)于指針 E - 引入類型變量、 D D; D | id : Q - 笛卡兒積類型、 Q type-variable. Q | T -多態(tài)函數(shù) T T T | T T | unary-constructor ( T ) | basic-type | type-variable | ( T ) E E (E ) | E, E | id,7.7.3 多 態(tài) 函 數(shù),代換、實(shí)例和合一 代換: 類型表達(dá)式中的類型變量用其所代表的類型表達(dá)式去替換,7.7.3 多 態(tài) 函 數(shù),代換、實(shí)例和合一 代換: 類型表達(dá)式中的類型變量用其所代表的類型表達(dá)式

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 多 態(tài) 函 數(shù),實(shí)例 把subst函數(shù)用于t后所得的類型表達(dá)式是t的一個(gè)實(shí)例，用S (t)表示。 例子（s t 表示s是t 的實(shí)例） pointer ( integer ) pointer ( ) pointer ( real ) p

57、ointer ( ) integer integer pointer ( ),7.7.3 多 態(tài) 函 數(shù),下面左邊的類型表達(dá)式不是右邊的實(shí)例 integerreal 代換不能用于基本類型 integer real 的代換不一致 integer 的所有出現(xiàn)都應(yīng)該代換,7.7.3 多 態(tài) 函 數(shù),合一 如果存在某個(gè)代換S使得S (t1) = S (t2)，那么這兩個(gè)表達(dá)式t1和t2能夠合一 最一般的合一代換 S(t1) = S(t2)； 對任何其它滿足S(t1) = S(t2)的代換S，代換S(t1)是S (t1)的實(shí)例,7.7.3 多 態(tài) 函 數(shù),多態(tài)函數(shù)的類型檢查 多態(tài)函數(shù)和普通函數(shù)在類型檢查

58、上的區(qū)別 (1)同一多態(tài)函數(shù)的不同出現(xiàn)無須變元有相同類型,7.7.3 多 態(tài) 函 數(shù),2)必須把類型相同的概念推廣到類型合一,7.7.3 多 態(tài) 函 數(shù),2)必須把類型相同的概念推廣到類型合一 (3)要記錄表達(dá)式合一的結(jié)果,7.7.3 多 態(tài) 函 數(shù),檢查多態(tài)函數(shù)的翻譯方案 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 多 態(tài) 函 數(shù),7.7.3 多 態(tài) 函 數(shù),確定表長度的ML函數(shù) fun length (lptr) = if null (lptr) then 0 else length (tl (lptr) + 1,7.7.3 多 態(tài) 函 數(shù),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 多 態(tài) 函 數(shù),7.7.3 多 態(tài) 函 數(shù),7.7.3 多 態(tài) 函 數(shù),7.7.3 多 態(tài) 函 數(shù),fun length (lptr) = if null (lptr) then 0 else length (tl (lptr) + 1; length函數(shù)的類型是 . list () integer,7.7.4 函數(shù)和運(yùn)算符的重載,重載符號(hào) 有多個(gè)含義，但在引用點(diǎn)的含義都是唯一的 例如 加法算符+可用于不同類型，是不同的函數(shù) 在Ada中，( ) 是重載的，