第七章 语义分析和中间代码生成 本章内容 介绍几种常用的中间表示：后缀表示、图形表示和三地址代码 用语法制导定义和翻译方案的方法来说明程序设计语言的结构怎样被翻译成中间形式

7.1 中 间 语 言 7.1.1 后缀式 表达式E的后缀式可以如下递归定义 如果E是变量或常数，那么E的后缀式就是E本身。

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的后缀式可以如下递归定义 如果E是变量或常数，那么E的后缀式就是E本身。 7.1 中 间 语 言 7.1.1 后缀式 表达式E的后缀式可以如下递归定义 如果E是变量或常数，那么E的后缀式就是E本身。 如果E是形式为E1 opE2的表达式，那么E的后缀式是E1 E2 op，其中E1和E2分别是E1和E2的后缀式。 如果E是形式为(E1)的表达式，那么E1的后缀表示也是E的后缀式。

7.1 中 间 语 言 后缀式表示法是波兰逻辑学家卢卡西维奇（Lukasiewicz）发明的一种表示表达式的方法因此又称逆波兰表示法。这种表示法是把运算量（操作数）写在前面把算符写在后面（后缀）。

7.1 中 间 语 言 把表达式翻译为后缀式的语义规则描述 产 生 式 语 义 规 则 7.1 中 间 语 言 把表达式翻译为后缀式的语义规则描述 产 生 式 语 义 规 则 E→E1op E2 E.code :＝E1.code || E2.code || op E→（E1） E．code := E1.code E→id E．code :＝id

7.1 中 间 语 言 后缀式不需要括号 (8  4) + 2 的后缀表示是8 4 2 + 后缀式的最大优点是便于计算机处理表达式 7.1 中 间 语 言 后缀式不需要括号 (8  4) + 2 的后缀表示是8 4 2 + 后缀式的最大优点是便于计算机处理表达式 后缀式很容易拓广到含一元算符的表达式 后缀式也可以拓广到其它语言成分 演示Table7_1

a := (b + cd ) + cd抽象语法树 7.1 中 间 语 言 7.1.2 图表示法 图表示法包括DAG与抽象语法树 抽象语法树 assign a +  b c d uminus (a) 语法树 a := (b + cd ) + cd抽象语法树

a := (b + cd ) + cd的图形表示 7.1 中 间 语 言 7.1.2 图表示法 有向无环图也是一种中间表示 assign a +  b c d uminus (a) 语法树 (b)DAG a := (b + cd ) + cd的图形表示

7.1 中 间 语 言 构造赋值语句抽象语法树的属性文法 演示Table7_2 产 生 式 语 义 规 则 S  id :=E 7.1 中 间 语 言 构造赋值语句抽象语法树的属性文法 演示Table7_2 产 生 式 语 义 规 则 S  id :=E S.nptr := mknode(‘assign’, mkleaf (id, id.entry), E.nptr) E  E1 +E2 E.nptr := mknode( ‘+’, E1.nptr, E2.nptr) E  E1 E2 E.nptr := mknode( ‘’, E1.nptr, E2.nptr) E  E1 E.nptr := mkunode( ‘uminus’, E1.nptr) E  (E1) E.nptr := E1.nptr E id E.nptr := mkleaf (id, id.entry)

7.1 中 间 语 言 7.1.3 三地址代码 一般形式：x := y op z 表达式x + y  z翻译成的三地址语句序列是 7.1 中 间 语 言 7.1.3 三地址代码 一般形式：x := y op z 表达式x + y  z翻译成的三地址语句序列是 t1 := y  z t2 := x + t1 演示Table7_3

7.1 中 间 语 言 三地址代码是语法树或DAG的一种线性表示 a := (b + cd ) + cd 语法树的代码 DAG的代码 7.1 中 间 语 言 三地址代码是语法树或DAG的一种线性表示 a := (b + cd ) + cd 语法树的代码 DAG的代码 t1 := b t1 := b t2 := c  d t2 := c  d t3 := t1 + t2 t3 := t1 + t2 t4 := c  d t4 := t3 + t2 t5 := t3 + t4 a := t4 a := t5

