CSc 453 — Compilers and Systems Software14 : Intermediate Code IIChristian CollbergDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergOctober 18, 20091Intermediate Code Generation2 Intermediate Code GenerationDecorated ASTIntermediateCode GeneratorCode (expressiontrees, tuples,DAGs...)IntermediateMachine CodeGeneratorset L, %o0ld [%o0], %l1Lexing,Parsing,SemanticAnalysisMachine Code• After semantic analysis we traverse the AST and emit the correct intermediate code.13 Generating Expression TreesAssignType=Des ExprId="R"NameType=RealRopLopOp="+"Binary Type=RealDecoratedASTNameId="C"Type=RealNameId="J"Type=IntIntConstType=IntValue=13RopLopOp="*"Binary Type=IntTree−WalkTransformerStoreVarLevel=0Addr=0x10LoadIntermediateCode ExpressionTreeIntegervalue = 13MultLoadVarLevel=1Addr=0x14FloatVarLevel=0Addr=0xAPlus• An expression tree is generated from an AST. The float can easily be inserted since all types areknown in the AST.4 Generating Quadruples• To generate quadruples from an AST we make an extra traversal of the tree after semantic analysis.• Each AST node in an expression sub-tree is given an attribute ⇑Place:SymbolT which represents thename of the identifier or temporary in which the value of the subtree will be computed.5 Generating Quadruples. . .PROCEDURE Program (n: Node);Decl(n.DeclSeq);Stat(n.StatSeq);END;PROCEDURE Decl (n: Node);IF n.Kind = ProcDecl THENDecl(n.Locals);Decl(n.Next);Stat(n.StatSeq);ENDIFEND;6 Generating Quadruples. . .• NewTemp generates a new temporary var.PROCEDURE Stat (n: Node);IF n.Kind = Assign THENExpr(n.Des);Expr(n.Expr);Emit(n.Des.Place ’:=’ n.Expr.Place);Stat(n.Next);ENDIFEND;27 Generating Quadruples. . .PROCEDURE Expr (n: Node);IF n.Kind = Add THENExpr(n.LOP);Expr(n.ROP);n.Place := NewTemp();Emit(n.Place ’:=’ n.LOP.Place ’+’ n.ROP.Place);ELSIF n.Kind = VarRef THENn.Place := n.Symbol;ENDIFEND;8 Generating Quadruples. . .Symbol Table EntryDes ExprAssignId="R"NamePlace=NameId="C"Place=NameId="J"Place=IntConstValue=13Place=RopLopOp="+"BinaryPlace=RopLopOp="*"BinaryPlace=R := T2T2 := C + T1T1 := J * 13(R,VAR,INT)(T1,TEMP,INT)(T2,TEMP,INT)(C,VAR,INT)(J,VAR,INT) (13,CONST,INT)Quadruples9Attribute Grammar Notation10 Attribute Grammar• The tree-walker is better described using an attribute grammar notation.Assign ::= Des:Expr Expr:Expr{ Emit(n.Des.Place ’:=’ n.Expr.Place); }Add ::= LOP:Expr ROP:Expr{ n.Place := NewTemp();Emit(n.Place ’:=’ n.LOP.Place ’+’ n.ROP.Place);}Name ::= Ident{ n.Place := n.Symbol; }311Summary12 Readings and References• Read Louden:Generating Intermediate Code
View Full Document