编译原理 Compiler Principles 第六章中间代码生成 湖南大学信息科学与工程学院 软件工程系杨金民 2019

Transcription

1 编译原理 Compiler Principles 第六章中间代码生成 湖南大学信息科学与工程学院 软件工程系杨金民 2019

2 什么叫语法制导的翻译 (SDT) 求表达式的值 id 1 + id 2 *id * 5 文法 :E E + E E * E id E 5 E 1 + E 4 id 1 E 2 * E 3 id 2 id 3 四者的语义相同 对于计算机执行的指令流 : E 1 = id 1 E 2 = id 2 E 3 = id 3 E 4 = E 2 * E 3 E 5 = E 1 * + E 4 对于计算器的计算结果 : 19

3 翻译之一 : 源程序 中间代码 求表达式的值 id 1 + id 2 *id * 5 文法 :E E + E E * E id E 5 E 1 + E 4 id 1 E 2 * E 3 id 2 id 3 对于计算机执行的指令流 : E 1 = id 1 E 2 = id 2 E 3 = id 3 E 4 = E 2 * E 3 E 5 = E 1 + E 4 对于计算器的计算结果 : 19 源程序是语句流, 中间代码是指令流, 都是线性结构

4 中间代码形式 源程序 高级中间表示形式 低级中间表现形式 目标代码 文法 :E E + E E * E id E 5 E 1 + E 4 id 1 E 2 * E 3 + * E 1 = id 1 E 2 = id 2 E 3 = id 3 E 4 = E 2 * E 3 E 5 = E 1 * + E 4 id 2 id 3 id 1 id 1 id 1 语法分析树 抽象语法树 三地址码

5 中间代码形式 有向无环图 DAG DAG(directed acyclic graph) 表达式 a + a * (b - c) + (b - c ) * d 的 DAG: + + * a * - d b c

6 中间代码形式 有向无环图 DAG 表达式 a + a * (b - c) + (b - c ) * d + + * * - a b c d DAG

7 DAG 与抽象语法树的联系与差异 生成抽象语法树的 SDD 产生式 1)E E 1 + T 2)E T 3)T T 1 * F 4)T F 5)F (E) 6)F id 语义规则 E.node = new Node('+', E 1.node, T.node) E.node =T.node E.node = new Node('*', T 1.node, F.node) T.node = F.node F.node = E.node F.node = new Leaf(id, id.entry)

