编译原理课件：第六章 类 型 检 查

1、 计算机科学与技术学院计算机科学与技术学院编译原理编译原理Compilers Principles, Techniques and Tools第六章第六章 类类 型型 检检 查查 本章内容本章内容静态检查中最典型的部分静态检查中最典型的部分 类型检查类型检查v设计语法制导的类型检查器设计语法制导的类型检查器忽略其它的静态检查：忽略其它的静态检查：控制流检查、唯一性检查、控制流检查、唯一性检查、关联名字检查关联名字检查语法语法分析分析器器类型类型检查检查器器中间中间代码代码生成生成器器语 法语 法树树语 法语 法树树中间中间表示表示记号记号流流简单类型检查器的说明简单类型检查器的说明类型检查类型

2、检查声明语句声明语句D D; DD id : T addtype (id.entry, T.type)addtype：把类型信息填入符号表：把类型信息填入符号表简单类型检查器的说明简单类型检查器的说明类型检查类型检查声明语句声明语句D D; DD id : T addtype (id.entry, T.type)T boolean T.type = booleanT integer T.type = integerT T1 T.type = pointer(T1.type)简单类型检查器的说明简单类型检查器的说明类型检查类型检查声明语句声明语句D D; DD id : T addtype (i

3、d.entry, T.type)T boolean T.type = booleanT integer T.type = integerT T1 T.type = pointer(T1.type)T array num of T1 T.type = array(num.val, T1.type)简单类型检查器的说明简单类型检查器的说明类型检查类型检查声明语句声明语句D D; DD id : T addtype (id.entry, T.type)T boolean T.type = booleanT integer T.type = integerT T1 T.type = pointer(T

4、1.type)T array num of T1 T.type = array(num.val, T1.type)T T1 T2 T.type = T1.type T2.type 简单类型检查器的说明简单类型检查器的说明类型检查类型检查表达式表达式E truthE.type = boolean E numE.type = integerE idE.type = lookup(id.entry)简单类型检查器的说明简单类型检查器的说明类型检查类型检查表达式表达式E truthE.type = boolean E numE.type = integerE idE.type = lookup(id.

5、entry)E E1 mod E2E.type = if E1.type = integer and E2. type = integer then integer else type_error 简单类型检查器的说明简单类型检查器的说明类型检查类型检查表达式表达式E E1 E2 E.type = if E2. type = integer and E1. type = array(s, t) then t else type_error 简单类型检查器的说明简单类型检查器的说明类型检查类型检查表达式表达式E E1 E2 E.type = if E2. type = integer and E

6、1. 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 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 (E2 )

7、 E. type = if E2 . type = s and E1. type = s t then t else type_error 简单类型检查器的说明简单类型检查器的说明类型检查类型检查语句语句S id := E if (id.type = E.type & E.type boolean, integer) S.type = void; else S.type = type_error; 简单类型检查器的说明简单类型检查器的说明类型检查类型检查语句语句S id := E if (id.type = E.type & E.type boolean, integer) S

8、.type = void; else S.type = type_error; S if E then S1 S. type = if E. type = booleanthen S1. type else type_error 简单类型检查器的说明简单类型检查器的说明类型检查类型检查语句语句S while E do S1S.type = if E.type = boolean then S1. type else type_error 简单类型检查器的说明简单类型检查器的说明类型检查类型检查语句语句S while E do S1S.type = if E.type = boolean the

9、n S1. type else type_error S S1; S2S. type = if S1. type = void andS2. type = void then voidelse type_error 简单类型检查器的说明简单类型检查器的说明类型检查类型检查程序程序P D; S P. type = if S. type = void then voidelse type_error 简单类型检查器的说明简单类型检查器的说明类型转换类型转换E E1 op E2E.type =if E1.type = integer and E2.type = integerthen integer

