第七章中间代码生成

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

2、数，那么E的后缀的后缀式式就是就是E本身。本身。7.1 中中 间间 语语 言言7.1.1 后缀表示后缀表示表达式表达式E的的后缀表示后缀表示可以如下递归定义可以如下递归定义 如果如果E E是变量或常数，那么是变量或常数，那么E的后缀表示就是的后缀表示就是E本身。本身。 如果如果E是形式为是形式为E1 opE2的表达式，那么的表达式，那么E的后的后缀式是缀式是E1 E2 op，其中其中E1 和和E2 分别是分别是E1和和E2的后缀式。的后缀式。7.1 中中 间间 语语 言言7.1.1 后缀式后缀式表达式表达式E的的后缀式后缀式可以如下递归定义可以如下递归定义 如果如果E E是变量或常数，那么是变

3、量或常数，那么E的后缀的后缀式式就是就是E本身。本身。 如果如果E是形式为是形式为E1 opE2的表达式，那么的表达式，那么E的后的后缀式是缀式是E1 E2 op，其中其中E1 和和E2 分别是分别是E1和和E2的后缀式。的后缀式。 如果如果E是形式为是形式为(E1)的表达式，那么的表达式，那么E1的后缀的后缀表示也是表示也是E的后缀的后缀式。式。 7.1 中中 间间 语语 言言 后缀式表示法是波兰逻辑学家卢卡西维奇（后缀式表示法是波兰逻辑学家卢卡西维奇（LukasiewiczLukasiewicz）发明的一种表示表达式的方法发明的一种表示表达式的方法因此又称逆波兰表示法。这种表示法是把运因此

4、又称逆波兰表示法。这种表示法是把运算量（操作数）写在前面把算符写在后面（算量（操作数）写在前面把算符写在后面（后缀）。后缀）。 7.1 中中 间间 语语 言言把表达式翻译为后缀式的语义规则描述把表达式翻译为后缀式的语义规则描述 产产 生生 式式 语语 义义 规规 则则EE1op E2 E.code :E1.code | E2.code | opE（E1） Ecode := E1.codeEid Ecode :id7.1 中中 间间 语语 言言 后缀后缀式式不需要括号不需要括号(8 4) + 2 的后缀表示是的后缀表示是8 4 2 + 后缀后缀式式的最大优点是便于计算机处理表达式的最大优点是便于

5、计算机处理表达式 后缀后缀式式很容易拓广到含一元算符的表达式很容易拓广到含一元算符的表达式 后缀后缀式式也可以拓广到表示赋值语句和控制语也可以拓广到表示赋值语句和控制语句，但很难用栈来描述它的计算句，但很难用栈来描述它的计算7.1 中中 间间 语语 言言7.1.2 图形表示图形表示图表示法包括图表示法包括DAG与抽象语法树与抽象语法树 语法树是一种图形化的中间表示语法树是一种图形化的中间表示assigna+ bcdcduminus(a) 语法树语法树 a := ( b + c d ) + c d的图形表示的图形表示7.1 中中 间间 语语 言言7.1.2 图形表示图形表示 语法树是一种图形化的

6、中间表示语法树是一种图形化的中间表示 有向无环图有向无环图也是一种中间表示也是一种中间表示 assigna+ bcdcduminusassigna+ bcduminus(a) 语法树语法树(b)DAG a := ( b + c d ) + c d的图形表示的图形表示7.1 中中 间间 语语 言言构造赋值语句语法树的语法制导定义构造赋值语句语法树的语法制导定义产产 生生 式式 语语 义义 规规 则则S id :=E S.nptr := mknode(assign, mkleaf (id, id.entry), E.nptr) E E1 +E2 E.nptr := mknode( +, E1.np

7、tr, E2.nptr) E E1 E2E.nptr := mknode( , E1.nptr, E2.nptr) E E1E.nptr := mkunode( uminus, E1.nptr) E (E1) E.nptr := E1.nptr F id E.nptr := mkleaf (id, id.entry) 7.1 中中 间间 语语 言言7.1.3 三地址代码三地址代码一般形式：一般形式：x := y op z表达式表达式x + y z翻译成的三地址语句序列是翻译成的三地址语句序列是t1 := y z t2 := x + t1 7.1 中中 间间 语语 言言三地址代码是语法树或三地址