8 产生式 1)E E 1 + T 2)E T 3)T T 1 * F 4)T F 5)F (E) 6)F id DAG 与抽象语法树的联系与差异 : 生成 DAG 的 SDD 语义规则 E.node = gennode('+', E 1.node, T.node) E.node =T.node E.node = gennode('*', T 1.node, F.node) T.node = F.node F.node = E.node F.node = gen Leaf(id, id.entry) gennode((op, left_node, right_node) { node = getnode(op, left_node, right_node); if (node == null ) then return new Node(op, left_node, right_node); else return node; } 差异何在?

9 6.2 中间代码 : 三地址代码 概念计算机上执行的指令流 ( 指令序列 ), 无穷的存储器 1 运算指令 : 一个运算符, 两个运算分量, 一个运算结果 ; x = y op z 运算分量 : 名字 : 用源程序中名字作为三地址代码的地址 常量 : 源程序中出现的 ; 编译器生成的临时变量 ;

10 三地址代码 (2) 运算 / 赋值指令 :x=y op z, 或者 x=op y 复制指令 :x = y 无条件转移指令 :goto L 条件转移指令 :if x goto L if False x goto L 条件转移指令 :if x relop y goto L

11 三地址代码 (3) 过程调用 / 返回 : param x1 param x2 param xn call p, n // 调用子过程 p,n 为参数个数 带下标的复制指令 :x=y[i] x[i] = y 地址 / 指针赋值指令 : x=&y, x=*y, *x=y

12 三地址码例子 语句 : do i = i + 1; while (a[i]<v); L: t 1 = i + 1 i = t 1 t 2 = i * 8 t 3 = a[t 2 ] IF t 3 < v GOTO L 符号表 id name type size 0 i integer 4 1 a float(6, integer) 2 v integer 4 3 t1 integer 4 4 t2 integer 4 5 t3 integer : 组元素的大小 ( 字节数 )

13 其它中间代码表达形式 在实现时, 还有四元式 三元式 间接三元式 静态单 赋值 ; 四元式 :op, arg1, arg2, result; 三元式 : 就是 DAG;

14 对程序的中间代码的理解 (1) 表达式 a+b*c 结合律, 交换律 带来了写程序时表达的灵活性 : 写成 b*c+a; c*b+a; a+c*b 都行 t 1 =b*c t 2 =a+t 1 识别 : 结合律, 交换律 引入了通用计算机特性 : ü 计算的单元化特性 ; ü 计算指令的序列性 ; ü 计算结果的存储性

15 对程序的中间代码的理解 (2) c=0 L 0 : if (c>10) goto L 1 goto L2 L 1 : c=c-1 if(a>b) goto L 3 goto L 4 L 3 : d=x+y goto L 5 L 4 : d=x*y goto L 5 L 5 : goto L 0 L 2 : x=1 { c=0; while(c>10) { c=c-1; if (a>b) d=x+y; else d=x*y; } x=1 } 在外形上, 层次结构变成了线性结构 控制语句的多样性, 变成了单一性 :for, do,if,while,switch if + goto

16 对程序的中间代码的理解 (3) int a[2][3], c, i, j; 表达式 c+a[i][j] 的三地址码 : t 1 = i * 12 t 2 = j * 4 t 3 = t 1 + t 2 t 4 = a[ t 3 ] t 5 = c + t 4 数组在三地址码中, 概念完全不同, 变成了 相对位置概念, 与基地址的偏移量 ( 字节数 )

17 对程序的中间代码的理解 (4) 函数调用 :n = f(x+y, x*y); 的三地址码 : t 1 = x + y t 2 = x*y param t 1 param t 2 t 3 = call f, 2 n = t 3 更加接近函数调用的实现机理

18 语义分析和中间代码生成中的数据结构 1. 中间代码表 三地址中间代码表 : nextinstr row_id tag code goto src_row_id 1 L 1 : i = j + k 2 3 生成特点 : 分析中通过栈缓存来实现了顺序调转, 只增不插 操作 : gen(get(i) '=' E.addr); gen( if (' E 1.addr ' >' E 2.addr ') goto' begin); AddLabel( begin ':'); backpatch( list, nextinstr);

19 语义分析之一 : 变量先定义后使用原则 2. 符号表 每申明一个变量, 便在符号表中添加一行 在中间代码表中, 变量的真实表达为 :V Tid.Rid 变量要先申明后使用, 因此每遇到一个变量, 都要到符号表 中检查, 检查它是否已经申明 ; 就近匹配原则, 确定是指哪个变量 ; 变量申明的重复性检查 : 同一块中申明的变量不允许同名 ; int main( ) { int p = 2; MyFun( p ); if (p > 0) { float p = 4; s = substr(s 1, p); } }

20 符号表的数据结构 T ID row_id name type_id offset s_row_num 1 i 符号表 : 2 j k cur_pos 中间代码中的变量, 标识形式 :V TID. RID AddVariable(id, type,offset); 全局变量 : 符号表数量计数器 :st_num;

21 在生成机器代码前, 求符号表中的每行数据的 offset 字段值 T ID row_id name type_id offset s_row_num cur_pos 1 i 符号表 : 2 j k UPDATE Tid AS t1 SET offset = (SELECT width FROM TypeT AS t2 WHERE t1.type_id = t2.row_id) + (SELECT offset FROM Tid AS t3 WHERE t3.row_id = t1.row_id - 1) WHERE row_id > 1

22 类型表和类型的项表 cur_pos TypeTable row_id name type width d_row_num 1 student record float 符号表 : item row_id type_id name type offset d_row _num 1 1 age integer tall float cur_pos

23 符号表的链表 : 每个 Block, 以 {} 标识, 都有自己的符号表 S { M S } N M { st = new SymbolTable(); st. prior =cst; cst = st; } N { cst = cst.prior; } E id { E.addr = Position(id); } class SymbolTable { Table T; int cur_pos; int offset; int TID; SymbolTable* prior; }

24 在符号表的链表中查找某个变量是否已经申明 position(id) { st = cst; i = st.cur_pos; find = false; while (1) { while ( i == 0 && st.prior!= null ) { st = st.prior; i = st.cur_pos; } if (i == 0 && st.prior == null) ' 未定义 return null; while( i > 0 ) { if(st[i - 1].name == id) ' 找到 ' return V [st.id, i]; i-- ; } } }

25 变量声明的 SDT D T L; L L, id; { if(nodulplicate(id)) AddVarible(id, T.type); } L id; { if(nodulplicate(id)) AddVarible(id, T.type); } 这个文法是 LR 的, 还是 LL 的? 下面的是书上的, 乱搞 1) F {top = new Env(); D.offset= 0 } D 2) D T id; { top.put(id, T.type, offset); D 1.offset = D.offset + T.width; } D 1 { D.offset = D 1.offset ; } 3) D

26 变量申明时, 在当前符号表中查找变量名是否有重复现象 NoDulplicate( id ) { i = cst.cur_pos; while( i >0 ) { } if(cst[i-1].name == id) ' 申明出现重名 ' return fasle; i-- ; } return true;

27 申明一个变量时, 往当前符号表中添加一行, 表达该变量 AddVarible( id,type_id ) { APPEND INTO cst.table VALUES( cst.cur_pos, id, type_id, cst.offset); cst.cur_pos ++; cst.offset += width(type_id); return; }

28 中间代码的特性 (5) 源程序中数据 ( 变量的申明 / 定义 ) 和代码混合交叉在一起, 须要时就定义, 数据是以名字来标识 中间代码中, 数据和代码进行了分离 数据都规一到符号表中 在中间代码中, 数据的标识, 不再是名字, 而是它在符号表中的位置, 即 Tid.Rid 在机器代码中, 数据的标识, 是它的内存地址 中间代码将变量都规一到符号表中, 变量的内存地址于是就是符号表在内存的地址 ( 即基地址 )+offset 第七章再介绍

29 3. 其它数据结构 goto 标签表 操作 label =NewLabel(); AddLabel(label ':'); gen('goto' label); 全局计数器 goto 标签表 row_id tag value 1 L L 这个表仅仅只有在 LL 分析中用到, 在 LR 分析中不须要 AddLabel(label ':') 这个函数, 就是把 nextinstr 的值赋给指定的标签行的 value 字段 goto 的值, 在随后中间代码优化, 或者翻译成机器码时, 查此表, 得到它的实际值

30 观察 c=0 if (c>10) goto L 1 goto L 0 L 1 : c=c-1 if(b>c) goto L 3 goto L 2 L 3 : b=x+y if(a>b) goto L 5 goto L 4 L 3 : a=x*y L 0 : L 2 : L 4 : x=1 c=0; if(c>10) { c=c-1; if (b>c) { b=x+y; if (a>b) { a=x*y; } } } x=1 在 LL(1) 中, 对 L SL 1, 要展开 S 时, 不知道 L 1 将会是按照 L SL 1 还是 L 展开? 导致每个语句的 S.next =newlabel( );

31 c=0 if (c>10) goto L 1 goto L 0 L 1 : c=c-1 if(b>c) goto L 3 goto L 2 L 3 : b=x+y if(a>b) goto L 5 goto L 4 L 3 : a=x*y L 0 : L 2 : L 4 : x=1 观察 c=0; if(c>10) { c=c-1; if (b>c) { b=x+y; if (a>b) { a=x*y; } } } x=1 在 LL(1) 分析中, 对 L SL 1, 要展开 S 时, 就要确定 S.next 的值, 因为随后在 B 中生成 goto 语句时, 要用到 在 LR(1) 分析中不一样, 规约出 S 后,S.next 的值才确定下来, 此 时看当前输入符, 如果是 '}', 说明 S 是当前块中的最后一个语句 ;

32 临时变量 临时变量 :E.addr = new temp(); 其含义是在当前符号表中, 添加一行 返回所添加的这一行的 标识 id, 即 Tid. Rid 注意 : 每申明一个变量, 也是往当前符号表中添加一行, 随后要使用这个变量时, 再基于名字 (id) 到符号表中来查出它所指的行, 返回该行的标识 id, 即 Tid. Rid, 作为中间代码中对该变量的标识

33 6.3 类型和变量声明 类型检查 (Type Checking) 规则 : 保证运算分量的类型和运算符的预期类型要匹配 翻译 : 确定变量的类型, 需要的内存空间 计算数组元素的 地址 ( 即存储空间布局 ( 相对地址 ) 类型转换 选择正确 的运算符 ;

34 类型表达式 类型表达式 (type expression) 表示类型的结构, 其定义如下 : 基本类型是一个类型表达式 如 :boolean integer,float, void 等 类名是一个类型表达式 类型构造算子作用于类型仍是类型表达式 array[ 数字, 类型表达式 ] record { < 字段类型 > 对的列表 } list 类型 set 类型

35 类型表达式 从函数的角度来看待类型 : 类型构造算子 : 是用类型作为参数, 构造出新的类型 ; 从类型 s 到类型 t 的函数记作 s t; 按照函数的写法应该是 t (s) 例如 :list( ) 的结果是列表类型, 其元素的类型为 ; class Cell { int info; Cell* next; } 类型名和递归类型 ; 可以给类型取名, 例如上面的 Cell 某种类型的变量,

36 数组类型的类型表达式, 及其长度求解的 SDD 产生式 T BC B int B float C [num]c 1 C 语义规则 C.inh_t = B.t C.inh_w = B.w T.t = C.t, T.w = C.w B.t = integer, B.w=4 B.t = float, B.w=8 C 1.inh_t = C.inh_t C 1.inh_w = C.inh_w C.t = array(num, C 1.t) C.t= C.inh_t C.w =C.inh_w LL 文法, 还是 LR 文法? T B t int syn syn inhc inh [ 2 ] C 1 syn sy inh [ 3 ] n C 2 例, int [2][3] 类型表达式为 array(2, array(3,integer)

37 上述 SDD 的 SDT 1)T B{C.inh_t = B.t; C.inh_w = B.w;} C { T.t = C.t; T.w = C.w; } 2)B int {B.t= integer; B.w = 4; } 3)B float {B.t= float; B.w = 8; } 4)C { C 1.inh_t = C.inh_t; C 1.inh_w = C.inh_w; } [num {S.inh= num; } ] C 1 { C.t = array(s.inh, C 1.t); C.w =S.inh* C 1.w } S 5)C {C.t = C.inh_t; C.w = C.inh_w; } 当 S 变成栈顶时, 要弹出它, 然后用它的产生式的右部倒着压入栈 中, 现在 S, 而且这个产生式中没有动作 即 S 直接出栈