7.1 中 间 语 言 约定的三地址语句 赋值语句x := y op z， x := op y， x := y 无条件转移goto L 7.1 中 间 语 言 约定的三地址语句 赋值语句x := y op z， x := op y， x := y 无条件转移goto L 条件转移if x relop y goto L 过程调用param x 和call p , n 过程返回 return y 索引赋值x := y[i]和 x[i] := y 地址和指针赋值x := &y，x := y和x := y

四元式、三元式、间接三元式 三地址语句可看成中间代码的一种抽象形式。编译程序中，三地址代码语句的具体实现可以用记录表示，记录中包含表示运算符和操作数的域。通常有三种表示方法：四元式、三元式、间接三元式。

a:＝b*－c＋b*－c 四元式 三元式 op arg1 arg2 result op arg1 arg2 四元式 三元式 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) (5) := T5 a (5) assign a (4)

X：=(A+B)*C;Y:=D↑(A+B); 间接 三元式 op arg1 arg2 (1) + A B (2) * (1) C (3) := X (2) (4) ↑ D (1) (5) := Y (4) 间接代码 （1） （2） （3） （4） （5）

7.2 说 明 语 句 为局部名字建立符号表条目 为它分配存储单元 符号表中包含名字的类型和分配给它的存储单元的相对地址等信息

7.2 说 明 语 句 7.2.1 过程中的声明

7.2 说 明 语 句 演示Figure7.6 计算被声明名字的类型和相对地址 P  D {offset := 0} D  D ; D D  id : T {enter ( id.name, 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.type := 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 作用域信息的保存 所讨论语言的文法 语义动作用到的函数 mktable(previous) 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.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), id.name, t ) } Did : T {enter(top(tblptr), id.name, 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: array[0..10] of integer; （3）     x: integer; （4）     procedure readarray （5）     var i: integer; （6）     begin…a…end{readarray} （7）     procedure exchange(i,j:integer); （8）     begin （9）     x:=a[i]; a[i]:=a[j]; a[j]:=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）  begin…a… （16）  …v… （17）  …exchange(i,j); … （18）  end {partition}; （19）  begin… end {quicksort}; （20）  begin…end {sort}.

7.2 说 明 语 句 sort 空 表 头 a x readarray 指向readarray exchange 指向exchange quicksort 指向readarray partition v k readarrary i 指向exchange

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(id.name); if p  nil then 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(id.name); if p  nil then E.place := p else error }

7.3 赋 值 语 句 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 赋 值 语 句 二维数组 列为主 A[1, 1], A[2, 1], A[1, 2], A[2, 2], A[1, 3], A[2, 3]

7.3 赋 值 语 句 二维数组 列为主 A[1, 1], A[2, 1], A[1, 2], A[2, 2], A[1, 3], A[2, 3] 行为主 A[1, 1], A[1, 2], A[1, 3], A[2, 1], A[2, 2], A[2, 3]

7.3 赋 值 语 句 二维数组 列为主 A[1, 1], A[2, 1], A[1, 2], A[2, 2], A[1, 3], A[2, 3] 行为主 A[1, 1], A[1, 2], A[1, 3], A[2, 1], A[2, 2], A[2, 3] base + ( (i1  low1)  n2 + (i2  low2 ) )  w （其中n2 = high2  low2 + 1）

7.3 赋 值 语 句 二维数组 列为主 A[1, 1], A[2, 1], A[1, 2], A[2, 2], A[1, 3], A[2, 3] 行为主 A[1, 1], A[1, 2], A[1, 3], A[2, 1], A[2, 2], A[2, 3] base + ( (i1  low1)  n2 + (i2  low2 ) )  w （其中n2 = high2  low2 + 1） ( (i1  n2 ) + i2 )  w + (base  ( (low1  n2 ) + low2 )  w)

7.3 赋 值 语 句 多维数组 A[i1, 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 Elist  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; 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.array := 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, ‘:=’, 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 := L.place else begin E.place := newtemp; emit (E.place, ‘:=’, L.place, ‘[’, L.offset, ‘]’) end }

7.3 赋 值 语 句 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 } E  E1 + E2{E.place := newtemp; emit (E.place, ‘:=’, E1.place , ‘+’, E2.place) }

