Semantic AnalysisCompilation in a Nutshell 1Compilation in a Nutshell 2Questions to Answer:Context-Sensitive AnalysisAttribute GrammarsAttribute TypesAttribute FlowSlide 9Slide 10Slide 11Slide 12Slide 13Action RoutinesSlide 15Abstract Syntax TreeSymbol TableSample programSlide 19Symbol Table ImplementationOne optionLeBlanc-Cook symbol tables1Semantic AnalysisAaron BloomfieldCS 415Fall 20052Compilation in a Nutshell 1Source code(character stream)Lexical analysisParsingToken streamAbstract syntax tree(AST)Semantic Analysisif (b == 0) a = b;if ( b ) a = b ;0==if==b 0=a bif==int b int 0=int alvalueint bbooleanDecorated ASTint;;3Compilation in a Nutshell 2Intermediate Code GenerationOptimizationCode generationif==int b int 0=int alvalueint bbooleanint;CJUMP ==MEMfp 8+CONST MOVE0 MEM MEMfp 4fp 8NOP++CJUMP ==CONSTMOVE0 DXCXNOPCXCMP CX, 0CMOVZ DX,CX4Questions to Answer:•Is x a scalar, an array, or a function?•Is x declared before it is used?•Which declaration of x does this reference?•Does the dimension of a reference match the declaration?•Is an array reference in bounds?•Type errors (that can be caught statically)5Context-Sensitive Analysis•Two solutions:Attribute grammars – augment CFG with rules, calculate attributes for grammar symbolsad hoc techniques – augment grammar with arbitrary code, execute at corresponding reduction, store information in attributes, symbol tables values6Attribute Grammars•Generalization of context-free grammars•Each grammar symbol has an associated set of attributes•Augment grammar with rules that define values–Not allowed to refer to any variables or attributes outside the current production7Attribute Types•Values are computed from constants and other types:– Synthesized attribute – value computed from children–Inherited attribute – value computed from siblings, parent, and own attributes8Attribute FlowS-attributed grammar–Uses only synthesized types–Bottom-up attribute flowL-attributed grammar–Attributes can be evaluated in a single left-to-right pass over the input–Each synthesized attribute of LHS depends only on that symbol’s own inherited attributes or on attributes (synthesized or inherited) of the production’s RHS symbols91011121314Action Routines•We need a translation scheme - an algorithm that invokes the attributes in a order that respects attribute flow.•Action Routines = an Ad hoc translation scheme that is interleaved with parsing•An action routine = Semantic function that programmer instructs the compiler to execute at a particular point in the parse.•What most production compilers use.1516Abstract Syntax Tree•An abstract syntax tree is the procedure’s parse tree with the nodes for most non-terminal symbols removedE.g., “a + 3 * b”17Symbol Table•A “Dictionary” that maps names to info the compiler knows about that name.•What names?–Variable and procedure names–Literal constants and strings•What info?Textual nameData typeDeclaring procedureLexical level of declarationIf array, number and size of dimensionsIf procedure, number and type of parameters18Sample programProgram gcd (input, output);Var I,j: integer;BeginRead(I,j);While I <> j toIf I > j then I := I – jElse j := j – I;Writeln (i)End.1920Symbol Table Implementation•Usually implemented as hash tables•Return closest lexical declaration to handle nested lexical scoping•How to handle multiple scopes?21One option•Use one symbol table per scope•Chain tables to enclosing scope•Insert names in tables for current scope•Start name lookup in current table, checking enclosing scopes in order if needed22LeBlanc-Cook symbol tables-Give each scope a number,-All names in a hash table, keyed by name -Also have a scope stack – to show current referencing environment.-As analyzer looks at programs, it pushes and pops this stack as it enters and leaves scopes.-To look up – scan down the appropriate hash chain, for each matching entry, scan down the scope stack to see if that is visible. We look no deeper than the top-most