38 在 LR 语法和 LR 分析中的 SDT 例如,int [2][3] 的类型表达式为 array(2, array(3,integer)) 1) T BC { T.t= B.t; T.w= B.w; while(int i=s.pop()) { B.t = array(num, B.t); T.w=T.w* i; } delete s; AddType(id, T.t, T.w); } } 2) B int { B.t = integer; B.w = 4 } 3) B float { B.t = float; B.w = 8 } 4) C C 1 [num] { s.push(num); } 5) C [num] { s = new stack(); s.push(num); } s 是一个全局变量, 该方案可行吗?

39 记录类型的定义文法和 SDT T record id { I } I I 1 T id; I T id; LL 文法, 还是 LR 文法? T record id { H I } { UpdateWidth( Rid, I.width); } I I 1 T id;{ AddItem( H.Rid, id, T.type); I.width = I 1.width +T.width;} I T id;{ AddItem( H.Rid, id, T.type); I.width = T.width; } H {H.Rid = AddType( id, record); }

40 程序中的变量 每申明一个变量, 便在符号表中添加一行 在中间代码表中, 变量的真实表达为 :V Tid.Rid 变量要先申明后使用, 因此每遇到一个变量, 都要到符号表 中检查, 检查它是否已经申明 ; 就近匹配原则, 确定是指哪个变量 ; 变量申明的重复性检查 ; int main( ) { int p = 2; MyFun( p ); if (p > 0) { float p = 4; s = substr(s 1, p); } }

41 局部变量的存储布局 变量有类型概念 类型又有宽度概念, 即内存大小 (Bytes), 变量有值和地址两个两个概念 变量值放在内存中, 基于其内存地址来访问变量的值 ; 变量的类型信息存储在类型表中 ; 变量信息存储在符号表中 每个块 (block) 都有自己的符号表 ; root 块的符号表存放了所有全局变量 root 块的子块为函数块

42 变量的作用域和内存布局 scheme 在一个函数里面, 其所有局部变量放在一个连续的存储空间中, 变量在该空间的放置顺序与声明顺序一致 ; 每申明一个变量,SDT 所做处理 : 在当前块的符号表中, 检查是否出现名字重复的变量定义 ; 如果无, 则在当前符号表中, 增加一行 ( 变量实例 ): 书上的是 :top.put(id.lexeme, T.type, offset); 我们的是 :AddVarible( ); 见前面的内容