7.3 赋 值 语 句 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 } E  E1 + E2{E.place := newtemp; emit (E.place, ‘:=’, E1.place , ‘+’, E2.place) } E  (E1 ){E.place := E1.place }

7.3 赋 值 语 句 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 } E  E1 + E2{E.place := newtemp; emit (E.place, ‘:=’, E1.place , ‘+’, E2.place) } E  (E1 ){E.place := E1.place } S  L := E {if L.offset = null then / L是简单变量 / emit (L.place, ‘:= ’, E.place) else emit (L.place , ‘[’, L.offset, ‘]’, ‘:=’, E.place) }

7.3 赋 值 语 句 S := L.place := x L.offset := null x E.place := t4 L.place := t2 L.offset := t3 Elist.place := t1 Elist.ndim := 2 Elist.array := A , Elist.place := y Elist.ndim := 1 E.place := z L.place := z E.place := y L.place := y A [ z ] y x := A[ y, z ]的注释分析树

7.3 赋 值 语 句 S := L.place := x L.offset := null x E.place := t4 L.place := t2 L.offset := t3 Elist.place := t1 Elist.ndim := 2 Elist.array := A , Elist.place := y Elist.ndim := 1 E.place := z L.place := z E.place := y L.place := y A [ z ] y x := A[ y, z ]的注释分析树 t1 := y  20 t1 := t1 + z

7.3 赋 值 语 句 S := L.place := x L.offset := null x E.place := t4 L.place := t2 L.offset := t3 Elist.place := t1 Elist.ndim := 2 Elist.array := A , Elist.place := y Elist.ndim := 1 E.place := z L.place := z E.place := y L.place := y A [ z ] y x := A[ y, z ]的注释分析树 t2 :=A  84 t3 := 4  t1 t1 := y  20 t1 := t1 + z

7.3 赋 值 语 句 S := L.place := x L.offset := null x E.place := t4 L.place := t2 L.offset := t3 Elist.place := t1 Elist.ndim := 2 Elist.array := A , Elist.place := y Elist.ndim := 1 E.place := z L.place := z E.place := y L.place := y A [ z ] y x := A[ y, z ]的注释分析树 t4 := t2 [t3 ] t2 :=A  84 t3 := 4  t1 t1 := y  20 t1 := t1 + z

7.3 赋 值 语 句 S := L.place := x L.offset := null x E.place := t4 L.place := t2 L.offset := t3 Elist.place := t1 Elist.ndim := 2 Elist.array := A , Elist.place := y Elist.ndim := 1 E.place := z L.place := z E.place := y L.place := y A [ z ] y x := A[ y, z ]的注释分析树 x := t4 t4 := t2 [t3 ] t2 :=A  84 t3 := 4  t1 t1 := y  20 t1 := t1 + z

7.3 赋 值 语 句 7.3.5 类型转换 x := y + i  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 = real then begin u := newtemp; emit (u, ‘:=’, ‘inttoreal’, E1.place); emit (E.place, ‘:=’, u, ‘real+’, E2.place); E.type := real . . .

7.4 布尔表达式的翻译 布尔表达式有两个基本目的 计算逻辑值 在控制流语句中用作条件表达式

7.4 布尔表达式的翻译 布尔表达式有两个基本目的 计算逻辑值 在控制流语句中用作条件表达式 布尔表达式的完全计算 布尔表达式的“短路”计算 E1 or E2 定义成 if E1 then true else E2 E1 and E2 定义成 if E1 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 := 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 布尔表达式的翻译 表达式 演示Figure7_13 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 < 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.truelist:布尔表达式E生成的四元式中需回填真出口的四元式标号； E.falselist:布尔表达式E生成的四元式中需回填假出口的四元式标号；

7.4 布尔表达式的翻译 nextquad makelist(i) merge(p1,p2) backpatch(p,t)

7.4 布尔表达式的翻译 E  E1 or M E2 {backpatch(E1.falselist,M.quad); E.truelist:=merge(E1.truelist,E2.truelist); E.falselist:=E2.falselist;} E  id1 relop id2 E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(jrelop,id1.place,id2.place,0); emit(j,-,-,0);} 演示

