Translation Scheme to Produce Three-Address Code S→id:=E p=lookup(id.name); if(p is not nil)then emit('mov'E.place,,'p) else error(undefined-variable")} E→E1+E2 E.place=newtemp(); emit(add'E1place‘,'E2.place‘,'E.place)} E→E1*E2 E.place newtempO); emit(mult'E1place‘,'E2.place‘,'E.place)} E→-E1 E.place newtempO; emit(‘uminus'Ei-place‘,'E.place)} E→(E1) E.place=E1place; E→id p=lookup(id.name); if(p is not nil)then E.place=id.place else error("undefined-variable")} CS308 Compiler Theory
Translation Scheme to Produce Three-Address Code S → id := E { p= lookup(id.name); if ( i il) h i (‘ ’ E l ‘ ’ ) if (p is not nil) t hen emit(‘mov’ E.p lace ‘,,’ p ) else error(“undefined-variable”) } E → E1 + E 2 E → E { E place = newtemp(); 1 + E 2 { E.place newtemp(); emit(‘add’ E1.place ‘,’ E 2.place ‘,’ E.place) } E → E1 * E 2 { E.place = newtemp(); emit(‘mult’ E1.place ‘,’ E 2.place ‘,’ E.place) } E → - E1 { E.place = newtemp(); emit(‘ i ’ E it(‘uminus’ E l ‘ ’E l ) } 1.p lace ‘,,’ E.p lace ) } E → ( E1 ) { E.place = E1.place; } E → id { p = lookup(id name); lookup(id.name); if (p is not nil) then E.place = id.place else error(“undefined-variable”) } CS308 Compiler Theory 11
Translation scheme with locations S->id:={E.inloc S.inloc E {p=lookup(id.name); if (p is not nil)then emit(E.outloc mov'E.place,'p);S.outloc=E.outloc+1 else error("undefined-variable");S.outloc=E.outloc } E>{E1.inloc E.inloc E+E2.inloc E1.outloc E2 E.place newtemp();emit(E2.outloc add'Eplace,'E.place,'E.place);E.outloc=E2.outloc+1 E>{E1.inloc E.inloc E+E2.inloc=E1.outloc E2 E.place newtemp();emit(E2.outloc 'mult'E.place,'E2.place,'E.place);E.outloc=E2.outloc+1} E>-E1.inloc E.inloc E {E.place newtemp();emit(E.outloc 'uminus'Eplace'E.place);E.outloc=E.outloc+1} E>(E){E.place=E1place;E.outloc=E1.outloc+1} E->id E.outloc E.inloc;p=lookup(id.name); if(p is not nil)then E.place id.place else error("undefined-variable")} CS308 Compiler Theory 12
Translation Scheme with Locations S → id := { E.inloc = S.inloc } E { p p( ); p = lookup(id.name); if (p is not nil) then { emit(E.outloc ‘mov’ E.place ‘,,’ p); S.outloc=E.outloc+1 } else { error(“undefined-variable”); S.outloc=E.outloc } } E → { E1.inloc = E.inloc } E1 + { E 2.inloc = E1.outloc } E 2 { E.place = newtemp(); emit(E 2.outloc ‘add’ E1.place ‘,’ E 2.place ‘,’ E.place); E.outloc=E 2.outloc+1 } E → { E1.inloc = E.inloc } E1 + { E 2.inloc = E1.outloc } E 2 { E.place = newtemp(); emit(E 2.outloc ‘mult’ E1.place ‘,’ E 2.place ‘,’ E.place); E.outloc=E 2.outloc+1 } E → - { E1.i l Ei l }E inloc = E.inloc } E1 { E.place = newtemp(); emit(E1.outloc ‘uminus’ E1.place ‘,,’ E.place); E.outloc=E1.outloc+1 } E → ( E ) { E place = E place; E outloc=E outloc+1 } 1 ) { E.place = E1.place; E.outloc=E1.outloc+1 } E → id { E.outloc = E.inloc; p= lookup(id.name); if (p is not nil) then E. place = id.place CS308 Compiler Theory 12 (p ) p else error(“undefined-variable”) }
Boolean Expressions E>{E1.inloc E.inloc E and E2.inloc E1outloc E2 E.place newtemp();emit(E2.outloc 'and'Eplace,'E2.place,'E.place);E.outloc=E2.outloc+1} E>E.inloc E.inloc E or E2.inloc E.outloc E2 {E.place newtemp();emit(E2.outloc 'and'Eplace,'E2.place,'E.place);E.outloc=E2.outloc+1} E>not E1.inloc E.inloc E {E.place newtemp();emit(E.outloc not'E.place,,'E.place);E.outloc=Eoutloc+1} E>{E1.inloc E.inloc E relop {E2.inloc E1.outloc E2 {E.place=newtemp(); emit(E2.outloc relop.code Eplace,'E2.place,'E.place);E.outloc=E2.outloc+1} CS308 Compiler Theory
Boolean Expressions E → { E1.inloc = E.inloc } E1 and { E 2.inloc = E1.outloc } E 2 { E place { E.place = newtemp(); emit(E newtemp(); emit(E 2 outloc ‘and’ E1 place ‘ ’ E 2 place ‘ ’ E place); E outloc = E 2 outloc+1 } 2.outloc and E1.place , E 2.place , E.place); E.outloc E 2.outloc+1 } E → { E1.inloc = E.inloc } E1 or { E 2.inloc = E1.outloc } E 2 { E place = newtemp(); emit(E { E.place = newtemp(); emit(E outloc ‘and’ E place ‘ ’ E place ‘ ’ E place); E outloc=E outloc+1 } 2.outloc and E1.place , E 2.place , E.place); E.outloc=E 2.outloc+1 } E → not { E1.inloc = E.inloc } E1 { E place = newtemp(); emit(E { E.place = newtemp(); emit(E outloc ‘not’ E place ‘ ’ E place); E outloc=E outloc+1 } 1.outloc not E1.place ,, E.place); E.outloc=E1.outloc+1 } E → { E1.inloc = E.inloc } E1 relop { E 2.inloc = E1.outloc } E 2 { E l t () { E.place = newtemp(); emit(E 2.outloc relop.code E1.place ‘,’ E 2.place ‘,’ E.place); E.outloc=E 2.outloc+1 } CS308 Compiler Theory 13
Translation Scheme(cont.) S->while E.inloc S.inloc E do emit(E.outloc jmpf E.place,,'NOTKNOWN'); S1.inloc=E.outloc+1;}S emit(S.outloc 'jmp,,'S.inloc); S.outloc=S.outloc+1; backpatch(E.outloc,S.outloc); S->if{E.inloc=S.inloc E then emit(E.outloc 'jmpf E.place,,'NOTKNOWN'); S1.inloc=E.outloc+1;}S else emit(S1.outloc jmp',,'NOTKNOWN'); S2.inloc=S.outloc+1; backpatch(E.outloc,S2.inloc);}S2 {S.outloc=S2.outloc; backpatch(S.outloc,S.outloc);} CS308 Compiler Theory 14
Translation Scheme(cont.) S → while { E.inloc = S.inloc } E do { emit(E outloc { emit(E.outloc ‘jmpf’ E place E.place ,, ‘ ’‘NOTKNOWN NOTKNOWN’); S1.inloc=E.outloc+1; } S1 { emit(S1.outloc ‘jmp’ ‘,,’ S.inloc); S outloc=S S.outloc=S outloc+1; 1.outloc+1; backpatch(E.outloc,S.outloc); } S → if { E inloc = S inloc } E then if { E.inloc = S.inloc } E then { emit(E.outloc ‘jmpf’ E.place ‘,,’ ‘NOTKNOWN’); S1.inloc=E.outloc+1; } S1 else { it(S em tl ‘j ’ ‘ ’ ‘NOTKNOWN’) 1.outloc ‘jmp’ ‘,,’ ‘NOTKNOWN’); S 2.inloc=S1.outloc+1; backpatch(E.outloc,S 2.inloc); } S 2 {S l S .outloc= S l 2.out oc; backpatch(S1.outloc,S.outloc); } CS308 Compiler Theory 14
Three Address Codes -Example X:=1, 01:mov 1,,8 y=x+10; 02:add ,10,t1 while (x<y){ → 03:mov t1,,Y X:=x+1; 04:1t x,y,t2 if (x%2==1)then y:=y+1; 05:jmpf t2,,17 else y:=y-2; 06:add ,1,t3 07:mov t3,,x 08:mod ,2,t4 09:eq t4,1,t5 10:jmpf t5,,14 11:add y,1,t6 12:mov t6,y 13:jmp ,,16 14:sub y,2,t7 15:mov t7,y 16:jmp ,4 17: CS308 Compiler Theory 15
Three Address Codes - Example x:=1; 01: mov 1,,x y: x+10; = 02: add x,10,t1 02: add x,10,t1 while (x<y) { Î 03: mov t1,,y x:=x+1; 04: lt x,y,t2 if (x%2==1) then y:=y+1; if (x%2==1) then y:=y+1; 05: jmpf t2 17 05: jmpf t2,,17 else y:=y-2; 06: add x,1,t3 } 07: mov t3,,x 08: mod x 2 t4 08: mod x,2,t4 09: eq t4,1,t5 10: jmpf t5,,14 11: add y 1 t6 11: add y,1,t6 12: mov t6,,y 13: jmp ,,16 14 b 2 t7 14: su b y, 2,t7 15: mov t7,,y 16: jmp ,,4 CS308 Compiler Theory 15 17: