CSc 453Compilers and Systems Software12 : Semantic Analysis IVDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergOptimizing Tree-WalkEvaluatorsOptimizing Tree-WalkersStoring every attribute in the AST may take up a lot of space.Sometimes we can make some optimizations:1Inherited attributes can be passed as input arguments to therecursive procedures.2Synthesized arguments can be returned as function results (oras reference parameters).This won’t work for output attributes, attributes that will beneeded by later compilation phases.PROCEDURE Program(n: Node);Std := {INT,REAL,CHAR,TRUNC,FLOAT};Decl(n.DeclSeq, ⇓{}, ⇑IdsOut, ⇓Std);xEnv := cons(IdsOut,StdEnv);Stat(n.StatSeq, ⇓ xEnv);PROCEDURE Decl(n:Node; IdsIn:SyTabT;VAR IdsOut:SyTabT; Env:EnvT);· · ·PROCEDURE Assign(n: Node; Env:EnvT);Des(⇓Env, ⇑DesType);Expr⇓(Env, ⇑ExprType);IF DesType 6= ExprType THEN · · ·Dynamic Tree-Walk EvaluatorsDynamic Tree-WalkersThe major problem with building a tree-walk evaluator is tofind an order (a visit sequence) in which to traverse the ASTand evaluate the attributes.So far, we have built Static Evaluators. With this type ofevaluator the visit sequence is determined by the compilerdesigner at compiler construction time.If we’re not concerned with efficiency, then we can build aDynamic Evaluator, one for which the visit sequence isdetermined at compile time (i.e. when we’re performingsemantic analysis).Dynamic Tree-Walkers. . .1Build the abstract syntax tree during parsing.2Build the dependency graph for the attributes of the tree.The nodes of the graph are the attributes of the tree.There’s an edge from node a to node b if b depends on a, i.e.if a has to be computed before b.3Perform a topological sort of the dependency graph.4If a cycle is detected abort the compile: “Cyclic evaluator,compilation aborted”.5Otherwise, evaluate the tree attributes in the order computed.Dynamic Tree-Walkers. . .Topological SortS.aS.bX.cX.dY.eY.fX.hZ.gConstructDependency GraphY ZXx y zSacbdef hgX.d S.bY.eY.fZ.gS.aX.hX.cHLocalsLevel=0Name="P"StatSeqNextVarDecl Name="Z"Level=0 NextName="Q"StatSeqNextProcDeclLocalsLevel=1VarDecl Name="Y"Level=1 NextVarDecl Name="X"Level=2 NextNoDeclLevel=2Program Name="M"DeclSeqStatSeqNoDeclLevel=0NoDeclLevel=1BCDEFG HAPerformsorttoplogicalBuilddependencygraphC G H FDA BABCDEFGProcDeclHBCDEFG HAA’s Level−attributeF’s Level−attributeBuilddependencygraphC G H FDA BPerformsorttoplogicalABCDEFGForward ReferencesForward ReferencesSome languages (Ada, Modula-3) allow declarations to comein an arbitrary order.Modula-2 allows forward references for procedures andvariables, but types and constants must be declared beforeuse.PROGRAM M;PROCEDURE P ();VAR X : INTEGER;BEGINX := Y + 1; ⇐ Forward ref to Y!Q(); ⇐ Forward ref to Q!END P;VAR Y : INTEGER;PROCEDURE Q (); BEGIN END Q;BEGIN END M;Forward References. . .We have to process declarations two times. The first time webuild (partial) symbol tables, the second time we buildenvironments and process statements.mIds1:SyTabT is built during pass 1, mIds2:SyTabT duringpass 2.mIds1:SyTabT will basically only store the names and kindsof identifiers, to be used during name lookup.mIds2:SyTabT will store complete symbols.Statements are processed in a third pass.PROCEDURE Program (n: Node);Program Pass1();Program Pass2();Program Pass3();END;Forward References — First passPROCEDURE Program Pass1 (n: Node);StdEnv := {INT,REAL,CHAR,TRUNC,FLOAT};n.DeclSeq.IdsIn1:= {};DeclPass1(n.DeclSeq);END;PROCEDURE DeclPass1 (n: Node);IF n.Kind=ProcDecl THENProcDeclPass1(n);ELSIF n.Kind=VarDecl THENVarDeclPass1(n);ELSIF · · · ENDIFEND;PROCEDURE VarDecl Pass1 (n: Node);-- Check for multiple declaration of the variable.Sy := (Name=n.Id,Kind=VAR); ⇐No Type!n.Next.IdsIn1 := n.IdsIn1 ∪ {Sy};Decl Pass1(n.Next);n.IdsOut1:=n.Next.IdsOut1;END;PROCEDURE ProcDecl Pass1 (n: Node);n.Formals.IdsIn1 := {};DeclPass1(n.Formals);n.Locals.IdsIn1 := n.Formals.IdsOut1;Decl Pass1(n.Locals);Sy:=(Name=n.Id,Kind=PROC);⇐No Formals!n.Next.IdsIn1 := n.IdsIn1 ∪ {Sy};Decl Pass1(n.Next);n.IdsOut1:=n.Next.IdsOut1;END;Forward References — Second PassPROCEDURE Program Pass2 (n: Node);StdEnv := {INT,REAL,CHAR,TRUNC,FLOAT};n.DeclSeq.Env := cons(n.DeclSeq.IdsOut1,StdEnv);n.DeclSeq.IdsIn2:= {};Decl Pass2(n.DeclSeq);END;PROCEDURE VarDeclPass2 (n: Node);-- Check if the type is declared.T := Lookup(n.TypeName,n.Env);Sy := (Name=n.Id,Kind=VAR, Type=T); ⇐ Type!n.Next.IdsIn2 := n.IdsIn2 ∪ {Sy};DeclPass1(n.Next);n.IdsOut2:=n.Next.IdsOut2;END;PROCEDURE ProcDecl Pass2 (n: Node);-- Use symbols from pass 1 as part of-- the env for locals and formals.n.Locals.Env := n.Formals.Env :=cons(n.Locals.IdsOut1, n.Env);-- Build new sy tab from locals & formals.n.Formals.IdsIn2:={};Decl Pass2(n.Formals);n.Locals.IdsIn2 := n.Formals.IdsOut2;DeclPass2(n.Locals);-- Build new sytab entry for the procedure. Include formals.Sy := (Name=n.Id,Kind=PROC, Formals=n.Formals.IdsOut2);n.Next.IdsIn2 := n.IdsIn2 ∪ {Sy};Decl Pass2(n.Next);n.IdsOut2:=n.Next.IdsOut2;Forward References — Third passPROCEDURE Program Pass3 (n: Node);n.DeclSeq.Env := n.StatSeq.Env :=cons(n.DeclSeq.IdsOut2, StdEnv);DeclPass3(n.DeclSeq);Stat(n.StatSeq);END;PROCEDURE DeclPass3 (n: Node);IF n.Kind=ProcDecl THENProcDeclPass3(n);ENDIFEND;PROCEDURE ProcDecl Pass3 (n: Node);n.Locals.Env := n.StatSeq.Env :=cons(n.Locals.IdsOut2, n.Env);DeclPass3(n.Locals);Stat(n.StatSeq);n.Next.Env:=n.Env; DeclPass3(n.Next);END;Forward References — Example 1LocalsFormalsProcDeclId=Q NextStatSeqLocalsNoDeclPQ YX:=Y+1Q()NoDeclXIdsOut=VarDeclNextId=XStatSeqDeclSeqProgram Id=MFormalsProcDeclId=Q NextStatSeqLocalsNoDeclX:=Y+1Q()PQ YXIdsOut=FormalsProcDeclId=P NextStatSeqLocalsIdsOut=VarDeclNextId=XNoDeclStatSeqDeclSeqProgram Id=MIdsOut=VarDecl Id=YNextIdsOut=VarDecl Id=YNextPass 3Pass 1/2IdsOut=FormalsProcDeclId=P NextStatSeqForward References — Example 2Why can’t we process the statements during the first pass?Types complicate things. Before we can process the call to Pat 2, we need to have processed P’s formals at 1 . We can’tprocess P’s formals until we’ve seen U at 4.We might be able to do the first pass as the AST is beingbuilt, or do pass 2 as we return from the pass 1 recursion.PROCEDURE P (S : U); ⇐ 1BEGIN · · · END P;PROCEDURE Q ();VAR K : T;BEGIN P(K); ⇐ 2 END Q;TYPE T = U; ⇐ 3TYPE U = INTEGER; ⇐ 4Pass 1PQ T UStatSeqDeclSeqProgram