7. 5 控制语句的翻译 7.5.1 控制流语句的翻译 S  if E then S1 | if E then S1 else S2 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.true E.code 跳向E.false E.true: S1.code . . . 7. 5 控制语句的翻译 E.code S1.code E.true: . . . 跳向E.true 跳向E.false (a) if-then E.false: goto S.next S2.code (b) if-then-else goto S.begin S.begin: (c) while-do S1.next: (d) S1; S2

7. 5 控制语句的翻译 S  if E then S1 {E.true := newlabel; E.false := S.next; 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 } E.code S1.code E.true: . . . 跳向E.true 跳向E.false (a) if-then

7. 5 控制语句的翻译 S  if E then S1 else S2 {E.true := newlabel; 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.true, ‘:’) || S1.code || gen(‘goto’, S.next) || gen(E.false, ‘:’) || S2.code} E.code S1.code E.true: . . . 跳向E.true 跳向E.false E.false: goto S.next S2.code (b) if-then-else

7. 5 控制语句的翻译 S  while E do S1 {S.begin:= newlabel; 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) } E.code S1.code E.true: . . . 跳向E.true 跳向E.false goto S.begin S.begin: (c) while-do

7. 5 控制语句的翻译 S  S1; S2 {S1.next := newlabel; S2.next := S.next; 7. 5 控制语句的翻译 S  S1; S2 {S1.next := newlabel; S2.next := S.next; S.code := S1.code || gen(S1.next, ‘:’) || S2.code } S1.code S2.code S1.next: . . . (d) S1; S2

使用回填技术一遍扫描翻译控制语句 S → if E then M1 S1 N else M2 S2 {backpatch(E.truelist,M1.quad); backpatch(E.falselist,M2.quad); S.nextlist:=merge(S1.nextlist,N.nextlist,S2.nextlist); N → ε {N.nextlist:=makelist(nextquad); emit(j,-,-,-)}

使用回填技术一遍扫描翻译控制语句 M → ε {M.quad:=nextquad;} S → if E then M S1 {backpatch(E.truelist,M.quad); S.nextlist:=merge(E.falselist,S1.nextlist);} S → while M1 E do M2 S1 M3 {backpatch(S1.nextlist,M1.quad); backpatch(E.turelist,M2.quad); backpatch(E.falselist,M3.quad+1); S.nextlist:=E.falselist; emit(j,-,-,M1.quad)}

演示Table7_8 P195的翻译模式能回填P196的第二个四元式么？

7. 5 控制语句的翻译 7.5.3 开关语句的翻译 switch E begin case V1: S1 case V2: S2 7. 5 控制语句的翻译 7.5.3 开关语句的翻译 switch E begin case V1: S1 case V2: S2 . . . case Vn - 1: Sn – 1 default: Sn end

7. 5 控制语句的翻译 分支数较少时 t := E的代码 | Ln-2: if t  Vn-1 goto Ln-1 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的代码 7. 5 控制语句的翻译 分支较多时，将分支测试的代码集中在一起， 便于生成较好的分支测试代码。 t := E的代码 | Ln: Sn的代码 goto test | goto next L1: 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 Ln Ln-1: Sn -1的代码 | next: goto next

7. 5 控制语句的翻译 中间代码增加一种case语句，便于代码生成器 对它进行特别处理 test: case V1 L1 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 emit（’param’ p）； emit （‘call’id.Place）} Elist  Elist, E {将E.Place加入到queeue的队尾} Elist  E {初始化queue仅包含E.place}

7.6 过程调用 过程调用id(E1, E2, …, En)的中间代码结构 E1.place := E1的代码 . . . En.place := En的代码 param E1.place param E2.place param En.place call id.place, n

7.6 过程调用 S  call id (Elist) {为长度为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 类型系统 变量的类型 变量在程序执行期间的取值范围 类型化语言 变量都被给定类型的语言 无类型语言 不限制变量值范围的语言 一个运算可以作用到任意的运算对象，其结果可能是一个有意义的值、一个错误、一个异常或一个未做说明的结果。

类型系统的根本目的是防止程序运行时出现执行错误 类型系统的形式化 类型表达式

一些实际使用的语言是弱类型化语言 Pascal语言 C语言 无标志的变体记录类型 函数型参数 有很多不安全的并且被广泛使用的特征，如： 指针算术运算 强制类型转换 参数个数可变

从工程的观点看，类型化语言有下面一些优点 开发的实惠 7.7.1.2 类型化语言的优点 从工程的观点看，类型化语言有下面一些优点 开发的实惠 较早发现错误 类型信息还具有文档作用

7.7.2 类型检查器的规格说明 一个简单的语言 P  D ; E 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  literal | num | id | E mod E | E [ E ] | E

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)}

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 类型检查器的规格说明 类型检查——声明语句 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 类型检查器的规格说明 类型表达式 基本类型 boolean, char, integer, real 构造类型 数组类型 array(I, T) 指针类型 pointer(T) 积类型 T1  T2 函数 T1  T2 类型表达式中还可以出现类型名字和类型变量

