Lecture 11: Semantic Analysis (Section 4.1- 4.4)Semantic Analysis From Code Form To Program MeaningPhases of CompilationSpecification of Programming LanguagesThe Semantic AnalyzerAttribute GrammarsAttribute Grammars ExampleAttribute FlowAttribute Flow ExampleSlide 10Attribute Flow Synthetic and Inherited AttributesAttribute Flow Inherited AttributesLL GrammarNon-S-Attributed Grammars ExampleSyntax TreeBottom-up Attribute Grammar to Construct a Syntax TreeConstruction of the Syntax TreeAction RoutinesAction Rules for the Previous LL(1) attribute grammarAction RulesStatic and Dynamic SemanticsDynamic SemanticsSemantic Specification11Lecture 11: Lecture 11: Semantic AnalysisSemantic Analysis(Section 4.1- 4.4)(Section 4.1- 4.4)CSCI 431 Programming LanguagesCSCI 431 Programming LanguagesFall 2002Fall 2002A modification of slides developed by Felix A modification of slides developed by Felix Hernandez-Campos at UNC Chapel HillHernandez-Campos at UNC Chapel Hill22Semantic AnalysisSemantic AnalysisFrom Code Form To Program MeaningFrom Code Form To Program MeaningCompiler or InterpreterCompiler or InterpreterTranslation Translation ExecutionExecutionSource CodeSource CodeTarget CodeTarget CodeInterpre-Interpre-tationtation33Phases of CompilationPhases of Compilation44Specification of Programming LanguagesSpecification of Programming Languages•PLs require precise definitions (i.e. no PLs require precise definitions (i.e. no ambiguityambiguity))–LanguageLanguage form form (Syntax)(Syntax)–LanguageLanguage meaning meaning (Semantics) (Semantics)•Consequently, PLs are specified using formal Consequently, PLs are specified using formal notation:notation:–Formal syntaxFormal syntax»TokensTokens»GrammarGrammar–Formal semanticsFormal semantics»Attribute Grammars (static semantics)Attribute Grammars (static semantics)»Dynamic SemanticsDynamic Semantics55The Semantic AnalyzerThe Semantic Analyzer•The principal job of the semantic analyzer is to The principal job of the semantic analyzer is to enforce static semantic rules. enforce static semantic rules. •In general, anything that requires the requires the In general, anything that requires the requires the compiler to compare things that are separate by a compiler to compare things that are separate by a long distance or to count things ends up being a long distance or to count things ends up being a matter of matter of semantics.semantics.•The semantic analyzer also commonly constructs a The semantic analyzer also commonly constructs a syntax tree (usually first), and much of the syntax tree (usually first), and much of the information it gathers is needed by the code information it gathers is needed by the code generator.generator.66Attribute GrammarsAttribute Grammars•Context-Free Grammars (CFGs) are used to specify Context-Free Grammars (CFGs) are used to specify the syntax of programming languagesthe syntax of programming languages–E.g.E.g. arithmetic expressions arithmetic expressions•How do we tie these rules to How do we tie these rules to mathematical concepts?mathematical concepts?•Attribute grammarsAttribute grammars are annotated are annotated CFGs in which CFGs in which annotationsannotations are are used to establish meaning used to establish meaning relationships among symbolsrelationships among symbols–Annotations are also known as Annotations are also known as decorationsdecorations77Attribute GrammarsAttribute GrammarsExampleExample•Each grammar symbols Each grammar symbols has a set of has a set of attributesattributes–E.g.E.g. the value of E the value of E11 is the is the attribute attribute EE11.val.val•Each grammar rule has Each grammar rule has a set of rules over the a set of rules over the symbol attributessymbol attributes–Copy rulesCopy rules–Semantic Function rulesSemantic Function rules»E.g. E.g. sumsum, , quotientquotient88Attribute FlowAttribute Flow•Context-free grammars are not tied to an specific Context-free grammars are not tied to an specific parsing orderparsing order–E.g.E.g. Recursive descent, LR parsing Recursive descent, LR parsing•Attribute grammars are not tied to an specific Attribute grammars are not tied to an specific evaluation orderevaluation order–This evaluation is known as the This evaluation is known as the annotationannotation or or decorationdecoration of the parse treeof the parse tree99Attribute Flow Attribute Flow ExampleExample•The figure shows the result The figure shows the result of annotating the parse of annotating the parse tree for tree for (1+3)*2(1+3)*2•Each symbols has at most Each symbols has at most one attribute shown in the one attribute shown in the corresponding boxcorresponding box–Numerical value in this Numerical value in this exampleexample–Operator symbols have no Operator symbols have no valuevalue•Arrows represent Arrows represent attribute attribute flowflow1010Attribute Flow Attribute Flow ExampleExample1111Attribute FlowAttribute FlowSynthetic and Inherited AttributesSynthetic and Inherited Attributes•In the previous example, semantic information is pass In the previous example, semantic information is pass up the parse treeup the parse tree–We call this type of attributes are called We call this type of attributes are called synthetic synthetic attributesattributes–Attribute grammar with synthetic attributes only are said Attribute grammar with synthetic attributes only are said to be to be S-attributedS-attributed•Semantic information can also be passed down the Semantic information can also be passed down the parse treeparse tree–Using Using inherited attributesinherited attributes–Attribute grammar with inherited attributes only are said Attribute grammar with inherited attributes only are said to be to be non-S-attributednon-S-attributed1212Attribute FlowAttribute FlowInherited AttributesInherited Attributes•L-attributedL-attributed grammars, such as the one on the next slide, can grammars, such as the one on the next slide, can still be evaluated in a single left-to-right pass over the input.still be evaluated in a single left-to-right pass over the input.•Each synthetic attribute of a LHS symbol (by definition of Each synthetic attribute of a LHS symbol (by definition of syntheticsynthetic)depends only on attributes of its RHS symbols.)depends only on attributes of its RHS symbols.•Each inherited attribute of a RHS symbol (by definition of Each inherited attribute of a