8、代码是语法树或DAG的一种线性表示的一种线性表示a := ( b + c d ) + c d语法树的代码语法树的代码DAG的代码的代码t1 := bt1 := bt2 := c dt2 := c dt3 := t1 + t2t3 := t1 + t2t4 := c dt4 := t3 + t2t5 := t3 + t4 a := t4a := t57.1 中中 间间 语语 言言本书常用的三地址语句本书常用的三地址语句 赋值语句赋值语句x := y op z， x := op y， x := y 无条件转移无条件转移goto L 条件转移条件转移if x relop y goto L 过程调用过

9、程调用param x 和和call p , n 过程返回过程返回 return y 索引赋值索引赋值x := yi和和 xi := y 地址和指针赋值地址和指针赋值x := &y，x := y和和 x := yT1:y*zT2:xT1 T1:=c T1:=c T2:=b*T1 T2:=b*T1 T3:=c T5:=T2+T4 T4:=b*T3 a:=T5 T5:=T2+T4 a:=T5 图7.5相应于图7.3的树和DAG的三地址代码 （a）对于抽象语法树的代码；(b)对于DAG的代码四元式、三元式、间接三元式 三地址语句可看成中间代码的一种抽象形式。编译程序中，三地址代码语句的具体实现

10、可以用记录表示，记录中包含表示运算符和操作数的域。通常有三种表示方法：四元式、三元式、间接三元式。 a:b*cb*c 四元式 三元式 op arg1 arg2 result op arg1 arg2(0) uminus c T1 (0) uminus c * b T1 T2 (1) * b (0) (2)uminus c T3 (2)uminus c (3) * b T3 T4 (3) * b (2) (4) + T2 T4 T5 (4) + (1) (3)(1) (5) := T5 a (5) assign a (4)7.2 说说 明明 语语 句句 为局部名字建立符号表条目为局部名字建立符号

11、表条目 为它分配存储单元为它分配存储单元 符号表中包含名字的类型和分配给它的存储符号表中包含名字的类型和分配给它的存储单元的相对地址等信息单元的相对地址等信息7.2 说说 明明 语语 句句7.2.1 过程中的声明过程中的声明7.2 说说 明明 语语 句句计算被声明名字的类型和相对地址计算被声明名字的类型和相对地址P D offset := 0D D ; D D id : T enter ( , T.type, offset); offset := offset + T.width T integer T.type := integer; T.width := 4 T real T

12、.type := real; T.width := 8 T array num of T1 T.type := array (num.val, T1.type); T.width := num.val T1.widthT T1 T.type := pointer (T1.type); T.width := 4 7.2 说说 明明 语语 句句7.2.2 作用域信息的保存作用域信息的保存 所讨论语言的文法所讨论语言的文法P D SD D ; D | id : T | proc id ; D ; S 语义动作用到的函数语义动作用到的函数mktable(previous)enter(table, na

13、me, type, offset) addwidth(table, width)enterproc(table, name, newtable)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 ; D2D proc id ; N D1; S t := top(tblptr); addwidth(t, top

14、(offset) ); pop(tblptr); pop(offset); enterproc(top(tblptr), , t ) Did : T enter(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:

15、integer;（4） procedure readarray（5） var i: integer;（6） beginaendreadarray（7） procedure 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

16、） v（17） exchange(i,j); （18） end partition;（19） begin end quicksort;（20） beginend sort.7.2 说说 明明 语语 句句exchangereadarrayxa表表 头头空空sortquicksort指向指向readarraypartitionvk表表 头头quicksortreadarraryi表表 头头exchange表表 头头指向指向exchangepartition7.2 说说 明明 语语 句句7.2.3 记录的域名记录的域名T record D endT record L D endT.type := r

17、ecord (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 thenemit ( p，:=, E.place)else error E E1 + E2E.place := newtemp; emit (E.place, :=, E1.place

18、, +, 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 赋赋 值值 语语 句句7.3.2数组元素的地址计算数组元素的地址计算一维数组一维数组A的第的第i个元素的地址计算个元素的地址计算base + ( i low ) w7

19、.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, 37.3 赋赋 值值 语语 句句二维数组二维数组 列为主列为主A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 3 行为主行为主A1, 1, A1, 2, A1, 3, A2, 1, A2, 2, A2, 37.

20、3 赋赋 值值 语语 句句二维数组二维数组 列为主列为主A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 3 行为主行为主A1, 1, A1, 2, A1, 3, A2, 1, A2, 2, A2, 3base + ( (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, 3base

21、+ ( (i1 low1) 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 ) w7.3 赋赋 值值 语语 句句7.3.4 数组元素地址计算的翻译方案数组元素地址计

22、算的翻译方案下标变量访问的产生式下标变量访问的产生式L id Elist | idElist Elist, E | E改成改成L Elist | idElist Elist, E | id E7.3 赋赋 值值 语语 句句所有产生式所有产生式S L := EE E + EE (E )E LL Elist L idElist Elist, EElist id E7.3 赋赋 值值 语语 句句L id L.place := id.place; L.offset := null 7.3 赋赋 值值 语语 句句L id L.place := id.place; L.offset := null Eli

23、st id E Elist.place := E.place; Elist.ndim := 1; 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

24、.array, m) ); emit (t, :=, t, +, E.place); Elist.array := Elist1.array; Elist.place := t; Elist.ndim := m7.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,

25、:=, Elist1.place, , limit(Elist1.array, m) ); emit (t, :=, t, +, E.place); Elist.array := Elist1.array; Elist.place := t; Elist.ndim := mL 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 赋

26、赋 值值 语语 句句E L if L.offset = null then / L是简单变量是简单变量 / E.place := 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, )

27、end E E1 + E2E.place := newtemp;emit (E.place, :=, E1.place , +, E2.place) 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)