43 将表达式 三地址指令序列的 SDD 产生式 1)S id=e; 2)E E 1 + E 2 3)E -E 1 4)E (E 1 ) 5)E id 语义规则 S.code =E.code gen(top.get(id.lexeme) '=' E.addr) E.addr = new temp(), E.code =E 1.code E 2.code gen(e.addr '= E 1.addr '+' E 2.addr) E.addr = new temp() E.code =E 1.code gen(e.addr '=' 'minus' E 1.addr ) E.addr = E 1.addr E.code =E 1.code E.addr = top.get(id.lexeme) E.code =''

44 增量式翻译方案 SDT 1)S id=e; 2)E E 1 + E 2 3)E -E 1 { gen(top.get(id.lexeme) '=' E.addr); } { E.addr = new temp(); gen(e.addr '= E 1.addr '+' E 2.addr); } { E.addr = new temp() gen(e.addr '=' 'minus' E 1.addr ); } 4)E (E 1 ) { E.addr = E 1.addr; } 5)E id { E.addr = top.get(id.lexeme); }

45 数组元素在中间代码中表达 一个一维数组, 元素从 0 到 n-1 编号, 在内存中依次 连续存 储 其起始地址为 base, 第 i 个元素的地址为 :base+i*w, w 为元素的类型的宽度 ; K 维数组 : 将其视为一个一维数组, 其元素的类型为一个 k- 1 维数组 A[i 1 ][i 2 ] [i k ] 的地址 : base+(( ((i 1 *n 2 +i 2 )*n 3 +i 3 ) )*n k +i k )*w 在符号表中有 A 的条项,A 的条项中记录了 A 的类型,base 就是 A 的地址 ;

46 数组元素的文法含义 L L[E] L id[e] 例如 : a[i][j] LL 文法, 还是 LR 文法? L 1 是 a 的元素, L 2 是 L 1 的元素 L 1 a [ E ] L 2 [ E ] j 数组定义 :int a[10][20], 对于数组元素 a[5][6] a.type = array(10, array(20, integer)); L 1.type = a.type.elem = array(20, integer); L 2.type = integer; i

47 求数组元素的偏移地址 L 2 L 是 a 的元素 L [ E ] a [ E ] i j L id[e];{ L.array = top.get(id.lexeme); L.type =L.array.type.elem; L.addr = new Temp(); gen( L.addr '=' E.addr '*' L.type.width); }

48 求数组元素的偏移地址 L 是 L 1 的元素 L L 1 [ E ] a [ E ] i j L L 1 [E]; { L.array = L 1.array_id ; L.type =L 1.type.elem; t = new Temp(); L.addr = new Temp(); gen( t '= E.addr '*' L.type.width); gen( L.addr '=' L 1.addr '+' t); }

49 数组元素作为因子 L 的代码只计算了偏移量 ; 数组元素的值 : L 的数组基址加上偏移量 ; 使用三地址指令 x=a[i] 5)E L { E.addr = new temp(); AddCode(E.addr '=' L.array'[' L.addr ']'); }

50 给数组元素赋值 使用三地址指令 a[i]=x S L = E; { gen(l.array '[' L.addr ']' '=' E.addr); }

51 c int a[2][3], c, i, j; 求赋值语句 c = c+a[i][j] 的三地址码序列 addr E addr= c c S = addr a [ E addr=i ] type=array(2, array(3, integer)) addr i addr E + addr=t 5 注释语法分析树 E L L type=array(3,integer) array = a addr=t 1 addr=t 4 array = a; type=integer addr=t 3 [ E addr=j ] j addr t 1 = i * 12 t 2 = j * 4 t 3 = t 1 + t 2 t 4 = a[ t 3 ] t 5 = c + t 4 c= t 5

52 类型检查和转换 类型系统 : 编译时, 目标代码中的元素有值, 类型, 存储地址 的概念 ; 编译时就解决类型匹配问题 保证运行时, 不再存在 有关类型的问题要处理, 不会出错 : 强类型的语言 ; 编译时来发现错误, 以提高运行时效率 确定临时变量的大小 例如 float b; int i; i= &b;

53 类型检查的两种方式 类型综合例如, 对于表达式 E 1 +E 2, 已知 E 1 和 E 2 的类型, 那么运算的结果的类型是什么? 类型推导 根据语言结构的使用方式来确定该结构的类型例 :null(x) 是一个测试列表是否为空的函数, 则根据函数 null(x) 可推断出 x 必定是一个列表, 但 x 的元素类型未知 不要求名字先定义的语言需要类型推导, 如 :ML

54 类型转换 设表达式 x+i,x 为浮点数 i 为整数, 则结果应该是浮点数 x 和 i 使用不同的二进制表示方式 浮点数相加, 和整数相加使用不同的指令 t1 = (float) i t2 = x + t1

55 类型的 widening 和 narrowing Java 类型转换规则区分了拓宽转换和窄化转换 编译器自动完成的转换为隐式转换, 程序员用代码指定的转换为显式转换

56 处理类型转换的 SDT E E 1 +E 2 { E.type = max(e 1.type, E 2.type); a 1 =widen(e 1.addr, E 1.type, E.type); a 2 =widen(e 2.addr, E 2.type, E.type); E.addr = new Temp( ); gen(e.addr '=' a1 '+' a2); } Addr widen(addr a, Type t, Type w) { if (t=w) return a; else if (t=integer and w= float) { temp = new Temp(); gen(temp '=' '(float)' a); return temp; } }

57 函数 / 运算符的重载 重载 (overload) 是面向对象程序设计语言的一个特征 例 :Java 语言中 + 算符可表示串连接或加法运算, 由操作数的类型来区分 用户自定义的函数也可以重载, 如 : Void err( ) { } Void err(string S) { } 通过查看参数个数, 类型, 顺序, 就能解决的函数重载问题

58 LL 语法分析中程序文法的表达 P S 1 S if (B) S T T else S 3 S id = E 4 S while(b) S 5 S T id 6 S {L} L SL L 程序 if 语句赋值语句 while 语句变量定义语句语句序列当前输入符为 } 或者 $, 选择 L E E+E E*E (E) id B B && B B B (B) E > E id true false

59 S { L } S L c = 0 S L while (B) S S c > 10 { L } x = 1 S L c=c-1 S L if ( B ) S else S d=x+y d=x*y L LL 语法分析树例子 { c=0; while(c>10) { c=c-1; if (a>b) d=x+y; else d=x*y; } x=1 }

60 LR 语法分析中程序文法的表达 P S 1 S if (B) S 2 S if (B) S else S 3 S id = E 4 S while(b) S 5 S T id 6 S {S} 7 S SS B B && B B B (B) E> E id true false E E+E E*E (E) id

61 LR 语法分析树例子 S c = 0 S { S } S S S x = 1 while ( B ) S c > 10 { S } S S { c=0; while(c>10) { c=c-1; if (a>b) d=x+y; else d=x*y; } x=1 } c=c-1 if ( B ) S else S d=x+y d=x*y

62 I 4 S id = E id=e I 0 P S S {S} S SS S if(b) S S while(b) S S id = E S I 1 P S S S S S SS S if(b) S S while(b) S S id = E S I 5 S SS S S S S SS S if(b) S S while(b) S S id = E S S if I 3 S if( B ) S S {S} S SS S if(b) S S while(b) S S id = E { S if I 2 S { S} S SS S if(b) S S while(b) S S id = E I 6 S {S } S S S S SS S if(b) S S while(b) S S id = E } I 7 S {S} S I 8 S if( B ) S

63 语言的 DFA I 4 S id = E I 0 P S S {S} S if(b) S S while(b) S S id = E if id S { { I 1 P S I 2 S { S} S SS S if(b) S S while(b) S S id = E S I 5 S {S } S S S S if(b) S S while(b) S S id = E } S I 7 S {S} I 8 S SS I 3 S if( B ) S S {S} S if(b) S S while(b) S if S id = E I S 6 S if( B ) S

64 表达式的类型 算术表达式 E; 优先级 :(),*/, +/- 布尔表达式 B; 优先级 :(),!,&&, 正则表达式 R; 优先级 :(),*, 联接,

65 6.6 控制流的翻译 布尔表达式可以用于改变控制流, 计算逻辑值 文法 B B B B && B!B (B) E relop E id true false B 1 B 2 中,B 1 为真时, 不计算 B 2, 整个表达式为真 因此, 当 B 1 为真时应该跳过 B 2 的代码 B 1 && B 2 中,B 1 为假时, 不计算 B 2, 整个表达式为假 短路代码 通过跳转指令实现控制流的处理

66 短路代码的例子 S if (B) S 1 语句的实例 : if (x<100 x>200 && x!= y) x = 0; 三地址码如下 : if x < 100 goto L 2 if FALSE x > 200 goto L 1 if FALSE x!= y goto L 1 L 2 : x=0 L 1 : 非终结符的属性 : S.next = L 1 ; B.true =L 2 ; B.false = S.next

67 S while(b) S 1 语句的 SDD 继承属性 : B.true B.false S.next begin: B.true: B.false: B.code S 1.code goto begin... to B.true to B.false 产生式 4)S while (B) S 1 语义规则 begin = newlable( ); B.true = newlable( ); B.false =S.next; S 1.next= begin; S.code =label(begin) B.code label(b.true) S.code

68 S if (B) S 1 语句的 SDD 继承属性 : B.true B.false S.next 综合属性 : B.code S.code B.true: B.false: B.code S 1.code... to B.true to B.false if x<100 goto L 2 goto L 3 L 3 : if x> 200 goto L 4 goto L 1 L 4 : if X!=y goto L 2 goto L 1 L 2 : x = 0 L 1 : 产生式 if (x<100 x>200 && x!= y) x = 0; 语义规则 S if (B) S 1 B.true = newlable( ); B.false = S.next; S 1.next= S.next; S.code =B.code label(b.true) S 1.code

69 S if (B) S 1 else S 2 语句的 SDD 继承属性 : B.true B.false S.next B.true: B.false: S.next: B.code S 1.code goto S.next S 2.code... to B.true to B.false 产生式 3)S if (B) S 1 else S 2 语义规则 B.true = newlable( ); B.false = newlable( ); S 1.next= S.next; S 2.next= S.next; S.code =B.code label(b.true) S 1.code gen('goto' S.next) label(b.false) S 2.code

70 P S 产生式的 SDD 产生式 继承属性 : S.next 综合属性 : S.code P.code 语义规则 1)P S; S.next =newlable( ); P.code = S.code label(s.next) 5)L SL 1 S.next = newlable( ); L 1.next = L.next; L.code =S.code L 1.code 继承属性 : L {if S 是控制语句 S.next = newlable( ); L 1.next= S.next; } S {L 1.inh_code+ = S.code } L 1 {L.code += L 1.code} L {L.code = L.inh_code}

