CSc 453 — Compilers and Systems Software9 : Semantic Analysis IChristian CollbergDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergSeptember 27, 20091Introduction2 Compiler PhasesWe are here!ASTasmSemanticAnalyserInterm.Code GenIRMachineCode GenIRASTLexertokenssourceerrorserrorsParsererrorsOptimize3 Semantic Analysis• The parser returns an abstract syntax tree (AST), a structured representation of the input program.All information present in the input program (except maybe for comments) is also present in the AST.• Literals (integer/real/. . . constants) and identifiers are available as AST input attributes.• During semantic analysis we add new attributes to the AST, and traverse the tree to evaluate theseattributes and emit error messages.• At compiler construction time we have to decide which attributes are needed, how they should beevaluated, and the order in which they should be evaluated.14 Why Semantic Analysis?1. Is the program statically correct? If not, report errors to user:• “undeclared variable”• “illegal procedure parameter”• “type incompatibility”2. Make preparations for later compiler phases (code generation and optimization):• Compute types of variables.• Compute addresses of variables.• Store transfer modes of procedure parameters.• Compute labels for control structures (maybe).5 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"6....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);7 Static Semantic RulesStatic Semantics: ≈ type checking rules. The rules that are checked by the compiler before execution.2Dynamic Semantics: Rules that can only be checked when the program is run. Example: ”pointer referenceto NIL”.Context Conditions: Static semantic rules.• Obviously, different languages have different static semantic rules. 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 definition and encode the rules in our semanticanalyzer.8 Kinds of Context ConditionsType Checks We must check that every operator used in the program 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 must only occur within a LOOP-statement:LOOP IF · · · THENEXIT ENDIF; ENDUniqueness Checks Sometimes a name must be defined exactly once. 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.9 Tree-Walk EvaluatorsStatic Semantic Rules are Confusing!• Check out any C++ manual...• Ada’s semantic rules are so unwieldy that compiler error messages often contain references to therelevant sub-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 systematic way.10 Tree-Walk Evaluators. . .• The syntax analyzer produces an Abstract Syntax Tree (AST), a structured representation of theinput program.• Each node in the tree has a number of variables called attributes.• We write a program that traverses the tree (one or more times) and assigns values to the attributes.311 Tree-Walk Evaluators. . .Attributes• Some attributes are given values by the parser. They are called input attributes.• The attributes can store whatever we like, e.g. the types of expressions.Context Conditions• The context conditions are encoded as tests on the values of attributes (node.type is the type attributeof node, node.pos the line number in the source code):if node.type 6= "integer" thenprint "Integer expected at " node.pos12 Tree-Walk EvaluationASSIGNIF a<10 THENENDIF;c := 1;EXPR THEN ELSEIFThe AST afterparsingSemanticAnalysisParsingSource programInputAttributesLOP ROPBinaryOp:<Des ExprVal: 1Id: "c"Val: 10Id: "a"INTEGERIDENTINTEGERIDENT13 Tree-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:EXPR14Tree Traversal15 Tree Traversal• A tree-walker is a number of procedures that take a node as argument. They start by processing theroot of the tree and then work their way down, recursively.4• Often we will have one procedure for each major node-kind, i.e one for declarations, one for statements,one for expressions. 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.16 Tree Traversal. . .• Each time we visit a node n we can1. Evaluate some of n’s attributes.2. Print a semantic error message.3. Visit 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;17 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;18Constant Expression Evaluation19 Constant Expressions• In many languages there are special constructs where only constant expressions may occur.• For example, in Modula-2 you can writeCONST C = 15;TYPE A = ARRAY [5..C*6] OF CHAR;5but 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).20 Constant Expressions. . .• Constant declarations can depend on other constant declarations:CONST C1 = 15;CONST C2 = C1 * 6;TYPE A = ARRAY [5..C2] OF CHAR;• Write a tree-walk evaluator that evaluates constant integer expressions.•IntConst has an input attribute Value. We mark input attributes