第八章静态语义分析和中间代码生成-4.ppt

1、第八章 静态语义分析和中间代码生成,学习目标： 掌握： 语法制导的语义分析 常见的中间代码形式； 常见语法成分的属性文法或翻译方案 理解：,静态语义分析和中间代码生成,语法制导翻译方法 使用属性文法/翻译模式为描述工具定义程序设计语言的语义及代码生成方法。 语义分析 在处理程序的声明部分时构造标识符的符号表 在处理程序的语句部分时完成静态语义检查,静态语义分析和中间代码生成,8.1 符号表 8.2 静态语义分析 8.3 中间代码生成 8.4 多遍的方法,符号表,符号表及其作用 符号表(Symbol Table) 符号表是存放标识符信息的一种表，其中的信息是标识符的属性(语义)。 如：种类，类型

2、，偏移地址，占用空间等,符号表,符号表的作用 符号表是连接声明与引用的桥梁。一个名字在声明时，相关信息被填写进符号表，而在引用时，根据符号表中的信息进行语义检查，进而生成中间代码。它的作用主要有： 辅助语义的正确性检查 辅助代码生成,符号表的设计 如何有效记录各类符号的属性，以便在编译的各个阶段对符号表进行快速、有效的查找、插入、修改、删除等操作，是符号表设计的基本目标。 符号表的组成 表项分两部分，其中前者是标识符的名字，而后者是属性部分（不同种类的标识符属性不同）。 符号表的组织方式和查找方法 符号表的组织方式可以是数组也可以是链表等等 查找算法可以是顺序查表法、平分查表法、散列查表法等

3、合理的组织和查找，将使得符号表的操作更高效,过程的说明部分： CONST A=35,B=49; VAR C,D,E; PROCEDURE P; VAR G,符号表中的信息,变量相对本过程基地址的偏移量,符号表,符号表的生存期 在编译过程中，每当遇到标识符时，就要查填符号表： 若是新的标识符时，就向符号表中填入一个新的表项； 否则，根据情况向符号表中的已有表项增填信息（如填入存储地址）或者查获信息（如进行语义检查等） 符号表的信息将在词法分析、语法分析的过程中陆续填入，将用于语义检查、中间代码生成以及目标代码生成等不同的阶段。,与语义分析相关的工作,8.2 静态语义分析,静态语义检查 编译期间所

4、进行的语义检查 动态语义检查 所生成的代码在运行期间进行的语义检查 收集语义信息 为语义检查收集程序的语义信息 为代码生成等后续阶段收集程序的语义信息,代码生成前程序合法性检查的最后阶段 控制流检查 控制流语句必须使控制转移到合法的地方（如 跳转语句要有合法的跳转目标，break 语句必须有合法的语句包围它） 唯一性检查 很多场合要求对 象只能被定义一次（如枚举类型的元素不能重复出现）,1 静态语义分析的主要任务,代码生成前程序合法性检查的最后阶段 名字的上下文相关性检查 例如：变量在使用前必须声明；在外部不能访问私有变量；名字的定义和使用之间要满足一定的上下文相关性 类型检查 检查每个操作是

5、否遵守语言类型系统的定义,1 静态语义分析的主要任务,类型检查程序（type checker）负责类型检查 验证程序的结构是否匹配上下文所期望的类型 为代码生成阶段搜集及建立必要的类型信息 实现某个类型系统（type system）,2 类型检查,一个简单语言的上下文无关文法GP ：,2 类型检查,类型表达式（type expressions） 为程序单元的类型进行解释 由基本类型，类型名字，类型变量，及类型构造子 （type constructor）通过归纳定义得到的表达式 类型系统（type systems） 将类型表达式赋给程序各个部分的规则集合,类型表达式和类型系统,2 类型检查,类型

6、表达式分四类定义 基本数据类型表达式，积类型表达式，过程类型表达式， 专用类型表达式 基本数据类型表达式 纯量类型表达式：bool, int, real 有界数组类型表达式：array(I,T) T bool, int, real ；I 代表一个整数区间，如 1.10 指针数据类型表达式：pointer(T) T bool, int, real 指向类型为T的对象的指针类型,类型表达式 举例,积类型表达式 T1, T2, , Tn 为上述数据类型表达式；若n=0，则表示为 过程类型表达式 fun（T） T 是上述积类型表达式 专用类型表达式 type_error 专用于有类型错误的程序单元 o

