CSc 453Compilers and Systems Software9 : Semantic Analysis IDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergIntroductionCompiler PhasesWe are here!ASTasmSemanticAnalyserInterm.Code GenIRMachineCode GenIRASTLexertokenssourceerrorserrorsParsererrorsOptimizeSemantic AnalysisThe parser returns an abstract syntax tree (AST), astructured representation of the input program. Allinformation present in the input program (except maybe forcomments) is also present in the AST.Literals (integer/real/. . . constants) and identifiers areavailable as AST input attributes.During semantic analysis we add new attributes to the AST,and traverse the tree to evaluate these attributes and emiterror messages.At compiler construction time we have to decide whichattributes are needed, how they should be evaluated, and theorder in which they should be evaluated.Why Semantic Analysis?1Is the program statically correct? If not, report errors to user:“undeclared variable”“illegal procedure parameter”“type incompatibility”2Make preparations for later compiler phases (code generationand optimization):Compute types of variables.Compute addresses of variables.Store transfer modes of procedure parameters.Compute labels for control structures (maybe).Typical Semantic Errors....beginend;y := "x"x,y : integer);var z,x : char;var k : P;var z : R;type R = array [9..7] of char;end Y."wrong closing identifier"procedure P ("multiple declaration""type mismatch""type name expected""identifier not declared"program X;var x,y,t : integer;begin"empty range"....3+2 : t := 9 |1+4 : t := 8case x ofend"too few parameters"beginy : t := 5 |P(1,2,3);P("x",2);R[5] := "x";z["x"] := 5;"repeated case labels""boolean expression expected"if x then t := 4;end Y."too many parameters""integer type expected""variable expected""type mismatch""constant expected"program X;P(1);Static Semantic RulesStatic Semantics: ≈ type checking rules. The rules that arechecked by the compiler before execution.Dynamic Semantics: Rules that can only be checked when theprogram is run. Example: ”pointer reference to NIL”.Context Conditions: Static semantic rules.Obviously, different languages have different static semanticrules. Ada, for example, allows null ranges (e.g.array [9..7] of char), while Modula-2 doesn’t.It’s our job as compiler writers to read the language definitionand encode the rules in our semantic analyzer.Kinds of Context ConditionsType Checks We must check that every operator used in theprogram takes arguments of the correct type.Kind Checks We must check that the right kind of identifier(procedure, variable, type, label, constant, exception)is used in the right place.Flow-of-control Checks In Modula-2 an EXIT- statement mustonly occur within a LOOP-statement:LOOP IF · · · THEN EXITENDIF; ENDUniqueness Checks Sometimes a name must be defined exactlyonce. Example: variable declarations, case labels.Name Checks Sometimes a name must occur more than once, e.g.at the beginning and end of a procedure.Tree-Walk EvaluatorsStatic Semantic Rules are Confusing!Check out any C++ manual...Ada’s semantic rules are so unwieldy that compiler errormessages often contain references to the relevantsub-sub-section of the Ada Reference Manual (ARM):”Type error. See ARM section 13.2.4.”We must organize the semantic analysis phase in a systematicway.Tree-Walk Evaluators. . .The syntax analyzer produces an Abstract Syntax Tree(AST), a structured representation of the input program.Each node in the tree has a number of variables calledattributes.We write a program that traverses the tree (one or moretimes) and assigns values to the attributes.Tree-Walk Evaluators. . .AttributesSome attributes are given values by the parser. They arecalled input attributes.The attributes can store whatever we like, e.g. the types ofexpressions.Context ConditionsThe context conditions are encoded as tests on the values ofattributes (node.type is the type attribute of node,node.pos the line number in the source code):if node.type 6= "integer" thenprint "Integer expected at " node.posTree-Walk EvaluationASSIGNIF a<10 THENENDIF;c := 1;EXPR THEN ELSEIFThe AST afterparsingSemanticAnalysisParsingSource programInputAttributesLOP ROPBinaryOp:<Des ExprVal: 1Id: "c"Val: 10Id: "a"INTEGERIDENTINTEGERIDENTTree-Walk Evaluation. . .realTHEN ELSEIFLOP ROPType:BinaryOp:<boolIDENTId: "a"Type: intType:INTEGERVal: 10intType:INTEGERVal: 1intDes ExprASSIGN Type:The AST aftersemantic analysisPossible type error?!TreeTraversalOrderSemanticAnalysischarIDENTId: "c"Type:EXPRTree TraversalTree TraversalA tree-walker is a number of procedures that take a node asargument. They start by processing the root of the tree andthen work their way down, recursively.Often we will have one procedure for each major node-kind,i.e one for declarations, one for statements, one forexpressions. Notation:n.Kind is n’s node type, for example IfStat,Assignment, etc.;n.C is n’s child C, for example n.expr, n.left, etc.;n.A is n’s attribute A, for example n.type,n.value, etc.Tree Traversal. . .Each time we visit a node n we can1Evaluate some of n’s attributes.2Print a semantic error message.3Visit some of n’s children.PROCEDURE Stat(n : Node);IF n.Kind = Assign THENExpr(n.Des); Expr(n.Expr);ELSIF n.Kind = IfElse THENExpr(n.Expr); Stat(n.Stat1); Stat(n.Stat2);ENDIFEND Stat;Tree Traversal. . .PROCEDURE Expr(n : Node);IF n.Kind = BinOp THENExpr(n.LOP);Expr(n.ROP);ELSIF n.Kind=Name THEN(* Process n.Name *)ELSIF n.Kind=IntCont THEN(* Process n.Value *)ENDIFEND Expr;Constant Expression EvaluationConstant ExpressionsIn many languages there are special constructs where onlyconstant expressions may occur.For example, in Modula-2 you can writeCONST C = 15;TYPE A = ARRAY [5..C*6] OF CHAR;but notVAR C : INTEGER;TYPE A = ARRAY [5..C] OF CHAR;i.e. the upper bound of an array index must be constant(value known at compile time).Constant Expressions. . .Constant declarations can depend on other constantdeclarations:CONST C1 = 15;CONST C2 = C1 * 6;TYPE A = ARRAY [5..C2] OF CHAR;Write a tree-walk evaluator that evaluates constant integerexpressions.IntConst has an input attribute Value. We mark inputattributes with a ⇐ in the abstract syntax.Each node is given an attribute Val.Val moves up the tree, so we mark it with a ⇑ in the abstractsyntax.Constant Expressions. . .Concrete Syntax:Expr ::= Add | Mul | IntConstAdd::= Expr + ExprMul::= Expr *