chaper 6 - 中间代码生成 2019.pdf
编译原理 Compiler Principles 第六章 中间代码生成 湖南大学信息科学与工程学院 软件工程系 杨金民 2019 什么叫语法制导的翻译(SDT) 求表达式的值id1 + id2 *id3 【4 + 3 * 5】 文法：EE + E | E * E | id 对于计算机执行的指令流： E5 E1 + E4 id1 E2 * id2 E3 id3 E1= id1 E2= id2 E3= id3 E4 = E2 * E3 E5 = E1 * + E4 对于计算器的计算结果： 四者的语义相同 19 翻译之一：源程序 中间代码 求表达式的值id1 + id2 *id3 【4 + 3 * 5】 文法：EE + E | E * E | id E5 E1 + E4 id1 E2 * id2 E3 id3 对于计算机执行的指令流： E1= id1 E2= id2 E3= id3 E4 = E2 * E3 E5 = E1 + E4 对于计算器的计算结果： 19 源程序是语句流，中间代码是指令流，都是线性结构 中间代码形式 源程序 高级中间表示形式 低级中间表现形式 目标代码 文法：EE + E | E * E | id E5 + E1 + E4 id1 E2 * id2 语法分析树 * E3 id3 id1 id1 抽象语法树 id1 E1= id1 E2= id2 E3= id3 E4 = E2 * E3 E5 = E1 * + E4 三地址码 中间代码形式——有向无环图DAG DAG(directed acyclic graph) 表达式 a + a * (b - c) + (b - c ) * d 的DAG: + + a * * b d c 中间代码形式——有向无环图DAG 表达式 a + a * (b - c) + (b - c ) * d + + * * a b DAG c d DAG与抽象语法树的联系与差异 生成抽象语法树的SDD 产生式 1)E→ E1 + T 2)ET 3)TT1 * F 4)TF 5)F→ (E) 6)F→id 语义规则 E.node = new Node('+', E1.node, T.node) E.node =T.node E.node = new Node('*', T1.node, F.node) T.node = F.node F.node = E.node F.node = new Leaf(id, id.entry) DAG与抽象语法树的联系与差异： 生成DAG的SDD 产生式 1)E→ E1 + T 2)ET 3)TT1 * F 4)TF 5)F→ (E) 6)F→id 语义规则 E.node = genNode('+', E1.node, T.node) E.node =T.node E.node = genNode('*', T1.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; } 差异何在？ 6.2 中间代码：三地址代码 概念计算机上执行的指令流(指令序列), 无穷的存储器 ① 运算指令： 一个运算符, 两个运算分量，一个运算结果； x = y op z 运算分量： • 名字：用源程序中名字作为三地址代码的地址 • 常量：源程序中出现的； • 编译器生成的临时变量； 三地址代码（2） l 运算/赋值指令：x=y op z，或者x=op y l 复制指令：x = y l 无条件转移指令：goto L l 条件转移指令：if x goto L if False x goto L l 条件转移指令：if x relop y goto L 三地址代码（3） l 过程调用/返回： param x1 param x2 … param xn call p, n //调用子过程p，n为参数个数 l 带下标的复制指令：x=y[i] l 地址/指针赋值指令： x=&y， x=*y， *x=y x[i] = y 三地址码例子 • 语句： do i = i + 1; while (a[i]10) goto L1 goto L2 L1: c=c-1 if(a>b) goto L3 goto L4 L3: d=x+y goto L5 L4: d=x*y goto L5 L5: goto L0 L2: x=1 { c=0; while(c>10) { c=c-1； if (a>b) d=x+y; else d=x*y; } x=1 } l 在外形上，层次结构变成了线性结构 l 控制语句的多样性，变成了单一性：for， do，if，while，switch if + goto 对程序的中间代码的理解（3） int a[2][3], c, i, j; 表达式 c+a[i][j] 的三地址码： t1= i * 12 t2 = j * 4 t3 = t1 + t2 t4= a[ t3 ] t5 = c + t4 数组在三地址码中，概念完全不同，变成了 相对位置概念，与基地址的偏移量（字节数) 对程序的中间代码的理解（4） 函数调用：n = f(x+y， x*y); t1 = x + y 的三地址码： t2= x*y param t1 param t2 t3 = call f, 2 n = t3 更加接近函数调用的实现机理 语义分析和中间代码生成中的数据结构 1. 中间代码表 三地址中间代码表： nextInstr row_id tag code 1 L1: i=j+k goto src_row_id 2 3 生成特点：分析中通过栈缓存来实现了顺序调转，只增不插。 操作： l gen（get(i) '=' E.addr); l gen(‘if （' E1.addr ' >' E2.addr ') goto' begin); l AddLabel( begin ':'); l backpatch( list, nextInstr); 语义分析之一：变量先定义后使用原则 2. 符号表 l 每申明一个变量，便在符号表中添加一行。在中间代码表中， 变量的真实表达为：VTid.Rid l 变量要先申明后使用，因此每遇到一个变量，都要到符号表 中检查，检查它是否已经申明； int main( ) { l 就近匹配原则，确定是指哪个变量； int p = 2; MyFun( p ); l 变量申明的重复性检查： if (p > 0) { 同一块中申明的变量不允许同名； float p = 4; s = substr(s1, p); } } 符号表的数据结构 TID row_id name type_id 1 i 7 120 2 符号表： j 1 124 3 2 130 k offset s_row_num cur_pos 中间代码中的变量，标识形式：VTID. RID AddVariable(id, type)； 全局变量：符号表数量计数器：st_num; 类型表和类型的项表 TypeTable row_id name type width d_row_num 1 student record 48 124 float 8 130 2 符号表： cur_pos item row_id type_id name cur_pos type offset d_row _num 1 1 age integer 4 120 2 1 tall float 8 124 符号表的链表：每个Block，以{}标识，都 有自己的符号表 lS{MS}N l M { st = new SymbolTable(); st. prior =cst; cst = st; } l N { cst = cst.prior; } l Eid { E.addr = Position(id); } class SymbolTable { Table T; int TID; int cur_pos; int offset； SymbolTable* prior; } 在符号表的链表中查找某个变量是否已经 申明 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-- ; } } } 变量声明的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); D1.offset = D.offset + T.width; } D1 { D.offset = D1.offset ; } 3) D 变量申明时，在当前符号表中查找变量名 是否有重复现象 NoDulplicate( id ) { i = cst.cur_pos; while( i >0 ) { if(cst[i-1].name == id) '申明出现重名' return fasle; i-- ; } return true; } 申明一个变量时，往当前符号表中添加一行， 表达该变量 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; } 以Block为单元为局部变量分配内存 l 块中的局部变量 int main( ) { int p = 2; MyFun( p ); if (p > 0) { float p = 4; s = substr(s1, p); } int i ; ...... } top p i top p i p top 对于每个Block中的局部变量，起始时在 栈中为其分配内存，末尾时释放 lS { M S } N lM { M.instr_pos = nextInstr; gen(null); st = new SymbolTable(); st. prior =cst; cst = st; } lN { if (cst.offset >0 ) { backReplace(M.instr_pos, push, cst.offset); gen('pop(', cst.offset,')'); } cst = cst.prior; } 中间代码的特性(5) 源程序中数据(变量的申明/定义）和代码混合交叉在一起，须要时 就定义，数据是以名字来标识。 中间代码中，数据和代码进行了分离。数据都规一到符号表中。在 中间代码中，数据的标识，不再是名字，而是它在符号表中的位置， 即Tid.Rid。 在机器代码中，数据的标识，是它的内存地址。中间代码将变量都 规一到符号表中，变量的内存地址于是就是符号表在内存的地址 （即基地址）+offset。第七章再介绍。 3. 其它数据结构——goto标签表 操作 l label =NewLabel（）； l AddLabel（label ':'）; l gen('goto' label); 全局计数器 goto 标签表 row_id tag value 1 L1 120 2 L2 200 3 这个表仅仅只有在LL分析中用到，在LR分析中不须要。 AddLabel（label ':'）这个函数，就是把nextInstr的值赋给指定 的标签行的value字段。 goto 的值，在随后中间代码优化，或者翻译成机器码时，查此表， 得到它的实际值。 观察 L1 : L3 : L3 : L0 : L2 : L4 : c=0 if (c>10) goto L1 goto L0 c=c-1 if(b>c) goto L3 goto L2 b=x+y if(a>b) goto L5 goto L4 a=x*y 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 SL1, 要展开S时，不知道L1将会是按照L SL1 还是L展开？导致每个语句的S.next =newLabel( ); 观察 L1 : L3 : L3 : L0 : L2 : L4 : c=0 if (c>10) goto L1 goto L0 c=c-1 if(b>c) goto L3 goto L2 b=x+y if(a>b) goto L5 goto L4 a=x*y 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 SL1, 要展开S时，就要确定S.next的值， 因为随后在B中生成goto 语句时，要用到。 在LR(1)分析中不一样，规约出S后，S.next的值才确定下来，此 时看当前输入符，如果是'}'，说明S是当前块中的最后一个语句; 临时变量 临时变量：E.addr = new temp(); 其含义是在当前符号表中，添加一行。返回所添加的这一行的 标识id，即Tid. Rid。 注意：每申明一个变量，也是往当前符号表中添加一行，随后 要使用这个变量时，再基于名字(id)到符号表中来查出它所指的 行，返回该行的标识id，即Tid. Rid，作为中间代码中对该变 量的标识。 6.3 类型和变量声明 • 类型检查(Type Checking) – 规则：保证运算分量的类型和运算符的预期类型要匹配。 • 翻译：确定变量的类型，需要的内存空间、计算数组元素的 地址（即存储空间布局（相对地址）、类型转换、选择正确 的运算符； 类型表达式 • 类型表达式（type expression）表示类型的结构，其定义如下： – 基本类型是一个类型表达式。如：boolean、integer，float， void等。 – 类名是一个类型表达式。 – 类型构造算子作用于类型仍是类型表达式 • array[数字，类型表达式] • record { <字段 • list类型 • set类型 类型>对的列表 } 类型表达式 从函数的角度来看待类型：类型构造算子：是用类型作为参数， 构造出新的类型； 从类型s到类型t的函数记作s t；按照函数的写法应该是t (s) l 例如：list()的结果是列表类型， 其元素的类型为; l class Cell { int info; Cell* next; } 类型名和递归类型； 可以给类型取名，例如上面的Cell。某种类型的变量， 数组类型的类型表达式，及其长度求解的SDD 产生式 语义规则 C.inh_t = B.t C.inh_w = B.w T.t = C.t, T.w = C.w B.t = integer, B.w=4 Bint B.t = float, B.w=8 Bfloat C[num]C1 C1.inh_t = C.inh_t C1.inh_w = C.inh_w C.t = array(num, C1.t) C.t= C.inh_t C C.w =C.inh_w LL文法，还是LR文法？ TBC T syn Bt syn inh C int inh syn [ 2 ] C1 sy inh n [3] C2 例， int [2][3] 类型表达式为 array(2, array(3,integer) 上述SDD的SDT 1)TB{C.inh_t = B.t; C.inh_w = B.w;} C { T.t = C.t; T.w = C.w; } 2)Bint {B.t= integer; B.w = 4; } 3)Bfloat {B.t= float; B.w = 8; } 4)C{ C1.inh_t = C.inh_t; C1.inh_w = C.inh_w; } [num {S.inh= num; } ] C1 { C.t = array(S.inh, C1.t); C.w =S.inh* C1.w } S 5)C {C.t = C.inh_t; C.w = C.inh_w; } 当S变成栈顶时，要弹出它，然后用它的产生式的右部倒着压入栈 中，现在S，而且这个产生式中没有动作。即S直接出栈。 在LR语法和LR分析中的 SDT 例如，int [2][3] 的类型表达式为array(2, array(3,integer)) 1) TBC { 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) Bint { B.t = integer; B.w = 4 } 3) Bfloat { B.t = float; B.w = 8 } 4) C C1[num] { s.push(num); } 5) C [num] { s = new stack(); s.push(num); } s是一个全局变量，该方案可行吗？ 记录类型的定义文法和SDT Trecord id { I } I I1T id； LL文法，还是LR文法？ I T id； Trecord id { H I } { UpdateWidth( Rid, I.width); } I I1 T id；{ AddItem( H.Rid, id, T.type); I.width = I1.width +T.width;} I T id；{ AddItem( H.Rid, id, T.type); I.width = T.width; } H {H.Rid = AddType( id, record); } 程序中的变量 l 每申明一个变量，便在符号表中添加一行。在中间代码表中， 变量的真实表达为：VTid.Rid l 变量要先申明后使用，因此每遇到一个变量，都要到符号表 中检查，检查它是否已经申明； int main( ) { l 就近匹配原则，确定是指哪个变量； int p = 2; MyFun( p ); l 变量申明的重复性检查； if (p > 0) { float p = 4; s = substr(s1, p); } } 局部变量的存储布局 l 变量有类型概念。类型又有宽度概念，即内存大小（Bytes）， l 变量有值和地址两个两个概念。变量值放在内存中，基于其内存 地址来访问变量的值； l 变量的类型信息存储在类型表中； l 变量信息存储在符号表中 l 每个块(block)都有自己的符号表； l root块的符号表存放了所有全局变量。root块的子块为函数块。 变量的作用域和内存布局scheme l 在一个函数里面，其所有局部变量放在一个连续的存储空间中， 变量在该空间的放置顺序与声明顺序一致； l 每申明一个变量，SDT所做处理： – 在当前块的符号表中，检查是否出现名字重复的变量定义； – 如果无，则在当前符号表中，增加一行(变量实例）： 书上的是：top.put(id.lexeme, T.type, offset)； 我们的是：AddVarible( ); l 见前面的内容。 将表达式三地址指令序列的SDD 产生式 1)Sid=E; 2)EE1 + E2 3)E-E1 4)E(E1) 5)Eid 语义规则 S.code =E.code || gen(top.get(id.lexeme) '=' E.addr) E.addr = new temp(), E.code =E1.code || E2.code || gen(E.addr '=’ E1.addr '+' E2.addr) E.addr = new temp() E.code =E1.code || gen(E.addr '=' 'minus' E1.addr ) E.addr = E1.addr E.code =E1.code E.addr = top.get(id.lexeme) E.code ='' 增量式翻译方案SDT 1)Sid=E; { gen(top.get(id.lexeme) '=' E.addr); } 2)EE1 + E2 { E.addr = new temp(); gen(E.addr '=’ E1.addr '+' E2.addr); } 3)E-E1 { E.addr = new temp() gen(E.addr '=' 'minus' E1.addr ); } 4)E(E1) { E.addr = E1.addr; } 5)Eid { E.addr = top.get(id.lexeme); } 数组元素在中间代码中表达 • 一个一维数组，元素从0到n-1编号，在内存中依次、连续存 储。其起始地址为base，第i个元素的地址为：base+i*w， w为元素的类型的宽度； • K维数组：将其视为一个一维数组，其元素的类型为一个k1维数组。A[i1][i2]…[ik]的地址： base+((…((i1*n2+i2)*n3+i3)…)*nk+ik)*w • 在符号表中有A的条项，A的条项中记录了A的类型，base 就是A的地址; 数组元素的文法含义 LL[E] Lid[E] L1是a的元素， L2是L1的元素 L2 例如: a[i][j] LL文法，还是LR文法？ [ L1 a [ E ] i 数组定义：int a[10][20], 对于数组元素a[5][6] a.type = array(10, array(20, integer)); L1.type = a.type.elem = array(20, integer); L2.type = = L1.type.elem = integer; E j ] 求数组元素的偏移地址 L2 L是a的元素 [ L a [ E ] i Lid[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); } E j ] 求数组元素的偏移地址 L L是L1的元素 [ L1 a [ E i LL1[E]; { L.array = L1.array_id ; L.type =L1.type.elem; t = new Temp(); L.addr = new Temp(); gen( t '=’ E.addr '*' L.type.width); gen( L.addr '=' L1.addr '+' t); } ] E j ] 数组元素作为因子 l L的代码只计算了偏移量； l 数组元素的值: L的数组基址加上偏移量; l 使用三地址指令x=a[i] 5)EL { E.addr = new temp(); AddCode(E.addr '=' L.array'[' L.addr ']'); } 给数组元素赋值 • 使用三地址指令a[i]=x SL = E; { gen(L.array '[' L.addr ']' '=' E.addr); } int a[2][3], c, i, j; 求赋值语句 c = c+a[i][j] 的三地址码序列 S c addr = Eaddr= c E addr=t5 + E addr=t4 = a; L array type=integer addr=t3 c addr [ L array = a type=array(3,integer) addr=t1 [ E addr=i ] a type=array(2, array(3, integer)) addr i addr 注释语法分析树 Eaddr=j ] j addr t1= i * 12 t2 = j * 4 t3 = t1 + t2 t4= a[ t3 ] t5 = c + t4 c= t5 类型检查和转换 • 类型系统：编译时，目标代码中的元素有 值，类型，存储地址 的概念；编译时就解决类型匹配问题。保证运行时，不再存在 有关类型的问题要处理，不会出错：强类型的语言； • 编译时来发现错误，以提高运行时效率、确定临时变量的大小。 例如 float b； int i; i= &b； 类型检查的两种方式 • 类型综合 例如， 对于表达式 E1+E2，已知E1和E2的类型，那么运算的 结果的类型是什么？ • 类型推导 – 根据语言结构的使用方式来确定该结构的类型 例：null(x)是一个测试列表是否为空的函数，则根据函数 null(x)可推断出x必定是一个列表，但x的元素类型未知。 – 不要求名字先定义的语言需要类型推导，如：ML 类型转换 • 设表达式x+i，x为浮点数、i为整数，则结果应该是浮点数 – x和i使用不同的二进制表示方式 – 浮点数相加，和整数相加使用不同的指令 – t1 = (float) i – t2 = x ＋ t1 类型的widening和narrowing • Java类型转换规则区分了拓宽转换和窄化转换 •编译器自动完成的转换为隐式转换， •程序员用代码指定的转换为显式转换。 处理类型转换的SDT EE1+E2 { E.type = max(E1.type, E2.type); a1=widen(E1.addr, E1.type, E.type); a2=widen(E2.addr, E2.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; } } { 函数/运算符的重载 • 重载（overload)是面向对象程序设计语言的一个特征 • 例：Java语言中’+’算符可表示串连接或加法运算，由操 作数的类型来区分 • 用户自定义的函数也可以重载，如： • Void err( ) {……} • Void err(String S) {……} • 通过查看参数个数，类型，顺序，就能解决的函数重载问题 语义分析和中间代码生成 •类型定义：放在类型表中, 有id,name,size；项表: name, type, size, offset,Tid, id； •变量申明：type，name，size,offset：先申明，后使用(包括 函数)；同一block中，变量不能重名； –每一个块都有自己的符号表，变量都放到符号表中，中间件 代码不再以名字标识数据，而用地址标识数据； •赋值语句，算术表达式，中间代码生成； •数组元素的中间代码表示； •类型检查和类型转换：运算结果的与宽的运算分量的看齐； LL分析中实现while语句翻译的框架 产生式： S while(B) S1 L1 L2 B S1 S.next L1: if ( B ) goto L2 goto B.false L2: S1.code goto L1 S.next: 继承属性： 综合属性： S.next S.code； B.false=S.next; B.code; B.true = newLabel(); S.code=L1 : || B.code || L2: ||S1.code || goto L1 || S.next: wihile语序例子，SDD c=20; while(c>10) c=c-1； x=1 L0 : L1 : L2 : 产生式 Swhile (B) S1 c=20 if (c>10) goto L1 goto L2 c=c-1 goto L0 x=1 语义规则 begin = newLable( ); B.true = newLable( ); B.false =S.next; S1.next= begin; S.code =label(begin) || B.code || label(B.true) || S .code LL分析中，while语句的SDT 产生式： S while (B) S1 c=20 L0: if (c>10) goto L1 goto L2 L1: c=c-1 goto L0 L2: x=1 产生式： S while ( B ) Y S1 Z while ( { begin = newLabel(); B.true= newLabel(); B.false = S.next；S1.next= begin; Y. label = B.true; Z.Label= begin; Z.nextLabel= S.next; AddLabel( begin ':'); } B ) {AddLabel( Y.Label ':'); } Y S1 { gen(' goto' Z.Label); AddLabel( Z.nextLabel ':'); } Z Y ； Z LL分析中的if语句 B 产生式： S if (B) S1 else S2 L1 if ( B ) goto L1 L2 goto L2 L1: S1.code goto S.next L2: S2.code S.next: S1 S2 S.next 继承属性： S.next B.false=newLabel(); B.true =newLabel(); 综合属性： S.code； B.code; S.code=B.code ||L1: || S1.code || goto S.next|| L2: || S2.code|| S.next: if语句例子，SDD c=20; if (a>b) d=x+y; else d=x*y x=1 产生式 3)Sif (B) S1 else S2 c=20 if(a>b) goto L3 goto L4 L3: d=x+y goto L5 L4: d=x*y L5: x=1 语义规则 B.true = newLable( ); B.false = newLable( ); S1.next= S.next; S2.next= S.next; S.code =B.code || label(B.true) || S1.code || gen('goto' S.next) || label(B.false) || S2.code || LL分析中实现if语句翻译的SDT 产生式： S if (B) S1 else S2 c=20 if(a>b) goto L3 goto L4 L3: d=x+y goto L5 L4: d=x*y L5: x=1 产生式： S if ( B) Y S1 else Z S2 W if ( { B.true= newLabel(); B.false = newLabel()；S1.next= S.next; S2.next= S.next; Y. label = B.true; Z.Label= B.false; Z.nextLabel =S.next; W. label = S.next; } B) {AddLabel( Y.Label ':'); } Y S1 else { gen(' goto' Z.nextLabel); AddLabel( Z.Label ':'); } Z S2 AddLabel( W.Label ':'); } Y ; Z ; W 表达式的类型 l 算术表达式E；优先级：（），*/, +/l 布尔表达式B；优先级：（），！，&&, || l 正则表达式R；优先级：（），*， 联接，| 在LL分析中，布尔表达式的翻译 产生式：S if （B）S1 c=20; if (a>b) d=x+y; x=1 c=20 if(a>b) goto L3 goto L5 L3: d=x+y L5: x=1 三个非终结符：S，B，S1 S.code=B.code ||L3: || S1.code || L5: 继承属性： S.next B.false=S.next; B.true =newLabel(); S1.next=S.next; 在LL分析中，布尔表达式的翻译 产生式：S if （B）S1 else S2 c=20; if (a>b) d=x+y; else d=x*y x=1 c=20 if(a>b) goto L3 goto L4 L3: d=x+y goto L5 L4: d=x*y L5: x=1 继承属性： S.next B.false=newLabel(); B.true =newLabel(); S1.next=S.next; S2.next=S.next; 四个非终结符：S，B，S1， S2 S.code=B.code ||L1: || S1.code || goto S.next|| L2: || S2.code|| S.next: 在LL分析中，布尔表达式的翻译 产生式：Swhile （B）S1 c=20; while (a>b) b=x+y; x=1 c=20 L0： if(a>b) goto L3 goto L4 L3: b =x+y goto L5 L4: x=1 继承属性： begin= newLabel(); S.next B.false=S.next; B.true =newLabel(); S1.next=begin; 三个非终结符：S，B，S1 S.code=L1: || B.code || L3: ||S1.code || goto S1.next|| S.next: 翻译布尔表达式B的SDD 产生式 语义规则 BE1 rel.op E2 B.code =E1.code || E2.code || gen('if' E1.addr rel.op E2.addr 'goto' B.true) || gen('goto' B.false) 在LL分析中，布尔表达式：BB1 && B2 的翻译 • if (x > 200 && x!= y) x = 0; 将其视作：if (B1 && B2) x = 0; if x > 200 goto L2 B1 goto L3 L2: if x != y goto L4 goto L3 L4: x=0 L3 : B2 继承属性： B1.true =newLabel(); B1.false = B.false； B2.true =B.true; B2.false = B.false； 翻译布尔表达式的SDD 产生式 BB1 && B2 语义规则 B1.true = newlabel( ); B1.false = B.false; B2.true = B.true; B2.false = B.false; B.code =B1.code || label (B1.true) || B2.code 注意：该文法不是LL文法，因产生式含左递归。 SDD仅只表达了逻辑关系，不是SDT。 在LL分析中，布尔表达式：BB1 || B2 的翻译 • if (x > 200 || x!= y) x = 0; 将其视作：if (B1 || B2) x = 0; 三地址码如下： if x > 200 goto L4 B1 goto L5 L5: if x != y goto L4 goto L3 L4: x=0 L3 : B2 继承属性： B1.true =B.true; B1.false = newLabel(); B2.true =B.true; B2.false = B.false； 在LL分析中，翻译布尔表达式的SDD 产生式 BB1 || B2 语义规则 B1.true = B.true; B1.false = newlabel( ); B2.true = B.true; B2.false = B.false; B.code =B1.code || label (B1.false) || B2.code 注意：该文法不是LL文法，因产生式含左递归。 SDD仅只表达了逻辑关系，不是SDT。 在LL分析中，布尔表达式的翻译例子 • if (x<100 || x > 200 && x!= y) x = 0; 优先级：先&&， 后 || S.next = L1; 三地址码如下： B.true =newLabel() = L2; B.false = S.next = L1; B1.true =B.true = L2; B1.false =newLabel() = L3; B2.true =B.true = L2; B2.false = B.false = L1; B2.1.true =newLabel() = L4; B2.1.false = B2.false = L1; B2.2.true = B2.true = L2; B2.2.false = B2.false = L1; if x < 100 goto L2 goto L3 L3: if x >200 goto L4 goto L1 L4: if x != y goto L2 goto L1 L2: x=0 L1 : LL语法分析中程序文法的表达 P S ① S if (B) S T 程序 if语句 T else S | ③ S id = E 赋值语句 ④ S while(B) S while语句 ⑤ S T id 变量定义语句 ⑥ S {L} 语句序列 LSL L E E+E | E*E | (E) 当前输入符为 } 或者$, 选择L | id B B && B | B || B | (B) | E > E | id | true | false 程序例子 c=0 L0 : if (c>10) goto L1 goto S(while).next L1 : c=c-1 if(a>b) goto L3 goto L4 L3 : d=x+y goto S(if).next L4 : d=x*y goto S(if).next S(if).next: goto L0 S(while).next: x=1 c=0; while(c>10) { c=c-1； if (a>b) then { d=x+y; } else { d=x*y; } } x=1 LL语法分析树例子 S {L} L S L S c=0 while (B) S S L c > 10 { L } x=1 S L c=c-1 S L if ( B ) S else S d=x+y d=x*y { c=0; while(c>10) { c=c-1； if (a>b) d=x+y; else d=x*y; } x=1 } LL分析中实现语句翻译的SDT——例子3 产生式： PS P { S.next= newLabel(); } S 产生式： S {L} P { { L.next = S.next;; } S } 产生式： L S L1 { if (当前输入符=='if' || 'while' ) S.next= newLabel(); L1.next= L.next; } S L1 产生式： L 不做任何事情, 本来是要给综合属性赋值 DFA的优势——LR语法分析实用的原因 I4 S→ id = E id I0 P→S S→ {S} S→ if(B) S S→ while(B) S S→ id = E S { { if I3 S→if( B ) S S→ {S} S→ if(B) S S→ while(B) S S→ id = E if I1 P→S I2 S→ {S} S→ SS S→ if(B) S S→ while(B) S S→ id = E I6 S S→if( B ) S I5 S→ {S} S→ SS S S→ if(B) S S→ while(B) S S→ id = E } S I7 S→ {S} I8 S→ SS LR分析中实现控制语句翻译的SDT 产生式： S while(B) S1 LL分析中， L1 LR分析中， 定义了继承属性： 则定义综合属性： S.next S.nextList； B.true B.falseList; B.false B.trueList； L2 B S1 S.next 实现同一目标：生成中间代码 S.code=L1 : || B.code || L2: ||S1.code || goto L1 || S.next: goto分两种：前向，后向 c=20; while(c>10 || a>b) c=c-1； x=1 c=20 L0: if (c>10) goto L1 if (a>b) goto L1 goto L2 L1: c=c-1 goto L0 L2: x=1 综合属性： S.nextList； B.falseList; B.trueList 前向 一旦变得已知，就要记 录下来，用于回填 后向 对L0, 在后面要用它，因 此要记录下来 对前向goto，使用S.nextList， B.falseList，B.trueList来记录要回填的行 c=20; while(c>10 || a>b) c=c-1； x=1 产生式：S while(B) S1 中间代码表： Rid L0: if (c>10) goto L1 if (a>b) goto L1 goto L2 L1 : nextInstr code 1 c=20 2 if (c>10) goto X 3 if (a>b) goto X 4 goto X 5 B被规约出来，得到B.falseList = {4}; B.trueList = {2,3} 接下来就要生成S1的代码了，此刻，B.true= 5，B.trueList中 goto 目标地址变成已知，于是执行回填操作。 LR分析中，综合属性的含义 c=20; while(c>10 || a>b) c=c-1； x=1 c=20 L0: if (c>10) goto L1 if (a>b) goto L1 goto L2 L1: c=c-1 goto L0 L2: x=1 BB1 || B2 B.trueList = B1.trueList B2.trueList B.falseList = B2.falseList 综合属性： B.trueList 综合属性： B.falseList; 综合属性： S.nextList = B.falseList； LR分析中实现while语句翻译的SDT 产生式： S while (B) S1 c=0 L0: if (c>10) goto L1 if (a>b) goto L1 goto L5 L1: c=c-1 goto L0 L5: x=1 产生式： S while (M B) S1 Swhile (M B) { backpatch(B.truelist, nextinstr); } S1 { backpatch(S1.nextlist, M.instr); gen('goto' M.instr); S.nextlist = B.falselist; } M { M.instr = nextinstr }; LR分析中，一个语句的next变 得确定的时刻 L1: L3: L3: L0: L2: L4: c=0 if (c>10) goto L1 goto L0 c=c-1 if(b>c) goto L3 goto L2 b=x+y if(a>b) goto L5 goto L4 a=x*y x=1 c=0; if(c>10) { c=c-1； if (b>c) { b=x+y; if （a>b) { a=x*y; } } } x=1 在S规约出来之后，看当前输入符，如果不是’}’，意味着该语句后 接另一语句，即SSS。此时S.next 变得确定，就是nextInstr； 如果是'}'，则说明是S是子句的末尾句，它的.next还不确定 。 LR分析中，语句与语句之间的关系 L1: L3: L3: L0: L2: L4: c=0 if (c>10) goto L1 goto L0 c=c-1 if(b>c) goto L3 goto L2 b=x+y if(a>b) goto L5 goto L4 a=x*y x=1 c=0; if(c>10) { c=c-1； if (b>c) { b=x+y; if （a>b) { a=x*y; } } } x=1 父子关系：Sif (B) S1 { S.nextlist = B.falselist + S1.nextlist; } 兄弟关系：SS1{ backpatch(S1.nextlist，nextInstr); } S2 {S.nextlist = S2.nextlist; } LR分析中实现if语句翻译的SDT 产生式： S if (B) S1 else S2 产生式： S if (B) S1 else S2 if ( a>b ) goto L1 Sif (B) { backpatch(B.truelist, nextinstr); } if ( c>10 ) goto L1 S1 else goto L2 { S.nextlist = merge(S1.nextlist, L1: d= x+y goto S.next L2: d= x*y S.next: makelist(nextinstr)); gen('goto _'); backpatch(B.falselist, nextinstr)；} S2 { S.nextlist = merge(S.nextlist, S2.nextlist); } LR分析中实现布尔表达式翻译的回填SDT BE1 rel E2 { B.truelist = makelist(nextinstr); B.falselist = makelist(nextinstr + 1); gen('if' E1.addr rel.op E2.addr 'goto _'); gen('goto _'); } LR分析中实现布尔表达式的回填翻译SDT BB1 && { Backpatch(B1.truelist, nextinstr); } B2 { B.truelist = B2.truelist; B.falselist = merge(B1.falselist, B2.falselist); } BB1 || { Backpatch(B1.falselist, nextinstr); } B2 { B.falselist = B2.falselist; B.truelist = merge(B1.truelist, B2.truelist); } 回填例子：x<100 || x>200 && x!=y 假设从nextinstr = 100开始 if (x<100 || x > 200 && x!= y ) x = 0; i=102 102: if x>200 goto _ 103: goto _ t={100,104} B f={103,105} 5 B1 t={100} t={104} i=104 B f={103,105} || 4 f={101} x<100 B2 t={102} && t={104}B3 f={103} x>200 100: if x<100 goto _ 101: goto _ f={105} x！=y 104: if x!=y goto _ 105: goto _ 106: x=0 107: B.code || Label(B.true) || S1.code || Label(B.false) 中间代码优化——减少goto指令 例：将if (x<100 || x > 200 && x!= y ) x = 0;翻译成三地址 码。 if x<100 goto L2 goto L3 L3: if x> 200 goto L4 goto L1 L4: if X !=y goto L2 goto L1 L2 : x = 0 L1 : if(B) S1 多余 ifFalse x>200 goto L1 ifFalse x!=y goto L1 B的指令之后就是S1， B.true不须要, 设为fall goto的优化：在LL分析中，goto的目标， 可能也是goto c=0 L0: if (c>10) goto L1 goto S(while).next L1: c=c-1 if(a>b) goto L3 goto L4 L3: d=x+y goto S(if).next L4: d=x*y S(if).next: goto L0 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 观察: 在LL分析中，可能一行的前面有多个 goto标签 L1: L3: L3: L0: L2: L4: c=0 if (c>10) goto L1 goto L0 c=c-1 if(b>c) goto L3 goto L2 b=x+y if(a>b) goto L5 goto L4 a=x*y x=1 c=0; if(c>10) { c=c-1； if (b>c) { b=x+y; if （a>b) { a=x*y; } } } x=1 原因是：控制语句嵌套，而且被嵌套的控制语句在其所在的块中 为最后一个语句。存在嵌套关系的三个if语句的next都是x=1语句； LR分析中实现其它语句翻译的SDT 产生式： Sid = E Sid = E; { S.nextlist =null; } 产生式： S {S1} S{S1} { S.nextlist =S1.nextlist ; } 产生式： S S1 S2 SS1 { backpatch(S1.nextlist, nextinstr); } S2 { S.nextlist = S2.nextlist; } 我们走到哪儿了？ 给定上下文无关文法G，在第四章，解决了的问题： lG是不是LL(1)文法，是不是LR(1)文法的问题； l文法 LL文法的预测分析表，LR文法的语法分析表 语法分 析器源程序生成工具； 语义分析，中间代码的生成，不是独立的环节，而是在语法分析 的过程（LL分析中的展开，LR分析中的规约，）中附带完成； 第五章， 在文法的产生式上加上动作，构造SDT。有了SDT，语 法分析，语义分析，中间代码生成，这三个工作的源程序就可由 语法分析器生成工具来自动得到； LR语法分析中程序文法的表达 P S ① S if (B) S ② S if (B) S else S ③ S id = E ④ S while(B) S ⑤ S T id ⑥ S {S} ⑦ SSS B B && B | B || B | (B) | E> E | id | true | false E E+E | E*E | (E) | id LR语法分析树例子 S {S} S S S c=0 while ( B c > 10 S ) S x=1 { S } { c=0; while(c>10) { c=c-1； if (a>b) d=x+y; else d=x*y; } x=1 } S S c=c-1 if ( B ) S else S d=x+y d=x*y 语言的DFA I4S→ id = E id I0 P→S S→ {S} S→ if(B) S S→ while(B) S S→ id = E S { { if I3 S→if( B ) S S→ {S} S→ if(B) S S→ while(B) S S→ id = E if S I1 P→S I2 S→ {S} S→ SS S→ if(B) S S→ while(B) S S→ id = E I6 S→if( B ) S I5 S→ {S} S→ SS S S→ if(B) S S→ while(B) S S→ id = E } S I7 S→ {S} I8 S→ SS S 对LL分析的观察 {L} { c=0; while(c>10) { c=c-1； if (a>b) d=x+y; else d=x*y; } x=1 } L S L S c=0 while (B) S S L c > 10 { L } x=1 S L c=c-1 S L if ( B ) S else S d=x+y d=x*y 在LL(1)中，L SL1 对于S，它怎么知道自己是不 是当前块中的最后一个语句？ 观察 L1 : L3 : L3 : L0 : L2 : L4 : c=0 if (c>10) goto L1 goto L0 c=c-1 if(b>c) goto L3 goto L2 b=x+y if(a>b) goto L5 goto L4 a=x*y 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 SL1, 要展开S时，不知道L1将会是按照L SL1 还是L展开？导致每个语句的S.next =newLabel(); 翻译布尔表达式的SDD 产生式 6)BB1 || B2 产生式 6)BB1 || B2 语义规则 B1.true = B.true; B1.false = newlabel( ); B2.true = B.true; B2.false = B.false; B.code =B1.code || label(B1.false) || B2.code 语义规则 if B.true = fall then B1.true = newLabel(); else B1.true = B.true; B1.false = fall; B2.true = B.true; B2.false = B.false; if B.true = fall then B.code =B1.code || B2.code || label(B1.true) else B.code =B1.code || label(B1.false) || B2.code 求布尔表达式的值, 比如:x= a200 && x!=y 假设从nextinstr = 100开始 100: if x<100 goto _ 101: goto _ 102: if x>200 goto _ 103: goto _ t={100,104} B f={103,105} 5 B1 t={100} f={101} x<100 || t={104} Mi=102 B f={103,105} 4 B2 t={102} && f={103} x>200 t={104} B3f={105} M i=104 x！=y 104: if x!=y goto _ 105: goto _ 回填例子：x<100 || x>200 && x!=y 假设从nextinstr = 100开始 if (x<100 || x > 200 && x!= y ) x = 0; i=102 102: if x>200 goto _ 103: goto _ t={100,104} B f={103,105} 5 B1 t={100} t={104} i=104 B f={103,105} || 4 f={101} x<100 B2 t={102} && t={104}B3 f={103} x>200 100: if x<100 goto _ 101: goto _ f={105} x！=y 104: if x!=y goto _ 105: goto _ 106: x=0 107: B.code || Label(B.true) || S1.code || Label(B.false) 观察: 在LL分析中，可能一行的前面有多个 goto标签 L1: L3: L3: L0: L2: L4: c=0 if (c>10) goto L1 goto L0 c=c-1 if(b>c) goto L3 goto L2 b=x+y if(a>b) goto L5 goto L4 a=x*y x=1 c=0; if(c>10) { c=c-1； if (b>c) { b=x+y; if （a>b) { a=x*y; } } } x=1 原因是：控制语句嵌套，而且被嵌套的控制语句在其所在的块中 为最后一个语句。存在嵌套关系的三个if语句的next都是x=1语句； 观察：在LL分析中，goto的目标，可能也 是goto c=0 L0: if (c>10) goto L1 goto S(while).next L1: c=c-1 if(a>b) goto L3 goto L4 L3: d=x+y goto S(if).next L4: d=x*y S(if).next: goto L0 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。 LR分析中，能克服上述两个问题 L1: L3: L3: L0: L2: L4: c=0 if (c>10) goto L1 goto L0 c=c-1 if(b>c) goto L3 goto L2 b=x+y if(a>b) goto L5 goto L4 a=x*y 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 LR分析中，一个语句的next变得 确定的时刻 L1: L3: L3: L0: L2: L4: c=0 if (c>10) goto L1 goto L0 c=c-1 if(b>c) goto L3 goto L2 b=x+y if(a>b) goto L5 goto L4 a=x*y x=1 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； 在LL分析中，goto的目标可能也是goto， LR分析能优化它 c=0 L0: if (c>10) goto L1 goto S(while).next L1: c=c-1 if(a>b) goto L3 goto L4 L3: d=x+y goto S(if).next L4: d=x*y S(if).next: goto L0 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 此例中 Swhile(B) S1; 这里S1{S2}， S2SaSb，Sb是if语句。 是其所在块的last语句，因此Sb.next = S2.next =S1.next =L0。 当Sb要规约出来时，因当前输入符是’}’，意味着S1到了末尾。 其它语句的回填(3) SA; { S.nextlist =null; } S{S1} { S.nextlist =S1.nextlist ; } SS1 { backpatch(S1.nextlist, nextinstr); } S2 { S.nextlist = S2.nextlist; } Break、Continue语句 • break，continue语句只能用在循环语句中，如while中。否 则就是语法错误。 • 这是一个上下文相关问题；因此，不存在用产生式来表达，属 于语义分析中的内容； Break、Continue的翻译方案 l 循环语句可能嵌套，因此要设一个全局的循环标志栈。 l 每进入一个循环语句时，就将其begin压入该栈中，规约时， 从该栈中弹出。 l 当遇到一个break/continue语句时，如果循环标志栈为空；则 表明当前不在循环语句中，出现了语法错误； Break、Continue的翻译方案(cont.) l 另有全局变量：list * breaklist。每遇到一个break语句时, breaklist =merge(breaklist, makelist(nextInstr)); 然后生成一 条悬空goto语句：Gen('goto _'); l 每遇到一个continue语句，则生成一条goto语句：Gen('goto' element[top]); l 当规约出一个循环语句S时： 1)从栈中弹出当前循环语句的begin； 2) S->nextlist =merge(S->nextlist, breaklist); 3) 复位 breaklist：S_breaklist = null； 6.8 switch语句的SDT • switch语句结构： switch (E) { case V1: S1; case V2: S2; … case Vn-1 :Sn-1; default: Sn; } 其文法：Sswitch(E) {T default: S } TT case E: S | case E: S 翻译法1 L1 : L2 : L3 : Ln-1: T=E if TＶ1 goto L2 S1的代码 goto next if TＶ2 goto L3 S2的代码 goto next … if TＶn-1 goto Ln Sn-1的代码 goto next Ln : Sn的代码 next: 翻译法2 L1 : … Ln-1: T=E goto test 关于S1的中间码 goto next 关于Sn-1的中间码 goto next Ln : 关于Sn的中间码 goto next test: if T=Ｖ1 goto L1 if T=Ｖ2 goto L2 ........… if T=Ｖn-1 goto Ln-1 goto Ln next: 用来翻译switch语句的case三地址代 码指令 Case ｔ Ｖ1 L1 Case ｔ Ｖ2 L2 Case ｔ Ｖn-1 Ln-1 Case ｔ t Ln … next: 函数及其调用的中间代码 • 在三地址码中，函数调用被拆分为准备进行调用时的参 数求值，然后是调用本身。 设a为int类型的数组， n = f(a[i]); 的三地址码： t1=i*4 t2=a[t1] param t2 t3 = call f, 1 n = t3 函数定义和调用的文法，SDT 函数定义文法：F T id(P) {S} P P, T id | T id | 函数调用文法： E id(A) AA, E | E | 语义分析：1）函数先定义，后调用；要有可区分性； 2）函数返回值要与函数的类型一致； 3）函数调用，参数要匹配； 同理，要建立函数定义表，和函数参数表，来实现上述语义分析； 请写出实现上述语义分析的SDT； 过程调用的翻译 • 翻译方法：把实参的地址逐一放在转子指令的前面. 例如， CALL S(A，X+Y) 翻译为: t1=X+Y param A param t1 call S, 2 第六章 中间代码生成 语义分析和 中间代码生成 DAG 图 中间代 码表示 类型检查 和翻译 三地 址码 表达式 翻译 静态单 赋值 中间代 码生成 控制流 翻译 回填 过程 翻译 谢 谢 谢 谢！
chaper 6 - 中间代码生成 2019.pdf 