10、else if E1.type = integer and E2.type = realthen realelse if E1.type = real and E2.type = integerthen realelse if E1.type = real and E2.type = realthen realelse type_error 第七章第七章 中间代码生成中间代码生成本章内容本章内容介绍几种常用的中间表示介绍几种常用的中间表示：后缀表示、图形表示后缀表示、图形表示和三地址代码和三地址代码用语法制导定义和翻译方案来说明源语言的各种用语法制导定义和翻译方案来说明源语言的各种构造怎样被翻

11、译成中间形式构造怎样被翻译成中间形式 分析分析器器静态静态检查检查器器中间中间代码代码生成生成器器中间中间代码代码记号记号流流代码代码生成生成器器7.1 中中 间间 语语 言言7.1.1 后缀表示后缀表示 E E op E | uop E | (E) | id | num表达式表达式E的的后缀表示后缀表示可以如下归纳定义：可以如下归纳定义：表达式表达式E后缀式后缀式E id idnumnumE1 op E2E1 E2 opuop EE uop(E) E 7.1 中中 间间 语语 言言v后缀表示不需要括号后缀表示不需要括号(8 5) + 2 的后缀表示是的后缀表示是8 5 2 + v后缀表示的最

12、大优点是便于计算机处理表达后缀表示的最大优点是便于计算机处理表达式式计算栈计算栈输入串输入串8 5 2 +8 5 2 +8 5 2 +3 2 +3 2 +57.1 中中 间间 语语 言言7.1.2 图形表示图形表示v语法树是一种图形化的中间表示语法树是一种图形化的中间表示v有向无环图有向无环图也是一种中间表示也是一种中间表示 assigna+ bcduminus(b) DAGassigna+ bcdcduminus(a) 语法树语法树 a = ( b + c d) + c d的图形表示的图形表示7.1 中中 间间 语语 言言构造赋值语句语法树的语法制导定义构造赋值语句语法树的语法制导定义产产

13、生生 式式 语语 义义 规规 则则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 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 三地址代码三地址代

14、码一般形式：一般形式：x = y op zv例例 表达式表达式x + y z翻译成的三地址语句序列翻译成的三地址语句序列是是t1 = y z t2 = x + t1 7.1 中中 间间 语语 言言v三地址代码是语法树或三地址代码是语法树或DAG的一种线性表示的一种线性表示v例例 a = ( b + c d ) + c d语法树的代码语法树的代码t1 = bt2 = c dt3 = t1 + t2t4 = c dt5 = t3 + t4a = t5assigna+ bcdcduminus7.1 中中 间间 语语 言言v三地址代码是语法树或三地址代码是语法树或DAG的一种线性表示的一种线性表示v例

15、例 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 = t5assigna+ bcduminus7.1 中中 间间 语语 言言本书常用的三地址语句本书常用的三地址语句v赋值语句赋值语句x = y op z， x = op y， x = yv无条件转移无条件转移goto Lv条件转移条件转移if x relop y goto Lv过程调用过程调用param x 和和call p

16、 , nv过程返回过程返回 return yv索引赋值索引赋值x = yi和和 xi = yv地址和指针赋值地址和指针赋值x = &y，x = y和和 x = y7.2 声声 明明 语语 句句本节介绍本节介绍v为局部名字建立符号表条目为局部名字建立符号表条目v为它分配存储单元为它分配存储单元v符号表中包含名字的类型和分配给它的存储符号表中包含名字的类型和分配给它的存储单元的相对地址等信息单元的相对地址等信息7.2 声声 明明 语语 句句7.2.1 过程中的声明过程中的声明7.2 声声 明明 语语 句句计算被声明名字的类型和相对地址计算被声明名字的类型和相对地址P offset = 0D