71 S while(b) S 1 语句的 SDT begin: B.true: B.false: B.code S 1.code goto begin... to B.true to B.false S.next 随堂测试 : 写出在 LL 分析中的 SDT; 写出在 LR 分析中的 SDT;

72 布尔表达式的中间代码例子 例 : 将 if (x<100 x > 200 && x!= y ) x = 0; 翻译成三地址 码 if x<100 goto L 2 goto L 3 L 3 : if x> 200 goto L 4 goto L 1 B 1 B B 4 L 4 : if X!=y goto L 2 goto L 1 L 2 : x = 0 L 1 : x<100 B 2 x>200 && B 3 x!=y

73 翻译布尔表达式 B 的 SDD 产生式 1)B true; 2)B false 3)B E 1 rel E 2 语义规则 B.code = gen('goto' B.true) B.code = gen('goto' B.false) B.code =E 1.code E 2.code gen('if' E 1.addr rel.op E 2.addr 'goto' B.true) gen('goto' B.false)

74 翻译布尔表达式的 SDD 产生式 4)B!B 1 ; 语义规则 B1.true =B.false; B1.false = B.true; 5)B B 1 && B 2 B 1.true = newlabel( ); B 1.false = B.false; B 2.true = B.true; B 2.false = B.false; B.code =B 1.code label(b 1.true) B 2.code

