CSc 453Compilers and Systems Software10 : Semantic Analysis IIDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergIntroductionOverviewSeveral independent tasks have to be performed duringsemantic analysis:Declaration AnalysisGo through and check the legality of the declarations (types,variables, procedures, etc) in the program. Check for:1multiple declarations: VAR x,y,x : int.2undeclared types : VAR x : intger.3illegal symbol kinds: VAR X : integer; VAR Y : X.Construct symbol tables and environments to be usedduring name and expression analysis.Overview. . .Name AnalysisMatch up each use of an identifier with the correctdeclaration. Report any undeclared identifiers.Expression AnalysisAssign types to every sub-expression.Report type mismatches: X:="Hi" * "there".Prepare for Code GenerationInsert explicit type conversions: X:=5+6.7 ⇒X:=float(5)+6.7.Compute labels for conditional- and loop-statements.Name AnalysisName AnalysisAlgol-like languages allow the same name to be declared indifferent scopes. During name analysis the use of a name ismatched up with the corresponding declaration.VAR I, K : INTEGER;PROCEDURE P (K : INTEGER);PROCEDURE Q (L : INTEGER);BEGIN I := L + K; (* Iglobal:= LQ+ KP*) END Q;VAR J : INTEGER;BEGIN I := J + K; (* Iglobal:= JP+ KP*) END P;Declaration AnalysisSymbol TablesAll compilers use a symbol table. In it we record allinformation regarding every declared item (variable,procedure, constant, etc).The symbol table is built during declaration analysis.The symbol table is used during name analysis and typechecking to look up identifiers.Some compilers build one (huge) symbol table for the entireinput program. Others build one separate symbol table foreach scope.The type of information which is stored in a symbol tablenode depends on the declaration:Symbol Tables. . .All Symbols Name, Position, Level, Enclosing Block, . . .Variables Type, Size, . . .Constants Type, Size, Value, . . .Types Size, . . .Records FieldsArrays Index-Type, Index-Range,Element-TypeProcedures Formal Parameters, Size of Local Data, . . .TYPE T = RECORD a, b : CHAR END;VAR X : T;PROCEDURE Q (a: T); BEGIN ... END Q;Example — Building theSymbol TableBuilding the Symbol TableThis time we want to build a symbol table from a sequence ofdeclarations. At the same time we want to check for multiplydeclared identifiers.In this example, the symbol table is simply a set of identifiers.Normally, we’d also want the symbol table to include otherkinds of information: type, size, and offset for variables,formal parameters for procedures, etc.Operations on SyTabs: Union (∪) and member (∈).Threaded AttributesWe use a threaded attribute Ids of type SyTab={String}(set of strings).A threaded attribute Attr is really a combination of twoattributes, a synthesized attribute AttrOut and an inheritedattribute AttrIn.Threaded attributes are used to collect information from asubtree. The evaluator uses the inherited attribute to collectinformation on the way down the tree, and the synthesizedattribute to move that information back up the tree.In our example, IdsIn is inherited and holds the current setof identifiers. IdsOut is synthesized and returns the completesymbol table.Building the Symbol Table. . .At any node n, n.IdsOut-n.IdsIn is the set of variablesdeclared in the subtree rooted at n.Abstract Syntax:Program ::= ⇐Id:String DeclSeq:Decl StatSeq:StatDecl::= VarDecl | ProcDecl | NoDeclVarDecl::= ⇐Id:String ⇐TypeName:String Next:DeclmIds:SyTabProcDecl ::= ⇐Id:String Locals:Decl StatSeq:Stat Next:DeclmIds:SyTabNoDecl ::= mIds:SyTabProgram ::= ⇐Id:String DeclSeq:Decl StatSeq:Stat{ DeclSeq.IdsIn:={} }VarDecl ::= ⇐Id:String ⇐TypeName:StringNext:Decl mIds:SyTab{CHECK Id ∈ IdsIn ⇒ ERROR(”Multiple Declaration”)Next.IdsIn := IdsIn ∪ IdIdsOut := Next.IdsOut}Decl ::= mIds:SyTab{ IdsOut := IdsIn }PROCEDURE Program (n: Node);n.DeclSeq.IdsIn:={}; Decl(n.DeclSeq);PROCEDURE Decl (n: Node);IF n.Kind ∈ {VarDecl,ProcDecl} THENIF n.Id ∈ n.IdsIn THENPRINT n.Pos ":Multiple "declaration: " n.Id;ENDIF;n.Next.IdsIn := n.IdsIn ∪ {n.Id};Decl(n.Next);n.IdsOut := n.Next.IdsOutELSIF n.Kind = NoDecl THENn.IdsOut := n.IdsInENDIFNoDeclId="M"ProgramStatSeqDeclSeqId="X"VarDeclTypeName="INT"NextIdsIn={X,P,Y}IdsOut={X,P,Y}Id="X"VarDeclTypeName="INT"NextId="P"ProcDeclLocalsStatSeqArgsNextId="Y"VarDeclTypeName="BOOL"NextIdsIn={}IdsOut={X,P,Y}IdsOut={X,P,Y}IdsOut={X,P,Y}IdsIn={X}IdsIn={X,P} IdsIn={X,P,Y}IdsOut={X,P,Y}Putting it all togetherPutting it all together. . .Obviously, We don’t write one tree-walk evaluator for eachattribute. Rather, we walk over the tree once (or maybe twiceor three times, depending on the language) and evaluate asmany attributes as possible.In this example we’ll just use several attribute evaluation rulesin order to1Check for multiple declarations and build a symbol tablecontaining all the identifiers.2Assign an offset to each variable and compute the total size ofthe variables declared.3Assign a unique number to each declared identifier and countthe number of identifiers.Putting it all together. . .Abstract Syntax:Program ::= ⇐Id:String DeclSeq:Decl StatSeq:StatDecl::= VarDecl | ProcDecl | NoDeclVarDecl::= ⇐Id:String ⇐TypeName:String Next:DeclmIds:SyTab mCount:INTEGER mSize:INTEGERProcDecl ::= ⇐Id:String Args:Decl Locals:Decl StatSeq:StatNext:Decl mIds:SyTab mCount:INTEGER mSize:INTEGERNoDecl ::= mIds:SyTab mCount:INTEGER mSize:INTEGERPROCEDURE Program (n: Node);n.DeclSeq.IdsIn := {};n.DeclSeq.CountIn:=0;n.DeclSeq.SizeIn:=0;Decl(n.DeclSeq);PROCEDURE Decl (n: Node);IF n.Kind = VarDecl THEN VarDecl(n);ELSIF n.Kind = ProcDecl THEN ProcDecl(n);ELSIF n.Kind = NoDecl THENn.CountOut := n.CountIn;n.SizeOut := n.SizeIn;n.IdsOut := n.IdsInENDIFPROCEDURE VarDecl (n: Node);n.Next.SizeIn := n.SizeIn + size(n.TypeName);n.Next.CountIn := n.CountIn + 1;IF n.Id ∈ n.IdsIn THENPRINT n.Pos ":Multiple declaration: " n.Id;ENDIF;n.Next.IdsIn := n.IdsIn ∪ {n.Id};Decl(n.Next);n.CountOut := n.Next.CountOut;n.SizeOut := n.Next.SizeOut;n.IdsOut := n.Next.IdsOutPROCEDURE ProcDecl (n: Node);n.Next.SizeIn := n.SizeIn;(* Rest is same as for VarDecl *)Putting it all together. .