7、k 专用于没有类型错误的程序单元,类型表达式 举例 (续),语法制导的方法可实现语言的一个类型系统 将类型表达式作为属性值赋给程序各个部分 设计实现类型检查的属性文法/翻译模式,类型检查程序的设计,2 类型检查,处理声明的翻译模式 作用：计算变量声明相关语法单位的类型信息，并保存标识符的类型信息到符号表,语法制导的类型检查程序 举例-1,V V1 ; T L.in := T.type L V.type := make_product_3 (V1.type, T.type, L.num) V V.type := T boolean T.type := bool ,T integer T.type

8、 := int T real T.type := real,make_product_3 (, type2, n) 生成积类型表达式（含n个type2）,处理声明的翻译模式,语法制导的类型检查程序 举例-2,T array num of T1 T.type := array(1. num.lexval, T1.type) T T1 T.type := pointer(T1.type) L L1.in := L.in L1, id addtype(id.entry, L.in) ; L.num := L1.num +1 L id addtype(id.entry, L.in); L.num :=

9、 1 ,L.in为继承属性 T.type， V.type，L.num为综合属性,处理声明的翻译模式 例：;int x,y,z,语法制导的类型检查程序,处理表达式的翻译模式 作用：计算表达式相关语法单位的类型信息，同时检查表达式运算数类型与给定运算是否兼容,语法制导的类型检查程序 举例-3,E true E.type := bool E false E.type := bool E int E.type := int E real E.type := real E id E.type := if lookup_type() = nil then type_error else lo