28、E (E1 )E.place := E1.place 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 S L := E if L.offset

29、= null then / L是简单变量是简单变量 /emit (L.place, := , E.place)else emit (L.place , , L.offset, , :=, E.place) 7.3 赋赋 值值 语语 句句S:=L.place := xL.offset := nullxE.place := t4L.place := t2L.offset := t3Elist.place := t1Elist.ndim := 2Elist.array := A,Elist.place := yElist.ndim := 1Elist.array := AE.place := zL.

30、place := zL.offset := nullE.place := yL.place := yL.offset := nullAzy x := A y, z 的注释分析树的注释分析树7.3 赋赋 值值 语语 句句S:=L.place := xL.offset := nullxE.place := t4L.place := t2L.offset := t3Elist.place := t1Elist.ndim := 2Elist.array := A,Elist.place := yElist.ndim := 1Elist.array := AE.place := zL.place :=

31、zL.offset := nullE.place := yL.place := yL.offset := nullAzy x := A y, z 的注释分析树的注释分析树t1 := y 20 t1 := t1 + z 7.3 赋赋 值值 语语 句句S:=L.place := xL.offset := nullxE.place := t4L.place := t2L.offset := t3Elist.place := t1Elist.ndim := 2Elist.array := A,Elist.place := yElist.ndim := 1Elist.array := AE.place

32、:= zL.place := zL.offset := nullE.place := yL.place := yL.offset := nullAzy x := A y, z 的注释分析树的注释分析树t1 := y 20 t1 := t1 + z t2 :=A 84 t3 := 4 t1 7.3 赋赋 值值 语语 句句S:=L.place := xL.offset := nullxE.place := t4L.place := t2L.offset := t3Elist.place := t1Elist.ndim := 2Elist.array := A,Elist.place := yEli

33、st.ndim := 1Elist.array := AE.place := zL.place := zL.offset := nullE.place := yL.place := yL.offset := nullAzy x := A y, z 的注释分析树的注释分析树t1 := y 20 t1 := t1 + z t2 :=A 84 t3 := 4 t1 t4 := t2 t3 7.3 赋赋 值值 语语 句句S:=L.place := xL.offset := nullxE.place := t4L.place := t2L.offset := t3Elist.place := t1Eli

34、st.ndim := 2Elist.array := A,Elist.place := yElist.ndim := 1Elist.array := AE.place := zL.place := zL.offset := nullE.place := yL.place := yL.offset := nullAzy x := A y, z 的注释分析树的注释分析树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 j（x和和y的类型是的

35、类型是real，i和和j的类型是的类型是integer）中间代码中间代码t1 := i int jt2 := inttoreal t1 t3 := y real+ t2 x := t37.3 赋赋 值值 语语 句句E E1 + E2E.place := newtempif E1.type = integer and E2.type = integer then begin emit (E.place, :=, E1.place, int+, E2.place);E.type = integerendelse if E1.type = integer and E2.type = real the