75 翻译布尔表达式的 SDD 产生式 6)B B 1 B 2 语义规则 B 1.true = B.true; B 1.false = newlabel( ); B 2.true = B.true; B 2.false = B.false; B.code =B 1.code label(b 1.false) B 2.code

76 布尔表达式代码的例子 例 : 将 if (x<100 x > 200 && x!= y ) x = 0; 翻译成三地址 码 if x<100 goto L 2 goto L 3 L 3 : if x> 200 goto L 4 goto L 1 B 1 B B 4 L 4 : if X!=y goto L 2 goto L 1 L 2 : x = 0 L 1 : x<100 B 2 x>200 && B 3 x!=y

77 优化 : 减少 goto 指令 例 : 将 if (x<100 x > 200 && x!= y ) x = 0; 翻译成三地址 码 if x<100 goto L 2 goto L 3 L 3 : if x> 200 goto L 4 goto L 1 L 4 : if X!=y goto L 2 goto L 1 L 2 : x = 0 L 1 : 多余 iffalse x>200 goto L 1 iffalse x!=y goto L 1 if(b) S 1 B 的指令之后就是 S 1, B.true 不须要, 设为 fall

78 S if (B) S 1 语句中减少 goto 指令 B.true: B.false: 产生式 3)B E 1 rel E 2 B.code S 1.code... 语义规则 if B.true fall then B.code =E 1.code E 2.code gen('if' E 1.addr rel.op E 2.addr 'goto' B.true) else to B.true to B.false B.false: B.true= fall B.code S 1.code... B.false B.code =E 1.code E 2.code gen('if False' E 1.addr rel.op E 2.addr 'goto' B.false)

79 减少 goto 指令 产生式 3)B E 1 rel E 2 语义规则 B.code =E1.code E1.code gen('if' E1.addr rel.op E2.addr 'goto' B.true) 产生式 3)B E 1 rel E 2 语义规则 if B.true fall then B.code =E1.code E1.code gen('if' E1.addr rel.op E2.addr 'goto' B.true) else B.code =E1.code E1.code gen('if False' E1.addr rel.op E2.addr 'goto' B.false)

80 减少 goto 指令 (2) B B 1 B 2 当 B.true=fall 时 B 1.true S.next B 1.code B 2.code S 1.code... to B 1.true to B 2.false 因为 B 1.false 就是 B 2.code, 因此设 B 1.false=fall, 要省了一 条 goto B 2 起始处的指令 因为 B.true=fall, 又 B 1.code 中要跳转到 S 1.code 的开始 处, 只好创建 B 1.true

81 减少 goto 指令 (2) B B 1 && B 2 当 B.true=fall 时 B 1.true S.next B1.code B 2.code S1.code... to B 1.false to B 2.false 因为 B 1.true 就是 B 2.code 起始处, 因此要设 B 1.true=fall, 省了一条 goto B 2 起始处的指令因为 B 2.true=fall, 又 B 2.code 后自然接 S 1, 省了一条 goto S 1 起始处的指令

82 goto 的优化 c=0 L 0 : if (c>10) goto L 1 goto S (while).next L 1 : L 3 : L 4 : c=c-1 if(a>b) goto L 3 goto L 4 d=x+y goto S (if).next d=x*y S (if).next: goto L 0 S (while).next: x=1 { c=0; while(c>10) { c=c-1; if (a>b) d=x+y; else d=x*y; } x=1 } goto 的目标, 还是一个 goto

83 goto 的优化 S while(b) S 1 S 1.next = S.begin 现在 :S 1 S a S b 直接表明了 S a.next 就是 S b S b.next 应该 = S 1.next { c=0; while(c>10) { c=c-1; if (a>b) d=x+y; else d=x*y; } x=1 } 产生式 语义规则 5)S S 1 S 2 S 1.next = newlable( ); S 2.next= S.next; S.code =S 1.code label( S 1.next) S 2.code 5)S S 1 S 2 S 2.next= S.next; S.code =S 1.code S 2.code

84 S { L } S L c = 0 S L while (B) S S c > 10 { L } x = 1 S L c=c-1 S L if ( B ) S else S d=x+y d=x*y L 观察 { c=0; while(c>10) { c=c-1; if (a>b) d=x+y; else d=x*y; } x=1 } 在 LL(1) 中,L SL 1 对于 S, 它怎么知道自己是不 是当前块中的最后一个语句?

85 观察 c=0 if (c>10) goto L 1 goto L 0 L 1 : c=c-1 if(b>c) goto L 3 goto L 2 L 3 : b=x+y if(a>b) goto L 5 goto L 4 L 3 : a=x*y L 0 : L 2 : L 4 : x=1 c=0; if(c>10) { c=c-1; if (b>c) { b=x+y; if (a>b) { a=x*y; } } } x=1 在 LL(1) 中, 对 L SL 1, 要展开 S 时, 不知道 L 1 将会是按照 L SL 1 还是 L 展开? 导致每个语句的 S.next =newlabel();

86 翻译布尔表达式的 SDD 产生式 6)B B 1 B 2 语义规则 B 1.true = B.true; B 1.false = newlabel( ); B 2.true = B.true; B 2.false = B.false; B.code =B 1.code label(b 1.false) B 2.code 产生式 6)B B 1 B 2 语义规则 if B.true = fall then B 1.true = newlabel(); else B 1.true = B.true; B 1.false = fall; B 2.true = B.true; B 2.false = B.false; if B.true = fall then B.code =B 1.code B 2.code label(b 1.true) else B.code =B 1.code label(b 1.false) B 2.code

87 求布尔表达式的值, 比如 :x= a<b S id =B 等价于 if (B) id=true else id = false; 随堂测试 : 写出在 LL 分析中的 SDT; 写出在 LR 分析中的 SDT;