7.7.2 类型检查器的规格说明 表达式的类型检查 E  literal {E.type := char } E  num {E.type := integer} E  id {E.type := lookup(id.entry)}

7.7.2 类型检查器的规格说明 类型检查——表达式 E  truth {E.type := boolean } E  num {E.type := integer} E  id {E.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 = integer and E1. type = array(s, t) then t else type_error } E  E1 {E.type := if E1.type = pointer(t) then t

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 E  E1 (E2 ) {E. type := if E2 . type = s and E1. type = s  t then t

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 = boolean then S1. type

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 void

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 = integer else if E1.type = real and E2.type = real else type_error }

7.7.3 函数和运算符的重载 重载符号 有多个含义，但在引用点的含义都是唯一的 例如 加法算符+可用于不同类型，是不同的函数 7.7.3 函数和运算符的重载 重载符号 有多个含义，但在引用点的含义都是唯一的 例如 加法算符+可用于不同类型，是不同的函数 在Ada中，( ) 是重载的，A( I ) 有不同含义

7.7.3函数和运算符的重载 子表达式的可能类型集合 例 Ada语言 声明： function “ ” (i, j : integer ) return complex; function “ ” (x, y : complex ) return complex; 使得算符重载，可能的类型包括： integer  integer  integer integer  integer  complex complex  complex  complex

7.7.3函数和运算符的重载 子表达式的可能类型集合 例 Ada语言 声明： function “ ” (i, j : integer ) return complex; function “ ” (x, y : complex ) return complex; 使得算符重载，可能的类型包括： integer  integer  integer 2  (3  5) integer  integer  complex complex  complex  complex

7.7.3函数和运算符的重载 子表达式的可能类型集合 例 Ada语言 声明： function “ ” (i, j : integer ) return complex; function “ ” (x, y : complex ) return complex; 使得算符重载，可能的类型包括： integer  integer  integer 2  (3  5) integer  integer  complex (3  5)  z complex  complex  complex z是复型

7.7.3函数和运算符的重载 以函数作用为例，考虑类型检查 在每个表达式都有唯一的类型时，函数作用 的类型检查是： EE1 (E2 ) {E. type := if E2. type = s and E1. type = s  t then t else type_ error }

7.7.3函数和运算符的重载 确定表达式可能类型的集合 产 生 式 语 义 规 则 E  E E.types := E. types 产 生 式 语 义 规 则 E  E E.types := E. types E  id E. types := lookup(id. entry) E  E1 (E2) E. types := {t | E2. types中存在一个s，使得s  t属于E1.types }

7.7.4 多态函数 7.7.3.1 为什么要使用多态函数 例：用Pascal语言写不出求表长度的通用程序 type link = cell ; cell = record info : integer; next : link end;

7.7.4 多 态 函 数 function length(lptr : link) : integer; var len : integer; begin len := 0; while lptr <> nil do begin len := len + 1; lptr := lptr. next end; length := len

7.7.4 多 态 函 数 用ML语言很容易写出求表长度的程序而不必管表元的类型。 fun length (lptr) = if null (lptr) then 0 else length (tl (lptr)) + 1;

7.7.4 多 态 函 数 用ML语言很容易写出求表长度的程序而不必管表元的类型。 fun length (lptr) = if null (lptr) then 0 else length (tl (lptr)) + 1; length ( [“sun”, “mon”, “tue”] ) length ( [10, 9, 8 ] ) 都等于3

7.7.4 多 态 函 数 多态函数 允许变元有不同的类型

7.7.4 多 态 函 数 多态函数 允许变元有不同的类型 体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）

7.7.4 多 态 函 数 多态函数 多态算符 允许变元有不同的类型 体中的语句可以在变元类型不同的情况下执行（区别于重载的特征） 用于以不同类型的变元执行的代码段

7.7.4 多 态 函 数 多态函数 多态算符 允许变元有不同的类型 体中的语句可以在变元类型不同的情况下执行（区别于重载的特征） 用于以不同类型的变元执行的代码段 例如：数组索引

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

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

7.7.4 多 态 函 数 多态函数 多态算符 允许变元有不同的类型 体中的语句可以在变元类型不同的情况下执行（区别于重载的特征） 用于以不同类型的变元执行的代码段 例如：数组索引、函数作用、通过指针间接访问 C语言手册中关于指针&的论述是： 如果运算对象的类型是‘…’，那么结果类型是指向‘…’的指针”。

7.7.4 多 态 函 数 类型变量 length的类型可以写成.list()  integer 允许类型变量出现在类型表达式中，还便于我们讨论未知类型 在不要求标识符的声明先于使用的语言中，通过类型变量的使用去确定程序变量的类型。

7.7.4 多 态 函 数 一个含多态函数的语言 P  D; 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.4 多 态 函 数 代换、实例和合一 代换: 类型表达式中的类型变量用其所代表的类型表达式去替换

7.7.4 多 态 函 数 代换、实例和合一 代换: 类型表达式中的类型变量用其所代表的类型表达式去替换 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.4 多 态 函 数 实例 把subst函数用于t后所得的类型表达式是t的一个实例，用S (t)表示。 例子（s < t 表示s是t 的实例） pointer ( integer ) < pointer ( ) pointer ( real ) < pointer ( ) integer  integer <   pointer ( ) <   < 

7.7.4 多 态 函 数 下面左边的类型表达式不是右边的实例 integer real 代换不能用于基本类型  的代换不一致 integer      的所有出现都应该代换

7.7.4 多 态 函 数 合一 如果存在某个代换S使得S (t1) = S (t2)，那么这两个表达式t1和t2能够合一 最一般的合一代换 对任何其它满足S(t1) = S(t2)的代换S，代换S(t1)是S (t1)的实例

7.7.4 多 态 函 数 多态函数的类型检查 多态函数和普通函数在类型检查上有很大区别 (1)同一多态函数的不同出现无须变元有相同类型 apply: o derefo:pointer(o)  o apply : i derefi : pointer(i)  i q: pointer(pointer(integer)) deref(deref (q ))的带标记的语法树

7.7.4 多 态 函 数 (2)必须把类型相同的概念推广到类型合一 apply: o derefo:pointer(o)  o apply : i derefi : pointer(i) i q: pointer(pointer(integer)) deref(deref (q ))的带标记的语法树

7.7.4 多 态 函 数 (2)必须把类型相同的概念推广到类型合一 (3)要记录表达式合一的结果 apply: o derefo:pointer(o)  o apply : i derefi :pointer(i)  i q: pointer(pointer(integer)) deref(deref (q ))的带标记的语法树

本 章 要 点 中间代码的几种形式，它们之间的相互转换 符号表的组织和作用域信息的保存 数组元素定址的翻译方案，布尔表达式的两种不同实现方式 本 章 要 点 中间代码的几种形式，它们之间的相互转换 符号表的组织和作用域信息的保存 数组元素定址的翻译方案，布尔表达式的两种不同实现方式 赋值语句和各种控制流语句的中间代码格式和生成中间代码的翻译方案 过程调用的中间代码格式和生成中间代码的翻译方案