编译原理中间代码生成

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 RuleS id := E S.nptr = mknode (assign,mkleaf(id, id.entry), E.nptr) E E1 + E2 E.nptr =

2、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 Codem一般形式：x := y op zm语法树、dag的线性化表示t1 := -ct1 := -ct2 := b * t1t2 := b * t1t3 := -ct5 := t

3、2 + t2t4 := b * t3a := t5t5 := t2 + t4a := t58.1.3 三地址码语句类型m二元运算：x := y op zm一元运算：x := op ym复制语句：x := ym无条件转移：goto Lm条件转移：if x relop y goto Lm函数调用：param x1 param x2 param xn call p, nm数组：x := y i ，x i := ym指针：x := &y，x := *y语法制导翻译生成三地址码m赋值语句：id := Em利用属性qE.place：保存E的值的名字qE.code：计算E的三地址代码mnewtemp：生成临

4、时变量名mgen：输出一条三地址码指令赋值语句的翻译PRODUCTION Semantic RuleS id := E S.code = E.code | gen(id.place := E.place) 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 - E

5、1 E.place= newtemp ; E.code = E1.code | gen(E.place := uminus E1.place) E ( E1 ) E.place= E1.place ; E.code = E1.codeE id E.place = id.entry ; E.code = 控制流语句的翻译mwhile语句：S while E do S1m翻译为S.begin:E.codeif E.place = 0 goto S.afterS1.codegoto S.beginS.after:m语法制导定义：S.begin = newlabel;S.after = newlabe

6、l ;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 := ymx := yi间接三元组实现方式8.2 声明语句的翻译m8.2.1 过程内部的声明PRODUCTION Semantic RuleP M D M offset:=0 D id : T addtype(id.entry, T.type, offset) offset:=offset + T