88 生成 goto 时, 其目标指令有两种情形 : 在前 ; 在后 c=0 L 0 : if (c>10) goto L 1 goto S (while).next L 1 : L 3 : L 4 : c=c-1 if(a>b) goto L 3 goto L 4 d=x+y goto S (if).next d=x*y S (if).next: goto L 0 S (while).next: x=1 在前 在后 目标指令尚未已知 c=0; while(c>10) { c=c-1; if (a>b) d=x+y; else d=x*y; } x=1

89 在 LR 分析中, 回填技术的基本思想 在代码生成中, 当生成 goto S.next 指令时, 记下该指令的 id, 即该指令在三地址码表中的行号, 添加到 S 的综合属性 S.nextList 中 随后, 当规约 S while (B) S 1 时, 在执行 AddLabel(S.next ':') 时,S.next 的值就确定下来了 使用 S.nextList, 就知道哪些 goto 指令的目标是 S.next 定位这些前面的 goto 指令所在的行号, 回填上这些行所要的 S.next 值 ;

90 中 布尔表达式的回填翻译 对布尔表达式 B, 因为有继承属性 ture 和 false, 自然也要引入两个综合属性 truelist: 对于 goto 指令, 如果其目标是 B.true, 则其 id( 即在三地址码表中所在的行号 ) 在 truelist 中 ; Falselist: 包含跳转指令的列表, 为 false 时执行这些指令辅助函数 : Makelist(i) : 创建一个只含 i 的列表, 返回该列表 ; Merge(p 1,p 2 ): 合并 p 1 和 p 2 两个列表, 返回合并后的列表 Backpatch(p,i): 将 i 作为 goto 目标地址, 回填到 p 所含各指令

91 布尔表达式的回填翻译 SDT 1)B true; { B.truelist = makelist(nextinstr); gen('goto _'); } 2)B false; { B.falselist = makelist(nextinstr); gen('goto _');} 3)B E 1 rel E 2 { B.truelist = makelist(nextinstr); B.falselist = makelist(nextinstr + 1); gen('if' E 1.addr rel.op E 2.addr 'goto _'); gen('goto _'); }

92 布尔表达式的回填翻译 SDT 4)B (B 1 ); { B.truelist = B 1.truelist; B.falselist = B 1.falselist ; } 5)B!(B 1 ); { B.truelist = B 1.falselist; B.falselist = B 1.truelist; }

93 布尔表达式的回填翻译 SDT 6)B B 1 && { B 2.instr = nextinstr; } B 2 { Backpatch(B 1.truelist, B 2.instr); B.truelist = B 2.truelist; B.falselist = merge(b 1.falselist, B 2.falselist); } 7)B B 1 { B 2.instr = nextinstr; } B 2 { Backpatch(B 1.falselist, B 2.instr); B.falselist = B 2.falselist; B.truelist = merge(b 1.truelist, B 2.truelist); }

94 回填例子 :x<100 x>200 && x!=y 假设从 nextinstr = 100 开始 B 1 t={100} f={101} x<100 i=102 B 5 t={100,104} f={103,105} t={104} i=104 B 4 B 2 t={102} f={103} && f={103,105} B 3 t={104} f={105} 100: if x<100 goto _ 101: goto _ 102: if x>200 goto _ 103: goto _ 104: if x!=y goto _ 105: goto _ x>200 x!=y

95 回填例子 :x<100 x>200 && x!=y 假设从 nextinstr = 100 开始 if (x<100 x > 200 && x!= y ) x = 0; B 1 t={100} f={101} i=102 B 5 t={100,104} f={103,105} t={104} i=104 B 4 f={103,105} 100: if x<100 goto _ 101: goto _ 102: if x>200 goto _ 103: goto _ 104: if x!=y goto _ 105: goto _ 106: x=0 107: x<100 B 2 t={102} f={103} x>200 && t={104}b 3 f={105} x!=y B.code Label(B.true) S 1.code Label(B.false)

96 L 1 : L 3 : 观察 : 在 LL 分析中, 可能一行的前面有多个 goto 标签 c=0 c=0; if (c>10) goto L 1 if(c>10) { goto L 0 c=c-1; c=c-1 if (b>c) { if(b>c) goto L 3 b=x+y; goto L 2 if (a>b) { b=x+y a=x*y; if(a>b) goto L 5 } goto L 4 } a=x*y } x=1 L 3 : L 0 : L 2 : L 4 : x=1 原因是 : 控制语句嵌套, 而且被嵌套的控制语句在其所在的块中 为最后一个语句 存在嵌套关系的三个 if 语句的 next 都是 x=1 语句 ;

97 观察 : 在 LL 分析中,goto 的目标, 可能也是 goto c=0 L 0 : if (c>10) goto L 1 goto S (while).next L 1 : L 3 : L 4 : c=c-1 if(a>b) goto L 3 goto L 4 d=x+y goto S (if).next d=x*y S (if).next: goto L 0 S (while).next: x=1 c=0; while(c>10) { c=c-1; if (a>b) d=x+y; else d=x*y; } x=1 原因是 : 要展开 if 语句时, 无法知道它是其所在块的最后一个语句 只有当它被匹配完之后, 看到当前输入符为 '}' 时, 才能知道它是其所在块中的 last 语句 但为时已晚, 因为开始时就要确定其 next

98 LR 分析中, 能克服上述两个问题 c=0 if (c>10) goto L 1 goto L 0 L 1 : c=c-1 if(b>c) goto L 3 goto L 2 L 3 : b=x+y if(a>b) goto L 5 goto L 4 L 3 : a=x*y L 0 : L 2 : L 4 : x=1 c=0; if(c>10) { c=c-1; if (b>c) { b=x+y; if (a>b) { a=x*y; } } } x=1 a=x*y; 语句规约出来后, 看当前输入符, 它是 }, 意味着该语句 在其所在块中是最后一个语句, 意味着它的 next 并不确定, 是其 父的 next 即其父.nextlist = 它的.next