10、okup_type( ,E E1 op E2 E.type := if E1.type=real and E2.type=real then real else if E1.type=int and E2.type=int then int else type_error E E1 rop E2 E.type := if E1.type=real and E2.type=real then bool else if E1.type=int and E2.type=int then bool else type_error E E1 E2 E.type := if E2.type=

11、 int 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 ,语法制导的类型检查程序 举例-4,处理语句的翻译模式,语法制导的类型检查程序 举例-5,S id := E S.type := if lookup_type (id.entry) = E.type then ok else type_error S if E then S1 S.type := if E.type=bool then S1.type else type_

12、error S if E then S1 else S2 S.type := if E.type=bool and S1.type = ok and S2.type = ok then ok else type_error ,处理语句的翻译模式,语法制导的类型检查程序 举例-6,S while E then S1 S.type := if E.type=bool then S1.type else type_error S S1 ; S2 S.type := if S1.type = ok and S2.type = ok then ok else type_error S break S.t

13、ype := ok ,8.3 中间代码生成,定义： 中间代码是复杂性介于源程序语言和机器语言之间的一种表示形式。 作用 源语言和目标语言之间的桥梁，避开二者之间较大的语义跨度，使编译程序的逻辑结构更加简单明确 利于编译程序的重定向 利于进行与目标机无关的优化,1 常见的中间代码表示形式,有不同层次不同目的之分 中间代码举例 AST（Abstract syntax tree，抽象语法树） TAC（Three-address code,三地址码，四元式） P-code （特别用于 Pasal 语言实现） Bytecode（Java 编译器的输出, Java 虚拟机的输入）,例：算术表达式 A +

14、B * ( C - D ) + E / ( C - D ) N AST（抽象语法树）表示,+,+,/,A,*,E,-,B,D,C,-,D,C,N,1 常见的中间代码表示形式,例：算术表达式 A + B * ( C - D ) + E / ( C - D ) N TAC （三地址码）表示 (1) ( - C D T1 ) T1 := C - D (2) ( * B T1 T2) T2 := B * T1 (3) ( + A T2 T3) T3 := A + T2 (4) ( - C D T4) 或 T4 := C - D (5) ( T4 N T5) T5 := T4 N (6) ( / E T

15、5 T6) T6 := E / T5 (7) (+ T3 T6 T7) T7 := T3 + T6,1常见的中间代码表示形式,T i是编译程序引入的临时变量,1常见的中间代码表示形式,顺序执行的语句序列 ，其语句的一般形式 x := y op z (op 为操作符，y 和 z 为操作数， x 为结果) 也可写成四元式的形式： （op y z x）,三地址码TAC,1常见的中间代码表示形式,在现行的编译程序中， AST是较常用的高级中间表示形式（接近源代码） TAC是较常用的低级中间表示形式（接近目标代码） 许多编译程序都是将源程序首先翻译成等价的AST，然后再从AST转换成TAC,抽象语法树A

16、ST的特点： 不含我们不关心的终结符（如逗号，括号），而只含标识符、常量等终结符 不具体体现语法分析的细节步骤，例如seq - stmt; seq，可以表示为链表 能完整体现源程序的语法结构，同时也没有损失源程序的任何语义信息,2 生成抽象语法树,抽象语法树AST的特点：,2 生成抽象语法树,1 语句系列,2 if语句,例：生成抽象语法树的语法制导方法,2 生成抽象语法树,S id := E S if E then S1 S while E do S1 S S1 ; S2, S.ptr := mknode(assign, mkleaf(id.entry), E.ptr) S.ptr := mk

17、node(if_then, E.ptr, S1.ptr) S.ptr := mknode(while_do, E.ptr, S1.ptr) S.ptr := mknode(seq , S1.ptr , S2.ptr) ,mknode: 构造AST内部结点 mkleaf : 构造AST叶结点 S.Ptr, E.ptr：指向AST某个结点的指针,例：生成抽象语法树的语法制导方法,2 生成抽象语法树,TreeNode * if_stmt(void) TreeNode * t = newStmtNode(IfK); match(IF); if (t!=NULL) t-child0 = exp(); m

18、atch(THEN); if (t!=NULL) t-child1 = stmt_sequence(); if (token=ELSE) match(ELSE); if (t!=NULL) t-child2 = stmt_sequence(); match(END); return t; ,E id E E1 + E2 E E1 E2 E ( E1 ), E.ptr := mkleaf(id.entry) E.ptr := mknode(+ , E1.ptr , E2.ptr) E.ptr := mknode( , E1.ptr , E2.ptr) E.ptr := E1.ptr ,TreeN

19、ode * simple_exp(void) TreeNode * t = term(); while (token=PLUS)|(token=MINUS) TreeNode * p = newExpNode(OpK); if (p!=NULL) p-child0 = t; p-attr.op = token; t = p; match(token); t-child1 = term(); return t;,3 生成三地址码,顺序执行的语句序列 其语句的一般形式 x := y op z (op 为操作符，y 和 z 为操作数， x 为结果) 也可写成四元式的形式： （op y z x）,三地

20、址码TAC是一种接近汇编语言的中间表示,3 生成三地址码,TAC 语句 赋值语句 x := y op z （op 代表二元算术/逻辑运算） 赋值语句 x := op y （op 代表一元运算） 复写语句 x := y （y 的值赋值给 x） 无条件跳转语句 goto L （无条件跳转至标号 L） 条件跳转语句if x rop y goto L （rop 代表关系运算） 标号语句 L : （定义标号 L）,3 生成三地址码,语义属性 id.place : id 对应的存储位置 E.place : 用来存放 E 的值的存储位置 E.code : 对应于E 的 TAC 语句序列 S.code : 对

21、应于 S 的 TAC 语句序列,赋值语句及算数表达式的语法制导翻译,3 生成三地址码,语义函数/过程 gen : 生成一条 TAC 语句 newtemp : 在符号表中新建一个从未使用过的名字， 并返回该名字的存储位置 | ：TAC 语句序列之间的链接运算,赋值语句及算数表达式的语法制导翻译,赋值语句及算数表达式的翻译模式,S id := E S.code := E.code | gen(id .place := E.place) E id E.place := id .place E int E.place := newtemp; E.code := gen (E.place := int

22、.val) E real E.place := newtemp; E.code := gen (E.place := real .val) ,3 生成三地址码,E E1 + E2 E.place := newtemp; E.code := E1.code | E2.code | gen (E.place := E1.place + E2.place) E E1 E2 E.place := newtemp; E.code := E1.code | E2.code | gen (E.place := E1.place E2.place) E -E1 E.place := newtemp; E.co

23、de := E1.code | gen (E.place := uminus E1.place) E (E1) E.place := E1.place ; E.code := E1.code ,3 生成三地址码,赋值语句及算数表达式的翻译模式,例 翻译赋值语句A:B+C,E1.placeB,E2.placeC,E.placet1； t1 := B + C,t1 := B + C A: t1,(为了直观，用B和C分别表示B和C在符号表的入口地址),翻译结果生成TAC序列 t1 := B C A: t1,3 生成三地址码,两种方法： 直接对布尔表达式求值 通过控制流体现布尔表达式的语义,布尔表达式

24、的语法制导翻译,3 生成三地址码布尔表达式,直接对布尔表达式求值 “1” 表示 true; “0” 表示 false; 采用与算术表达式类似的翻译方法,例：a or b and not c被翻译成： (1) t1:=not c (2) t2:=b and t1 (3) t3:=a or t2,3 生成三地址码布尔表达式,通过控制流体现布尔表达式的语义 方法：通过转移到程序中的某个位置来表示布尔表达式的结果 优点： 方便实现控制流语句中布尔表达式的翻译 利用短路（short-circuit）代码，避免不必要的求值,3 生成三地址码,短路（short-circuit） E1 or E2 if E1

25、 then 1 else E2 E1 and E2if E1 then E2 else 0 已知 E1 为真时，不必再对E1or E2 中的 E2进行求值； 已知 E1 为假时，不必再对 E1 and E2中的E2 进行求值,布尔表达式的语法制导翻译,例 ab or cd and ef 采用短路代码，E.true 和E.false 分别代表 E 为真和假时要转移到的程序位置，即标号 if ab goto E.true goto label1 label1: if cd goto label2 goto E.false label2: if ef goto E.true goto E.false

26、,3 生成三地址码布尔表达式,翻译布尔表达式至短路代码（L-翻译模式）,E E1.true := E.true; E1.false := newlabel E1 or E2.true := E.true; E2.false := E.false E2 E.code := E1 .code | gen (E1.false :) | E2 .code E E1.false := E.false; E1.true := newlabel E1 and E2.false := E.false; E2.true := E.true E2 E.code := E1 .code | gen (E1.true

27、 :) | E2 .code E E1.true := E.false; E1.false := E.true E1 E.code := E1.code newlabel返回一个新的语句标号,3 生成三地址码-布尔表达式,翻译布尔表达式至短路代码（L-翻译模式）,E ( E1.true := E.true; E1.false := E.false E1 ) E.code := E1.code E id1 rop id2 E.code := gen (if id1.place rop.op id2.place goto E.true ) | gen (goto E. false) E true

28、E.code := gen (goto E.true) E false E.code := gen (goto E. false) ,3 生成三地址码-布尔表达式,例 ab or cd and ef 的翻译过程 假定整个表达的E.true= Ltrue, E.false=Lfalse,E.true=Ltrue E.false=Lfalse,E1.true=Ltrue E1.false=L1,E2.true=Ltrue E2.false=Lfalse,E1.true=L2 E1.false=Lfalse,E.true=Ltrue E.false=Lfalse,if ab goto Ltrue g

29、oto L1,if cd goto L2 goto Lfalse,if ef goto Ltrue goto Lfalse,Label L1,label L2,if-then 语句（L 翻译模式） S if E.true := newlabel；E.false := S.next E then S1.next := S.next S1 S.code := E.code | gen(E.true :) | S1.code ,控制语句的语法制导翻译,E.code,S1.code,E.true:,E.false:,to E.true,to E.false,newlabel 返回一个新的语句标号 S.next 属性表示 S 之后要执行的首条 TAC 语句的标号,3 生成三地址码,控制语句的共同特点是：根据布尔表达式取值，分别执行不同的语句序列。 问题：不同的语句序列结束后，如何使控制转向语句的结束。例如：if E1 then if E2 then S1 else S2 else S3,if-then-else 语句（L 翻译模式）,E.code,S1.code,E.true:,E.false:,goto S.next,to E.true,to E.fase,S2.