36、n beginu := newtemp;emit (u, :=, inttoreal, E1.place);emit (E.place, :=, u, real+, E2.place);E.type := realend . . .7.4 布尔表达式的翻译布尔表达式的翻译布尔表达式有两个基本目的布尔表达式有两个基本目的 计算逻辑值计算逻辑值 在控制流语句中用作条件表达式在控制流语句中用作条件表达式7.4 布尔表达式的翻译布尔表达式的翻译布尔表达式有两个基本目的布尔表达式有两个基本目的 计算逻辑值计算逻辑值 在控制流语句中用作条件表达式在控制流语句中用作条件表达式布尔表达式的完全计算布尔表达式的

37、完全计算布尔表达式的布尔表达式的“短路短路”计算计算E1 or E2 定义成定义成 if E1 then true else E2E1 and E2 定义成定义成 if E1 then E2 else false7.4 布尔表达式的翻译布尔表达式的翻译7.4.1 布尔表达式的翻译布尔表达式的翻译E E or E | E and E | not E | ( E ) | id relop id | true | falsea b的翻译的翻译100: if a b goto 103101: t := 0102: goto 104103: t := 1104:7.4 布尔表达式的翻译布尔表达式的翻译E

38、 E1 or E2 E.place := newtemp; emit (E.place, :=, E1.place, or E2.place) E id1 relop id2E.place := newtemp;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 i

39、f a b goto 103 107 T2 :=1101 T1 :=0 108 if e f goto 111 102 goto 104 109 T3:=0103 T1 :=1 110 goto 112 104 if c d goto 107 111 T3:=1105 T2 :=0 112 T4:= T2 and T3 106 goto 108 113 T5:= T1 or T47.4 布尔表达式的翻译布尔表达式的翻译E E1 or E2E1.true := E.true; E1.false := newlabel; E2.true := E.true; E2.false := E.false

40、; E.code := E1.code | gen(E1.false, :) | E2.code 7.4 布尔表达式的翻译布尔表达式的翻译E E1 or E2E1.true := E.true; E1.false := newlabel; E2.true := E.true; E2.false := E.false; E.code := E1.code | gen(E1.false, :) | E2.code E not E1E1.true := E.false; E1.false := E.true; E.code := E1.code 7.4 布尔表达式的翻译布尔表达式的翻译E E1 an

41、d E2E1.true := newlabel; E1.false := E.false; E2.true := E.true; E2.false := E.false; E.code := E1.code | gen(E1.true, :) | E2.code 7.4 布尔表达式的翻译布尔表达式的翻译E E1 and E2E1.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 ) E

42、1.true := E.true; E1.false := E.false; E.code := E1.code 7.4 布尔表达式的翻译布尔表达式的翻译E id1 relop id2E.code := gen(if, id1.place, relop.op, id2.place, goto, E.true) | gen(goto, E.false) 7.4 布尔表达式的翻译布尔表达式的翻译E id1 relop id2E.code := gen(if, id1.place, relop.op, id2.place, goto, E.true) | gen(goto, E.false) E t

43、rueE.code := gen(goto, E.true)E falseE.code := gen(goto, E.false)7. 5 控制语句的翻译控制语句的翻译7.5.1 控制流语句的翻译控制流语句的翻译S if E then S1| if E then S1 else S2| while E do S1| S1; S2 7. 5 控制语句的翻译控制语句的翻译E.codeS1.codeE.true:. . .指向指向E.true指向指向E.false(a) if-thenE.codeS1.codeE.true:. . .指向指向E.true指向指向E.falseE.false:goto

44、 S.nextS2.code(b) if-then-elseE.codeS1.codeE.true:. . .指向指向E.true指向指向E.falsegoto S.beginS.begin:(c) while-doS1.codeS2.codeS1.next:. . .(d) S1; S27. 5 控制语句的翻译控制语句的翻译S if E then S1E.true := newlabel; E.false := S.next; S1.next := S.next; S.code := E.code | gen(E.true, :) | S1.code E.codeS1.codeE.true:

45、. . .指向指向E.true指向指向E.false(a) if-then7. 5 控制语句的翻译控制语句的翻译S if E then S1 else S2E.true := newlabel; E.false := newlabel; S1.next := S.next; S2.next := S.next; S.code := E.code | gen(E.true, :) | S1.code | gen(goto, S.next) | gen(E.false, :) | S2.code E.codeS1.codeE.true:. . .指向指向E.true指向指向E.falseE.fal

46、se:goto S.nextS2.code(b) if-then-else7. 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) E.codeS1.codeE.true:. . .指向指向E.true指向指向E.falsegoto S.beginS.begin:

47、(c) while-do7. 5 控制语句的翻译控制语句的翻译S S1; S2S1.next := newlabel; S2.next := S.next; S.code := S1.code | gen(S1.next, :) | S2.code S1.codeS2.codeS1.next:. . .(d) S1; S2 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+

48、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) if cd then 102 (j, c, d,104) x:=y+z103 (j, -, -, 100)104 (+, y, z, T) 105 (:=, T, -, x)106 (j, -, -, 100)1077. 5 控制语句的翻译控制语句的翻译7.5.2 布尔表达式的控制流翻译布尔表达式的控制流翻译如果如果E是是a b的形式，的形式，那么代码是：那么代码是：if a b goto E.tr

49、uegoto E.false7. 5 控制语句的翻译控制语句的翻译7.5.3 开关语句的翻译开关语句的翻译switch Ebegincase V1: S1case V2: S2. . .case Vn - 1: Sn 1default: Snend7. 5 控制语句的翻译控制语句的翻译分支数较少时分支数较少时t := E的代码的代码 | Ln-2: if t Vn-1 goto Ln-1 if t V1 goto L1 | Sn -1的代码的代码 S1的代码的代码 | goto nextgoto next | Ln-1: Sn的代码的代码 L1:if t V2 goto L2 | next:

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

51、Sn -1的代码的代码| next:goto next7. 5 控制语句的翻译控制语句的翻译中间代码增加一种中间代码增加一种case语句，便于代码生成器语句，便于代码生成器对它进行特别处理对它进行特别处理 test: case V1 L1case V2 L2. . .case Vn-1 Ln-1case t Ln next: 7.6 过程调用的处理过程调用的处理 过程调用的翻译过程调用的翻译S call id (Elist) for 队列队列queue中的每一项中的每一项p do emit（param p）；）； emit （callid.Place）Elist Elist, E 将将E.Pl

52、ace加入到加入到queeue的队尾的队尾 Elist E 初始化初始化queue仅包含仅包含E.place7.4 布尔表达式和控制流语句布尔表达式和控制流语句过程调用过程调用id(E1, E2, , En)的中间代码结构的中间代码结构E1.place := E1的代码的代码E2.place := E2的代码的代码. . .En.place := En的代码的代码param E1.placeparam E2.place. . .param En.placecall id.place, n7.4 布尔表达式和控制流语句布尔表达式和控制流语句S call id (Elist)为长度为为长度为n的队

53、列中的每个的队列中的每个E.place，emit(param, E.place); emit(call, id.plase, n) Elist Elist, E把把E.place放入队列末尾放入队列末尾Elist E将队列初始化，并让它仅含将队列初始化，并让它仅含E.place 7.7 类型检查类型检查 静态检查中最典型的部分静态检查中最典型的部分 类型检查：类型检查：类型系统、类型检查、多态函数、重载。类型系统、类型检查、多态函数、重载。 忽略其它的静态检查：忽略其它的静态检查：控制流检查、唯一性控制流检查、唯一性检查检查 、关联名字检查。、关联名字检查。分析分析器器类型类型检查检查器器中间

54、中间代码代码生成生成 器器语 法语 法树树语 法语 法树树中间中间表示表示记号记号流流7.7.1 类型系统类型系统 变量的类型变量的类型变量在程序执行期间的取值范围变量在程序执行期间的取值范围 类型化语言类型化语言变量都被给定类型的语言变量都被给定类型的语言 未类型化的语言未类型化的语言不限制变量值范围的语言不限制变量值范围的语言一个运算可以作用到任意的运算对象，其结果可能一个运算可以作用到任意的运算对象，其结果可能是一个有意义的值、一个错误、一个异常或一个未是一个有意义的值、一个错误、一个异常或一个未做说明的结果。做说明的结果。 类型系统类型系统的根本目的是防止程序运行时出现执行错的根本目的