99 c=0 if (c>10) goto L 1 goto L 0 L 1 : c=c-1 if(b>c) goto L 3 goto L 2 L 3 : b=x+y if(a>b) goto L 5 goto L 4 L 3 : a=x*y L 0 : L 2 : L 4 : x=1 LR 分析中, 一个语句的 next 变得确定的时刻 c=0; if(c>10) { c=c-1; if (b>c) { b=x+y; if (a>b) { a=x*y; } } } x=1 一个语句要被规约出来的时候, 看当前输入符, 如果不是 }, 意 味着该语句在其所在的块中不是 last 语句 此时该语句的 next 变 得确定, 就是 nextinstr;

100 在 LL 分析中,goto 的目标可能也是 goto, LR 分析能优化它 c=0 L 0 : if (c>10) goto L 1 goto S (while).next L 1 : L 3 : L 4 : c=c-1 if(a>b) goto L 3 goto L 4 d=x+y goto S (if).next d=x*y S (if).next: goto L 0 S (while).next: x=1 c=0; while(c>10) { c=c-1; if (a>b) d=x+y; else d=x*y; } x=1 此例中 S while(b) S 1 ; 这里 S 1 {S 2 }, S 2 S a S b,s b 是 if 语句 是其所在块的 last 语句, 因此 S b.next = S 2.next =S 1.next =L 0 当 S b 要规约出来时, 因当前输入符是 }, 意味着 S 1 到了末尾

101 控制转移语句的回填 S if ( B ) S 1 if (B) S 1 else S 2 while (B) S 1 { L } A L L S S 语句的综合属性 :S.nextlist

102 if 语句的回填 (2) 1) S if (B) { S 1.instr = nextinstr;} S 1 { backpatch(b.truelist, S 1.instr); S.nextlist = merge(b.falselist, S 1.nextlist); } 2) S if (B) { S 1.instr = nextinstr; } S 1 N else {S 2.instr = nextinstr;} S 2 { backpatch(b.truelist, S 1.instr); backpatch(b.falselist, S 2.instr); temp= merge(s 1.nextlist, N.nextlist); S.nextlist = merge(temp, S 2.nextlist); } 3) N { N.nextlist = makelist(nextinstr); gen('goto _'); } N 的作用是生成 goto 指令坯,N.nextlist 记录了这个指令的位置

103 S while (B) S 1 语句的回填 4) S while ( { B.instr = nextinstr;} B) { S 1.instr = nextinstr;} S 1 { backpatch(s 1.nextlist, B.instr); backpatch(b.truelist, S 1.instr); S.nextlist = B.falselist; gen('goto' B.instr); }

104 其它语句的回填 (3) S A; { S.nextlist =null; } S {S 1 } { S.nextlist =S 1.nextlist ; } S S 1 { backpatch(s 1.nextlist, nextinstr); } S 2 { S.nextlist = S 2.nextlist; }

105 Break Continue 的处理 虽然 break continue 在语法上就是一个句子, 但是它的代码 却和外围语句相关 只有在循环语句中才能出现, 否则就是语 法错误

106 6.8 switch 语句 switch 语句结构 : switch (E) of { case V 1 : S 1 ; case V 2 : S 2 ; case V n-1 :S n-1 ; otherwise: S n }

107 翻译法 1 T=E L 1 : if T V 1 goto L 2 S 1 的代码 goto next L 2 : if T V 2 goto L 3 S 2 的代码 goto next L 3 : L n-1 : if T V n-1 goto L n S n-1 的代码 goto next L n : next: S n 的代码

108 翻译法 2 L 1 : L n-1 : L n : T=E goto test 关于 S 1 的中间码 goto next 关于 S n-1 的中间码 goto next 关于 S n 的中间码 goto next test: if T=V 1 goto L 1 if T=V 2 goto L 2... if T=V n-1 goto L n-1 goto L n next:

109 用来翻译 switch 语句的 case 三地址代 码指令 Case t V 1 L 1 Case t V 2 L 2 Case t V n-1 L n-1 Case t t L n next:

110 过程的中间代码 在三地址码中, 函数调用被拆分为准备进行调用时的参数求值, 然后是调用本身 设 a 为 int 类型的数组, n = f(a[i]); 的三地址码 : t 1 =i*4 t 2 =a[t 1 ] param t 2 t 3 = call f, 1 n = t 3

111 函数定义和调用的产生式 D T id(f) {S} F T id T id, F S return E; E id(a) A E E, A

112 过程调用的处理 过程调用主要对应两种事 : 传递参数 转子 传地址 : 把实在参数的地址传递给相应的形式参数 调用段预先把实在参数的地址传递到被调用段可以拿到的地方 ; 程序控制转入被调用段之后, 被调用段首先把实在参数的地址抄进自己相应的形式单元中 ; 过程体对形式参数的引用域赋值被处理成对形式单元的间接访问

113 过程调用的翻译 翻译方法 : 把实参的地址逐一放在转子指令的前面. 例如, CALL S(A,X+Y) 翻译为 : t1=x+y param A /* 第一个参数的地址 */ param t1 /* 第二个参数的地址 */ call S,2 /* 转子 */

114 过程调用的翻译 过程调用文法 : (1) S id (Elist) (2) Elist Elist, E (3) Elist E 参数的地址存放在一个队列中 最后对队列中的每一项生成一条 param 语句

115 翻译模式 3. Elist E { 初始化 queue 仅包含 E.place;n=0 } 2. Elist Elist, E { 将 E.place 加入到 queue 的队尾 ;n=n+1 } 1. S id(elist) { for 队列 queue 中的每一项 p do gen( param p); gen( call id.addr, n) }

116 第六章中间代码生成 语义分析和中间代码生成 中间代码表示 类型检查和翻译 中间代码生成 DAG 图 三地址码 静态单赋值 表达式翻译 控制流翻译 回填 过程翻译

117 谢谢谢谢!