17、; SD D ; D D id : T enter ( id.lexeme, 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 T1T.type = array (num.val, T1.type);T.width = num.val T1.widthT T1 T.type = pointer (T1.type); T.width = 4 7.2 声声 明明 语语 句句计算被声明名字的

18、类型和相对地址计算被声明名字的类型和相对地址P offset = 0D; SD D ; D D id : T enter ( id.lexeme, 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 T1T.type = array (num.val, T1.type);T.width = num.val T1.widthT T1 T.type = pointer (T1.type);

19、T.width = 4 7.2 声声 明明 语语 句句7.2.2 作用域信息的保存作用域信息的保存v所讨论语言的文法所讨论语言的文法P D; SD D ; D | id : T | proc id ; D ; S sort var a:; x:; readarray var i:; exchange quicksort var k, v:; partition var i, j:;7.2 声声 明明 语语 句句exchangereadarrayxa表表 头头空空sortquicksort指向指向readarraypartitionvk表表 头头quicksortreadarrayi表表 头头e

20、xchange表表 头头指向指向exchangepartition sort readarray exchange quicksort partition符号表实例符号表实例 7.2 声声 明明 语语 句句v符号表的特点符号表的特点各过程有各自的符号表各过程有各自的符号表符号表之间有双向链符号表之间有双向链构造符号表时需要符号表栈构造符号表时需要符号表栈构造符号表需要活动记录栈构造符号表需要活动记录栈v语义动作用到的函数语义动作用到的函数mkTable(previous)enter(table, name, type, offset) addWidth(table, width)enterPr

21、oc(table, name, newtable)sort var a:; x:; readarray var i:; exchange quicksort var k, v:; partition var i, j:;7.2 声声 明明 语语 句句P M D; S 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);add

22、Width(t, top(offset) ); pop(tblptr); pop(offset);enterProc(top(tblptr), id.lexeme, t) Did :T enter(top(tblptr), id.lexeme, T.type, top(offset); top(offset) = top(offset) + T.width N t = mkTable(top(tblptr) ); push(t, tblptr); push(0, offset) 7.2 声声 明明 语语 句句P M D; S addWidth (top (tblptr), top (offse

23、t); 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(offset) ); pop(tblptr); pop(offset);enterProc(top(tblptr), id.lexeme, t) Did :T enter(top(tblptr), id.lexeme, T.type, top(offset); top(offset) = top(offset

24、) + T.width N t = mkTable(top(tblptr) ); push(t, tblptr); push(0, offset) 7.2 声声 明明 语语 句句P M D; S 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(offset) ); pop(tblptr);

25、 pop(offset);enterProc(top(tblptr), id.lexeme, t) Did :T enter(top(tblptr), id.lexeme, T.type, top(offset); top(offset) = top(offset) + T.width N t = mkTable(top(tblptr) ); push(t, tblptr); push(0, offset) 7.3 赋赋 值值 语语 句句7.3.1 符号表中的名字符号表中的名字S id := E p = lookup(id.lexeme);if p != nil thenemit ( p, =

26、, E.place)else error E E1 + E2E.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.lexeme);if p != nil then E.place = p else error 第八章第八章 代代 码码 生生 成成

27、 本章内容本章内容v一个简单的代码生成算法一个简单的代码生成算法v涉及存储管理，指令选择，寄存器分配和计涉及存储管理，指令选择，寄存器分配和计算次序选择算次序选择等基本问题等基本问题前端代 码 优 化 器中间代码源程序代码生成器中间代码目标程序8.1 代码生成器的设计中的问题代码生成器的设计中的问题8.1.1 目标程序目标程序v绝对机器语言程序绝对机器语言程序目标程序将装入到内存的固定地方目标程序将装入到内存的固定地方v可重定位目标模块可重定位目标模块代码中含重定位信息，以适应重定位要求代码中含重定位信息，以适应重定位要求8.1 代码生成器的设计中的问题代码生成器的设计中的问题8.1.1 目标

28、程序目标程序v绝对机器语言程序绝对机器语言程序目标程序将装入到内存的固定地方目标程序将装入到内存的固定地方v可重定位目标模块可重定位目标模块代码中含重定位信息，以适应重定位要求代码中含重定位信息，以适应重定位要求允许程序模块分别编译允许程序模块分别编译调用其它先前编译好的程序模块调用其它先前编译好的程序模块8.1 代码生成器的设计中的问题代码生成器的设计中的问题8.1.1 目标程序目标程序v绝对机器语言程序绝对机器语言程序v可重定位目标模块可重定位目标模块代码中含重定位信息，以适应重定位要求代码中含重定位信息，以适应重定位要求允许程序模块分别编译允许程序模块分别编译调用其它先前编译好的程序模块

29、调用其它先前编译好的程序模块v汇编语言程序汇编语言程序免去编译器重复汇编器的工作免去编译器重复汇编器的工作从教学角度，增加可读性从教学角度，增加可读性8.1 代码生成器的设计中的问题代码生成器的设计中的问题8.1.2 指令的选择指令的选择v目标机器指令系统的性质决定了指令选择的目标机器指令系统的性质决定了指令选择的难易程度，指令系统的统一性和完备性是重难易程度，指令系统的统一性和完备性是重要的因素要的因素v指令的速度和机器特点是另一些重要的因素指令的速度和机器特点是另一些重要的因素8.1 代码生成器的设计中的问题代码生成器的设计中的问题v若不考虑目标程序的效率，指令的选择是直截了当若不考虑目标

30、程序的效率，指令的选择是直截了当的的v例例 三地址语句三地址语句x = y + z (x x，y y和和z z都静态分配都静态分配) )MOVy,R0/ 把把y装入寄存器装入寄存器R0 /ADDz,R0 / 把把z加到加到R0上上 /MOVR0,x / 把把R0存入存入x中中 /逐条语句地产生代码，常常得到低质量的代码逐条语句地产生代码，常常得到低质量的代码 8.1 代码生成器的设计中的问题代码生成器的设计中的问题语句序列语句序列 a = b + c d = a + e的代码如下的代码如下MOV b,R0ADDc,R0MOVR0, aMOVa,R0ADDe,R0MOVR0, d8.1 代码生成

31、器的设计中的问题代码生成器的设计中的问题语句序列语句序列 a = b + c d = a + e的代码如下的代码如下MOV b,R0ADDc,R0MOVR0, aMOVa,R0 多余的指令多余的指令ADDe,R0MOVR0, d8.1 代码生成器的设计中的问题代码生成器的设计中的问题语句序列语句序列 a = b + c d = a + e的代码如下的代码如下MOV b,R0ADDc,R0MOVR0, aMOVa,R0 多余的指令多余的指令ADDe,R0 若若a不再使用，不再使用，MOVR0, d 第三条指第三条指令令也也多余多余8.1 代码生成器的设计中的问题代码生成器的设计中的问题8.1.3

32、 寄存器分配寄存器分配运算对象处于寄存器和处于内存相比，指令运算对象处于寄存器和处于内存相比，指令要短一些，执行也快一些要短一些，执行也快一些v寄存器分配寄存器分配选择驻留在寄存器中的一组变量选择驻留在寄存器中的一组变量v寄存器指派寄存器指派挑选变量要驻留的具体寄存器挑选变量要驻留的具体寄存器8.2 目目 标标 机机 器器 8.2.1 目标机器的指令系统目标机器的指令系统v选择可作为几种微机代表的寄存器机器选择可作为几种微机代表的寄存器机器v四个字节组成一个字，有四个字节组成一个字，有n个通用寄存器个通用寄存器R0, ,R1, , ,Rn-1v二地址指令：二地址指令： op 源，目的源，目的M

33、OV源传到目的源传到目的ADD源加到目的源加到目的SUB目的减去源目的减去源 8.2 目目 标标 机机 器器 v地址模式和它们的汇编语言形式及附加代价地址模式和它们的汇编语言形式及附加代价模式模式 形式形式地址地址 附加代价附加代价绝对地址绝对地址 M M 1寄存器寄存器 R R 0变址变址 c(R)c + contents(R) 1间接寄存器间接寄存器 Rcontents(R) 0间接变址间接变址 c(R)contents(c + contents(R) 1 直接量直接量 #cc 1 8.2 目目 标标 机机 器器 v例例 指令实例指令实例MOVR0,MMOV4(R0),M4(R0)的值：的

34、值：contents(4 + contents(R0) MOV 4(R0),M 4(R0)的值：的值：contents(contents(4 + contents(R0)MOV#1,R08.2 目目 标标 机机 器器 8.2.2 指令的代价指令的代价v指令代价简化为指令代价简化为1 + + 指令的源和目的地址模式的附加代价指令的源和目的地址模式的附加代价8.2 目目 标标 机机 器器 v地址模式和它们的汇编语言形式及附加代价地址模式和它们的汇编语言形式及附加代价模式模式 形式形式地址地址 附加代价附加代价绝对地址绝对地址 M M 1寄存器寄存器 R R 0变址变址 c(R)c + conten

35、ts(R) 1间接寄存器间接寄存器 Rcontents(R) 0间接变址间接变址 c(R)contents(c + contents(R) 1 直接量直接量 #cc 1 8.2 目目 标标 机机 器器 8.2.2 指令的代价指令的代价v指令代价简化为指令代价简化为1 + + 指令的源和目的地址模式的附加代价指令的源和目的地址模式的附加代价指令指令代价代价MOV R0，R11MOV R5，M 2ADD #1，R32SUB 4(R0), 12(R1) 38.3 基本块和流图基本块和流图v怎样为三地址语句序列生成目标代码？怎样为三地址语句序列生成目标代码？先给出本节用例先给出本节用例prod = 0

36、;i = 1; do prod = prod + ai bi; i = i +1; while (i = 20); 其三地址代码见右边其三地址代码见右边 (1)prod = 0(2) i = 1(3) t1 = 4 i(4) t2= at1(5) t3 = 4 i(6) t4 = bt3(7) t5 = t2 t4(8) t6 = prod + t5(9) prod = t6(10) t7 = i +1(11) i = t7(12) if i = 20 goto (3) 8.3 基本块和流图基本块和流图8.3.1 基本块基本块v基本块基本块连续连续的语句序列，控的语句序列，控制流从它的开始进入

37、，制流从它的开始进入，并从它的末尾离开并从它的末尾离开v流图流图再用再用有向边表示基本块有向边表示基本块之间的控制流信息，就之间的控制流信息，就能得到程序的流图能得到程序的流图(1)prod = 0(2) i = 1(3) t1 = 4 i(4) t2= at1(5) t3 = 4 i(6) t4 = bt3(7) t5 = t2 t4(8) t6 = prod + t5(9) prod = t6(10) t7 = i +1(11) i = t7(12) if i = 20 goto (3) 8.3 基本块和流图基本块和流图(1)prod = 0 (2)i = 1 (3)t1 = 4 i (4

38、)t2= at1 (5 )t3 = 4 i (6 )t4 = bt3 (7 )t5 = t2 t4 (8 )t6 = prod + t5(9 )prod = t6(10) t7 = i +1(11) i = t7(12 ) if i = 20 goto (3) (1)prod = 0(2) i = 1(3) t1 = 4 i(4) t2= at1(5) t3 = 4 i(6) t4 = bt3(7) t5 = t2 t4(8) t6 = prod + t5(9) prod = t6(10) t7 = i +1(11) i = t7(12) if i = 20 goto (3) B1B2一个简单

39、的代码生成器一个简单的代码生成器v为单个块生成代码为单个块生成代码依次考虑三地址指令依次考虑三地址指令进行寄存器组织和管理（最大限度地利用）进行寄存器组织和管理（最大限度地利用）v执行一个运算时，部分或全部分量在寄存器中执行一个运算时，部分或全部分量在寄存器中v寄存器存放单个组块内的临时变量寄存器存放单个组块内的临时变量v寄存器可以存放全局值寄存器可以存放全局值v运行时刻的存储管理运行时刻的存储管理一个简单的代码生成器一个简单的代码生成器v为单个块生成代码为单个块生成代码每个寄存器都有寄存器描述符每个寄存器都有寄存器描述符v跟踪哪些变量的当前值存放在此寄存器跟踪哪些变量的当前值存放在此寄存器每

40、个变量都有地址描述符每个变量都有地址描述符v跟踪哪些位置上可找到该变量的当前值。位置可以跟踪哪些位置上可找到该变量的当前值。位置可以指一个寄存器、一个内存地址、一个栈中的位置指一个寄存器、一个内存地址、一个栈中的位置t=a-b LD R1, a LD R2, b SUB R2,R1, R2abcdR1 R2 R3a b c d t u vata,R1bcdR2一个简单的代码生成器一个简单的代码生成器v代码生成算法代码生成算法getReg(I)：为每个与三地址指令：为每个与三地址指令I有关的内存有关的内存位置选择寄存器位置选择寄存器运算的机器指令：运算的机器指令：x = y + zvgetReg

41、(x=y+z)为为x、y、z选择寄存器，记为选择寄存器，记为Rx、Ry、Rzv如果如果y不在不在Ry的寄存器描述符中，则生成指令的寄存器描述符中，则生成指令“LD Ry, y”，其中，其中y是存放是存放y的内存位置之一的内存位置之一(y可以根可以根据据y的地址描述符得到的地址描述符得到)。vz的处理跟的处理跟y的处理类似的处理类似v生成指令生成指令“ADD Rx, Ry, Rz”一个简单的代码生成器一个简单的代码生成器v代码生成算法代码生成算法管理寄存器和地址描述符管理寄存器和地址描述符vLD R, x修改修改R的寄存器描述符，使之只包含的寄存器描述符，使之只包含x把把R加入到加入到x的地址描

42、述符中的地址描述符中从任何不同于从任何不同于x的变量的地址描述符中删除的变量的地址描述符中删除R一个简单的代码生成器一个简单的代码生成器v代码生成算法代码生成算法管理寄存器和地址描述符管理寄存器和地址描述符vADD Rx, Ry, Rz改变改变Rx的寄存器描述符，使之只包含的寄存器描述符，使之只包含x改变改变x的地址描述符，使之只包含的地址描述符，使之只包含Rx从任何不同于从任何不同于x的变量的地址描述符中删除的变量的地址描述符中删除Rx一个简单的代码生成器一个简单的代码生成器v代码生成算法代码生成算法t=a-b LD R1, a LD R2, b SUB R2,R1, R2abcdR1 R2

43、 R3a b c d t u vata,R1bcdR2t=a-bu=a-cv=t+ua=dd=v+u一个简单的代码生成器一个简单的代码生成器v代码生成算法代码生成算法t=a-b LD R1, a LD R2, b SUB R2,R1, R2abcdR1 R2 R3a b c d t u vata,R1bcdR2t=a-bu=a-cv=t+ua=dd=v+uu=a-c LD R3, c SUB R1, R1, R3utcabc,R3dR2R1一个简单的代码生成器一个简单的代码生成器v代码生成算法代码生成算法t=a-b LD R1, a LD R2, b SUB R2,R1, R2abcdR1 R2 R3a b c d t u vata,R1bcdR2t=a-bu=a-cv=t+ua=dd=v+uu=a-c LD R3, c SUB R1, R1, R3v=t+u ADD R3, R2, R1utcabc,R3dR2R1utvabcdR2R1R3.一个简单的代码生成器一个简单的代码生成器v代码生成算法