55、是防止程序运行时出现执行错误误 类型可靠的类型可靠的语言语言粗略地说，所有程序运行时都没有执行错误出现粗略地说，所有程序运行时都没有执行错误出现 类型系统的形式化类型系统的形式化类型表达式、定型断言、定型规则、类型检查算法类型表达式、定型断言、定型规则、类型检查算法 显式类型化的显式类型化的语言语言类型是语法的一部分类型是语法的一部分 隐式类型化的隐式类型化的语言语言 执行错误和安全语言执行错误和安全语言执行错误执行错误 会被捕获的错误会被捕获的错误（trapped error） 例：例：非法指令错误、非法内存访问非法指令错误、非法内存访问、除数为零除数为零 引起计算立即停止引起

56、计算立即停止 不会被捕获的错误不会被捕获的错误（untrapped error） 例：下标变量的例：下标变量的访问越过数组末端的数据访问越过数组末端的数据 例：例：跳到一个错误的地址，该地址开始的内存正跳到一个错误的地址，该地址开始的内存正好代表一个指令序列好代表一个指令序列 类型可靠的类型可靠的语言语言 所有合法的程序都是良行为的所有合法的程序都是良行为的 又称为又称为强检查的语言强检查的语言 未类型化语言未类型化语言通过彻底的运行时详细检查来排除通过彻底的运行时详细检查来排除所有的禁止错误，如所有的禁止错误，如LISP语言语言 也也可以通过静态检查来拒绝不良行为的程序可以通过静态检查来拒绝

57、不良行为的程序 类型系统就是用来支持这种静态检查的类型系统就是用来支持这种静态检查的 这种检查叫做类型检查这种检查叫做类型检查 这样的这样的类型化语言，又称类型化语言，又称强类型化的强类型化的语言语言一些实际使用的语言是弱类型化语言一些实际使用的语言是弱类型化语言 Pascal语言语言 无标志的变体记录类型无标志的变体记录类型 函数型参数函数型参数一些实际使用的语言是弱类型化语言一些实际使用的语言是弱类型化语言 Pascal语言语言 无标志的变体记录类型无标志的变体记录类型 函数型参数函数型参数 C语言语言有很多不安全的并且被广泛使用的特征，如：有很多不安全的并且被广泛使用的特征，如： 指针算

58、术运算指针算术运算 类型强制类型强制 参数个数可变参数个数可变 在语言设计的历史上，安全性考虑不足是出在语言设计的历史上，安全性考虑不足是出于效率上的原因于效率上的原因 在语言设计的历史上，安全性考虑不足是出在语言设计的历史上，安全性考虑不足是出于效率上的原因于效率上的原因 在语言设计中的，安全性的位置越来越重要在语言设计中的，安全性的位置越来越重要 C的一些问题已经在的一些问题已经在C+中得以缓和中得以缓和 更多一些问题在更多一些问题在Java中已得到解决中已得到解决 ML是一个类型化的安全语言是一个类型化的安全语言 类型化语言的优点类型化语言的优点从工程的观点看，类型化语言有

59、下面一些优点从工程的观点看，类型化语言有下面一些优点 开发的实惠开发的实惠较早发现错误较早发现错误类型信息还具有文档作用类型信息还具有文档作用 类型化语言的优点类型化语言的优点从工程的观点看，类型化语言有下面一些优点从工程的观点看，类型化语言有下面一些优点 开发的实惠开发的实惠较早发现错误较早发现错误类型信息还具有文档作用类型信息还具有文档作用 编译的实惠编译的实惠程序模块可以相互独立地编译程序模块可以相互独立地编译 类型化语言的优点类型化语言的优点从工程的观点看，类型化语言有下面一些优点从工程的观点看，类型化语言有下面一些优点 开发的实惠开发的实惠较早发现错误较早

60、发现错误类型信息还具有文档作用类型信息还具有文档作用 编译的实惠编译的实惠程序模块可以相互独立地编译程序模块可以相互独立地编译 运行的实惠运行的实惠可得到更有效的空间安排和访问方式可得到更有效的空间安排和访问方式7.7.2 类型检查器的规格说明类型检查器的规格说明 一个简单的语言一个简单的语言P D ; SD D ; D | id : TT boolean | integer | array num of T | T | T TS id := E | if E then S | while E do S | S ; SE truth | num | id | E mod E | E E | E | E