《编译原理 中间代码生成教材》由会员分享，可在线阅读，更多相关《编译原理 中间代码生成教材（59页珍藏版）》请在金锄头文库上搜索。
1、第八章 中间代码生成 学习内容 m三地址码表示方法 m声明语句的翻译 m赋值语句的翻译：数组寻址 m布尔表达式的翻译 mcase语句的翻译 mbackpatching技术的实现 m过程调用的翻译 8.1 中间语言 8.1.1 图表示 a := b * -c + b * -c 语法树方式表示 后缀表示语法树的线性表示方式 a b c uminus * b c uminus * + assign 语法制导定义构造语法树 PRODUCTIONSemantic Rule S id := E S.nptr = mknode (assign, mkleaf(id, id.entry), E.nptr) E
2、 E1 + E2 E.nptr = mknode(+, E1.nptr,E2.nptr) E E1 * E2 E.nptr = mknode(*, E1.nptr,E2.nptr) E - E1 E.nptr = mknode(uminus, E1.nptr) E ( E1 ) E.nptr = E1.nptr E id E.nptr = mkleaf(id, id.entry) 语法树的计算机内部表示 8.1.2 三地址码 mThree-Address Code m一般形式：x := y op z m语法树、dag的线性化表示 t1 := -ct1 := -c t2 := b * t1t2
3、:= b * t1 t3 := -ct5 := t2 + t2 t4 := b * t3a := t5 t5 := t2 + t4 a := t5 8.1.3 三地址码语句类型 1.二元运算：x := y op z 2.一元运算：x := op y 3.复制语句：x := y 4.无条件转移：goto L 5.条件转移：if x relop y goto L 6.函数调用：param x1 param x2 param xn call p, n 7.数组：x := y i ，x i := y 8.指针：x := E.code = E1.code | E2.code | | gen(E.plac
4、e := 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.code = E1.code | | gen(E.place := uminus E1.place) E ( E1 ) E.place= E1.place ; E.code = E1.code E id E.place = id.entry ; E.code = 控制流语句的翻译 mwhile语句：
5、S while E do S1 m翻译为S.begin:E.code if E.place = 0 goto S.after S1.code goto S.begin S.after: m语法制导定义： S.begin = newlabel; S.after = newlabel ; S.code = gen(S.begin :) | E.code | gen(if E.place = 0 goto S.after) | S1.code | gen(goto S.begin) | gen(S.after :) 8.1.5 三地址码的实现 m四元组，三元组 三元运算的实现拆分 mxi := y
6、mx := yi 间接三元组实现方式 8.2 声明语句的翻译 m8.2.1 过程内部的声明 PRODUCTION Semantic Rule P M D M offset:=0 D id : T addtype(id.entry, T.type, offset) offset:=offset + T.width T charT.type = char; T.width = 4; T integer T.type = integer ; T.width = 4; T array num of T1 T.type=array(num.val,T1.type) T.width = num.val *
7、 T1.width T T1 T.type = pointer(T1.type); T1.width = 4 8.2.2 作用域的处理 处理作用域的翻译模式 P M D addwidth(top(tblptr), top(offset); pop(tblptr); pop(offset) M t:=mktable(null); push(t, tblptr); push(0, offset) D D1 ; D2 D proc id ; N D ; S t:=top(tblpr); addwidth(t,top(offset); pop(tblptr); pop(offset); enterpr
8、oc(top(tblptr), id.name, t) N t:=mktable(top(tblptr); push(t,tblptr); push(0,offset); D id : T enter(top(tblptr), id.name, T.type, top(offset); top(offset):=top(offset) + T.width 符号表栈 内存占 用量栈 8.2.3 记录类型的处理 m创建独立的符号表 T record L D end T.type = record(top(tblptr); T.width = top(offset); pop(tblptr); po
9、p(offset); L t = mktable(null); push(t, tblptr); push(0, offset); 8.3 赋值语句 8.3.1 符号表中的名字 S id := E p = lookup(id.name); if (p != null) emit(p := E.place); else error; E E1 + E2 E.place = newtemp; emit(E.place := E1.place + E2.place; E E1 * E2 E.place = newtemp; emit(E.place := E1.place * E2.place; E
10、 - E1 E.place = newtemp; emit(E.place := uminus E1.place; E ( E1 ) E.place = E1.place E id p = lookup(id.name); if (p != null) E.place = p; else error; 在符号表中 查找标识符 8.3.2 临时名字的重用 mnewtemp每次产生不同名字，浪费空间 mEE1 + E2 计算E1t1 计算E2t2 t = t1 + t2 m计算E2的临时变量的生存期都包含在t1内 m重用算法计数器c，初始为0 q临时名字作为运算对象使用c- q生成新的临时名字$c
11、，c+ 例8.1 mx = a * b + c * d e * f $0, $1为运算对象，c减2 ，变为0结果又保存在 $0 8.3.3 数组元素寻址 m一维数组 qtype Alowhigh; q计算Ai的地址 A的起始地址base 数组元素大小w Ai与A起始位置的“距离”(i low) * w 最终结果：base + (i low) * w i * w + (base low * w) (base low * w)为常量，可在编译时计算 Ai base (i low) * w 数组元素寻址（续） m二维数组： qtype Alow1high1, low2high2 q计算Ai1, i2
12、地址 数组的数组，两次利用一维数组计算方法 行：n2=high2low2+1个元素的一维数组元素 二维数组：n1=high1-low1+1个“行”的一维数组 i1行的位置 (i1 - low1) * n2 Ai1, i2距行开始位置的距离：i2 low2 最终结果base + (i1 - low1) * n2 + i2 - low2) * w (i1*n2) + i2)*w + (base (low1*n2) + low2)*w) (base (low1*n2) + low2)*w)为常量 Alow1, low2 Alow1, high2 Ai1, low2 Ai1, i2 base n2 *
13、 w 数组元素寻址（续） m扩展到多维情况 qtype Alow1high1, , lowkhighk q计算Ai1, i2, , ik的地址 q最终结果 (i1n2 + i2)n3 + i3)nk + ik) * w + base (low1n2+low2)n3 + low3)nk + lowk) * w 实现方法 Lid Elist | id L Elist | id ElistElist , E | E ElistElist , E | id E m(i1n2 + i2)n3 + i3)nm + im的计算 e1=i1，em=em-1*nm + im mElist.ndim：数组维数 m
14、Elist.place：下标表达式计算结果，em mlimit(array, j)：第j维的大小，nm mL.place：基地址（地址计算常量部分） mL.offset：偏移，普通变量为null 8.3.4 数组元素寻址的翻译模式 m文法 (1)S L := E (2)E E + E (3)E ( E ) (4)E L (5)L Elist (6)L id (7)Elist Elist , E (8)Elist id E 数组元素寻址的翻译模式(续) (1)S L := E if (L.offset = null) emit(L.place := E.place); else emit(L.p
15、lace L.offset := E.place); (2)E E1 + E2 E.place = newtemp; emit(E.place := E1.place + E2.place); (3)E ( E1 ) E.place = E1.place; 普通变量 ？数组？ 数组元素寻址的翻译模式(续) (5)L id L.place = id.place; L.offset = null; (6)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;