7、.width T charT.type = char; T.width = 4; T integer T.type = integer ; T.width = 4; T array num of T1T.type=array(num.val,T1.type) T.width = num.val * T1.widthT T1 T.type = pointer(T1.type); T1.width = 48.2.2 作用域的处理处理作用域的翻译模式P M D addwidth(top(tblptr), top(offset); pop(tblptr); pop(offset) M t:=mktab

8、le(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);enterproc(top(tblptr), , t)N t:=mktable(top(tblptr); push(t,tblptr);push(0,offset);D id : T enter(top(tblptr), , T.type, top(offset);top(offset):=top(of

9、fset) + T.width符号表栈内存占用量栈8.2.3 记录类型的处理m创建独立的符号表T record L D end T.type = record(top(tblptr); T.width = top(offset); pop(tblptr); pop(offset); L t = mktable(null); push(t, tblptr); push(0, offset); 8.3 赋值语句8.3.1 符号表中的名字S id := E p = lookup(); if (p != null) emit(p := E.place); else error; E E1

10、 + 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 - E1 E.place = newtemp; emit(E.place := uminus E1.place; E ( E1 ) E.place = E1.place E id p = lookup(); if (p != null) E.place = p; else error; 在符号表中查找标识符8.3.2 临时名

11、字的重用mnewtemp每次产生不同名字，浪费空间mEE1 + E2计算E1t1计算E2t2t = t1 + t2m计算E2的临时变量的生存期都包含在t1内m重用算法计数器c，初始为0q临时名字作为运算对象使用c-q生成新的临时名字$c，c+例8.1mx = a * b + c * d e * f$0, $1为运算对象，c减2，变为0结果又保存在$08.3.3 数组元素寻址m一维数组qtype Alow.high;q计算Ai的地址A的起始地址base数组元素大小wAi与A起始位置的“距离”(i low) * w最终结果：base + (i low) * w i * w + (base low

12、* w)(base low * w)为常量，可在编译时计算Aibase(i low) * w数组元素寻址（续）m二维数组：qtype Alow1.high1, low2.high2q计算Ai1, i2地址数组的数组，两次利用一维数组计算方法行：n2=high2low2+1个元素的一维数组元素二维数组：n1=high1-low1+1个“行”的一维数组i1行的位置 (i1 - low1) * n2Ai1, i2距行开始位置的距离：i2 low2最终结果base + (i1 - low1) * n2 + i2 - low2) * w(i1*n2) + i2)*w + (base (low1*n2)

13、+ low2)*w)(base (low1*n2) + low2)*w)为常量Alow1, low2Alow1, high2Ai1, low2Ai1, i2basen2 * w数组元素寻址（续）m扩展到多维情况qtype Alow1.high1, , lowk.highkq计算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 ,

14、E | id Em(i1n2 + i2)n3 + i3)nm + im的计算e1=i1，em=em-1*nm + immElist.ndim：数组维数mElist.place：下标表达式计算结果，emmlimit(array, j)：第j维的大小，nmmL.place：基地址（地址计算常量部分）mL.offset：偏移，普通变量为null8.3.4 数组元素寻址的翻译模式m文法mS L := EmE E + EmE ( E )mE LmL Elist mL idmElist Elist , E(1)Elist id E数组元素寻址的翻译模式(续)mS L := E if (L.offset =

15、 null) emit(L.place := E.place); else emit(L.place L.offset := E.place); mE E1 + E2 E.place = newtemp; emit(E.place := E1.place + E2.place); mE ( E1 ) E.place = E1.place; 普通变量？数组？数组元素寻址的翻译模式(续)mL id L.place = id.place; L.offset = null; mElist Elist1 , E t = newtemp; m = Elist1.ndim + 1; emit(t := El

16、ist1.place * limit(Elist1.array, m);emit(t := t + E.place);Elist.array = Elist1.array;Elist.place = t; Elist.ndim = m; mElist id E Elist.array = id.place; Elist.place = E.place; Elist.ndim = 1; em-1em数组元素寻址的翻译模式(续)mE L if (L.offset = null) E.place = L.place; else E.place = newtemp; emit(E.place := L

17、.place L.offset ); mL Elist L.place = newtemp; L.offset = newtemp;emit(L.place := c(Elist.array);emit(L.offset := Elist.place * width(Elist.array); 地址计算常量部分例8.21020的数组，low1=low2=1, n1=10, n2=20, w=4翻译x := Ay, z生成的三地址码：t1 := y * 20t1 := t1 + zt2 := ct3 := 4 * t1t4 := t2t3x := t48.3.5 类型转换mEE1 + E2的语义

18、动作E.place = newtemp;if (E1.type = integer & E2.type = integer) emit(E.place := E1.place int+ E2.place; E.type = integer; else if (E1.type = real & E2.type = real) emit(E.place := E1.place real+ E2.place; E.type = real; else if (E1.type = integer & E2.type = real) u = newtemp; emit(u := inttoreal E1.

19、place);emit(E.place := u real+ E2.place; E.type = integer; else if (E1.type = real & E2.type = integer) 类型转换例子mx := y + i * jx、y实数i、j整数t1 := i int* jt3 := inttoreal t1t2 := y real+ t3x := t28.3.6 记录（结构）域的访问m保存每个域的类型和相对地址符号表mlookup可用于域名字m独立符号表mt：符号表指针，record(t)T.typem翻译 + 1qp的类型pointer(record(t

20、)qp的类型record(t)q得到t查找info域8.4 布尔表达式的翻译mEE or E | E and E | not E | (E) | id relop id | true | falsem8.4.1 两种翻译方式q数值编码：0false，非0tureq控制流语句属性true布尔表达式为真时跳转到的程序位置属性false布尔表达式为假时跳转到的程序位置m短路求值qE1 or E2，E1=false才对E2求值q注意副作用问题：函数调用8.4.2 用数值表示布尔值ma or b and not c t1 := not ct2 := b and t1t3 := a or t2ma b i

21、f a b then 1 else 0100:if a b goto 103101:t := 0102:goto 104103:t := 1104:翻译模式EE1 or E2 E.place = newtemp;emit(E.place := E1.place or E2.place); EE1 and E2 E.place = newtemp;emit(E.place := E1.place and E2.place); Enot E1 E.place = newtemp;emit(E.place := not E1.place); E( E1 ) E.place = E1.place; E

22、id1 relop id2 E.place = newtemp;emit(if id1.place relop.op id2.place goto nextstat + 3);emit(E.place := 0);emit(goto nextstat + 2);emit(E.place := 1); Etrue E.place = newtemp; emit(E.place := 1); Efalse E.place = newtemp; emit(E.place := 0); 例8.3m翻译a b or c d and e f100: if a b goto 103 107: t2 := 1

23、101: t1 := 0108: if e f goto 111102: goto 104 109: t3 := 0103: t1 := 1110: goto 112104: if c d goto 107 111: t3 := 1105: t2 := 0112: t4 := t2 and t3106: goto 108 113: t5 := t1 or t48.4.3 控制流语句的翻译Sif E then S1 | if E then S1 else S2 | while E do S1语法制导定义ifS if E then S1E.true = newlabel; E.false = S.

24、next;S1.next = S.next;S.code = E.code | gen(E.true :) | S1.code语法制导定义if-elseSif E then S1 else S2E.true = newlabel; E.false = newlabel;S1.next = S.next; S2.next = S.next;S.code = E.code | gen(E.true :) | S1.code | gen(goto S.next) | gen(E.false :) |S2.code语法制导定义Swhile E do S1S.begin = newlabel; E.tr

25、ue = newlabel;E.false = S.next; S1.next = S.begin;S.code = gen(S.being :) | E.code | gen(E.true :) |S1.code | gen(goto S.begin)8.4.5 布尔表达式翻译为控制流语句EE1 or E2E1.true = E.true; E1.false = newlabel;E2.true = E.true; E2.false = E.false;E.code = E1.code | gen(E1.false :) | E2.code EE1 and E2E1.true = newla

26、bel; E1.false = E.false;E2.true = E.true; E2.false = E.false;E.code = E1.code | gen(E1.true :) | E2.code Enot E1E1.true = E.false; E1.false = E.true; E.code = E1.code; E( E1 )E1.true = E.true; E1.false = E.false; E.code = E1.code; Eid1 relop id2E.code = gen(if id1.place relop.op id2.place goto E.tru

27、e) | gen(goto E.false)EtrueE.code = gen(goto E.true);EfalseE.code = gen(goto E.false);例8.4a b or c d and e f生成代码：if a b goto Ltruegoto L1L1:if c d goto L2goto LfalseL2:if e f goto Ltruegoto Lfalse例8.5while a b doif c d thenx := y + zelsex := y z生成代码为：L1:if a b goto L2L4:t2 := y - zgoto Lnextx := t2L

28、2:if c d goto L3goto L1goto L4Lnext:L3:t1 := y + zx := t1goto L18.4.6 混合翻译方式EE + E | E and E | E relop E | idEE1 + E2对应的语义规则为：E.type = arith;if (E1.type = arith and E2.type = arith) E.place = newtemp;E.code = E1.code | E2.code | gen(E.place := E1.place + E2.place); else if (E1.type = arith and E2.ty

29、pe = bool) E.place = newtemp; E2.true = newlabel; E2.false = newlabel;E.code = E1.code | E2.code | gen(E2.true : E.place := E1.place + 1) |gen(goto nextstat + 1) | gen(E2.false : E.place := E1.place) else if 8.5 case语句的翻译switch Ebegincase V1 : S1case V2 : S2case Vn-1 : Sn-1default : Snendm计算表达式Em寻找哪

30、个V与E的值相等，都不等，则选择default1.运行对应的语句翻译方法m第(2)步是一个n-路分支q翻译为简单的条件分支语句q表驱动表项利用一循环进行检测qhash表q直接定位取值范围小，iminimax标号数组labelimax - imin + 1值j 对应语句标号labelj - imin表达式求值 直接定位标号翻译方法1计算Etgoto testL1:S1代码goto nextL2:S2代码goto nextLn-1:Sn-1代码goto nextLn:Sn代码goto nexttest:if (t = V1) goto L1if (t = V2) goto L2if (t = Vn

31、-1) goto Ln-1goto Lnnext:翻译方法2计算Etif t V1 goto L1S1代码goto testL1:if t V2 goto L2S2代码goto nextL2:Ln-2: if t Vn-1 goto Ln-1Sn-1代码goto nextLn:Sn代码next:8.6 BackPatching技术m第4节语法制导定义实现方法q两遍扫描：创建语法树，然后计算属性值q若单遍扫描：生成转移语句时目的标号未知mbackpatchingq语句四元式数组，标号数组索引qmakelist(i)：创建列表，仅包含i指向四元式数组的索引qmerge(p1, p2)：合并列表p1

32、、p2qbackpatch(p, i)：将列表p指向的所有语句中的空白地址用i填入8.6.1 语法制导定义EE1 or M E2 backpatch(E1.falselist, M.quad); E.truelist = merge(E1.truelist, E2.truelist); E.falselist = E2.falselist; EE1 and M E2 backpatch(E1.truelist, M.quad); E.truelist = E2.truelist; E.falselist = merge(E1.falselist, E2.falselist); Enot E1

33、E.truelist = E1.falselist; E.falselist = E1.truelist; E( E1 ) E.truelist = E1.truelist; E.falselist = E1.falselist; 下一语句编号语法制导定义（续）Eid1 relop id2 E.truelist = makelist(nextquad); E.falselist = makelist(nextquad + 1);emit(if id1.place relop.op id2.place goto _); emit(goto _); Etrue E.truelist = makel

34、ist(nextquad); emit(goto _); Efalse E.falselist = makelist(nextquad); emit(goto _); M M.quad = nextquad; 下一语句编号例8.6a b or c d and e f例8.6（续）ma b归约为E，产生两个四元式100:if a b goto _101:goto _mEE1 or M E2中的M，属性值为102mc d归约为E，产生两个四元式102:if c d goto _103:goto _mEE1 and M E2中的M，属性值为104me f归约为E，产生两个四元式104:if e f goto _105:goto _例8.6（续）m利用EE1 and M E2归约，backpatch(102,104)100:if a b goto _1