Chapter _4_Semantic Analysis .pptx

this document is design document

1. Chapter 4 Semantic Analysis

2. C ONTENTS Introduction A Short Program Semantic Analysis Annotated Abstract Syntax tree (AST) Syntax-Directed Translation Syntax-Directed Definitions (SDD) Translation Schemes

3. Where are we? Semantic Analyzer

4. Introduction Program is lexically well-formed: Identifiers have valid names. Strings are properly terminated. Program is syntactically well-formed: Class declarations have the correct structure. Expressions are syntactically valid. Does this mean that the program is legal?

5. A Short Program class MyClass implements MyInterface { string myInteger ; void doSomething () { int [] x = new string; x[5] = myInteger * y; } void doSomething () { } int fibonacci ( int n) { return doSomething () + fibonacci (n – 1); } }

6. A Short Program… class MyClass implements MyInterface { string myInteger ; void doSomething () { int [] x = new string; x[5] = myInteger * y; } void doSomething () { } int fibonacci ( int n) { return doSomething () + fibonacci (n – 1); } }

7. Semantic Analysis Ensure that the program has a well-defined meaning. Verify properties of the program that aren't caught during the earlier phases: Variables are declared before they're used. Expressions have the right types. Classes don't inherit from nonexistent base classes Type consistence; Inheritance relationship is correct; A class is defined only once; A method in a class is defined only once; Reserved identifiers are not misused; … Once we finish semantic analysis, we know that the user's input program is legal.

8. A Simple Semantic Check “Matching identifier declarations with uses” Important analysis in most languages If there are multiple declarations, which one to match? The scope of an identifier is the portion of a program in which that identifier is accessible

9. Semantic Analysis… Semantic Analysis  is the third phase of Compiler. Semantic Analysis makes sure that declarations and statements of program are semantically correct. It is a collection of procedures which is called by parser as and when required by grammar. Both syntax tree of previous phase and symbol table are used to check the consistency of the given code.  Last compiler phase that can report errors to the user. Type checking  is an important part of semantic analysis where compiler makes sure that each operator has matching operands

10. Semantic Analysis… Semantic Analyzer: It uses syntax tree and symbol table to check whether the given program is semantically consistent with language definition. It gathers type information and stores it in either syntax tree or symbol table. This type information is subsequently used by compiler during intermediate-code generation. Semantic Errors: Errors recognized by semantic analyzer are as follows: Type mismatch Undeclared variables Reserved identifier misuse Access of an out of scope variable. Actual and formal parameter mismatch.

11. Semantic Analysis… Semantic analysis also gathers useful information about program for later phases: E.g. count how many variables are in scope at each point. Why can't we just do this during parsing? Read about Limitations of CFGs

12. Semantic Analysis… Functions of Semantic Analysis: Type Checking – Ensures that data types are used in a way consistent with their definition. Label Checking – A program should contain labels references. Flow Control Check – Ensures that control structures are used in the right way example: no break statement outside a loop) Scope resolution. This involves determining the scope of a name Array-bound checking. This is determining whether all array references in a program are within the declared range Example: float x = 10.1; float y = x*30; In the above example integer 30 will be typecasted to float 30.0 before multiplication, by semantic analyzer.

13. Semantic Analysis… Semantic Analysis can be implemented using Annotated Abstract Syntax tree (AST) The input for Semantic Analysis (syntax analyzer) is Abstract Syntax tree and the output is Annotated Abstract Syntax tree . Annotated Abstract Syntax tree is parse-tree that also shows the values of the attributes at each node. Y=3* x+z

14. Syntax-Directed Translation(SDT) SDT is used to drive semantic analysis tasks based on the language’s syntax structures What semantic tasks? Generate AST (abstract syntax tree) Check type errors Generate intermediate representation (IR) What is synatx structures? Context free grammar (CFG) Parse tree generated from parser How? Attach attributes to grammar symbols/parse tree Attach either rules or program fragments to productions in a grammar Evaluate attribute values using semantic actions/ semantic rules associated with the production rules.

15. Two Types of Attributes In semantic rule attributes are value that holds or represent anything we need: a string, a type, a number, a memory location , … represented as (VAL) and they are two types Reading assignment Synthesized attributes vs Inherited attributes

16. Two Types of Syntax Directed Translation Sy ntax-directed definition A general way to associate actions (i.e., programs) to production rules of a context-free grammar. Used for carrying out most semantic analyses as well as code translation A syntax-directed definition associates: With each grammar symbol, a set of attributes, and With each production, a set of semantic rules for computing the values of the attributes associated with the symbols appearing in the production A grammar with attributes and semantic rules is called an attributed grammar A parse tree augmented with the attribute values at each node is called an annotated parse tree.

17. Two Types of Syntax Directed Translation When we associate semantic rules with productions, we use two notations:- Syntax-Directed Definitions associates a production rule with a set of semantic actions, and we do not say when they will be evaluated. don’t specify order of evaluation/ Translation - hides implementation details Grammar +semantic rule Translation Schemes indicate the order of evaluation of semantic actions associated with a production rule. shows more implementation details

18. Attribute Grammar An  attribute grammar  is an extension of context-free  grammar  that enables definition of context-sensitive aspects of a language and its translation.  Attribute grammar is a special form of context-free grammar where some additional information (attributes) are appended to one or more of its non-terminals in order to provide context-sensitive information. Each attribute has well-defined domain of values, such as integer, float, character, string, and expressions.

19. Attribute Grammar Attribute grammar is a medium to provide semantics to the context-free grammar and It can help specify the syntax and semantics of a programming language. Attribute grammar (when viewed as a parse-tree) can pass values or information among the nodes of a tree. Example: E → E + T { E.value = E.value + T.value } The right part of the CFG contains the semantic rules that specify how the grammar should be interpreted.

20. Attribute Grammar Semantic attributes may be assigned to their values from their domain at the time of parsing and Evaluated at the time of assignment or conditions. Based on the way the attributes get their values, they can be broadly divided into two categories : synthesized attributes and inherited attributes. Expansion  : When a non-terminal is expanded to terminals as per a grammatical rule Reduction  : When a terminal is reduced to its corresponding non-terminal according to grammar rules. Syntax trees are parsed top-down and left to right. Whenever reduction occurs, we apply its corresponding semantic rules (actions).

21. Attribute Grammar Semantic analysis uses Syntax Directed Translations to perform the above tasks. Semantic analyzer attaches attribute information with AST, which are called Attributed AST. Attributes are two tuple value, <attribute name, attribute value> Example int value = 5; <type, “integer”> < presentvalue , “5”> For every production, we attach a semantic rule.

22. Two Types of Syntax Directed Translation E  E+T | T T  T*F | F F  id This is a grammar to syntactically validate an expression having additions and multiplications in it. Now, to carry out semantic analysis we will augment SDT rules to this grammar, in order to pass some information up the parse tree and check for semantic errors, if any. In this example, we will focus on the evaluation of the given expression, as we don’t have any semantic assertions to check in this very basic example.  E  E+T { E.val = E.val + T.val } E  T { E.val = T.val } T  T*F { T.val = T.val * F.val } T  F { T.val = F.val } F  id { F.val = id.lexval }

23. Two Types of Syntax Directed Translation To construct the SDT Step1: Generate the syntax tree from the given Grammar Step2:Associate production rule with semantic ruel Step3:Parse the tree from left to right and top to down Step4: When ever there is a reduction from Right hand side to left side go to the production and carryout action

24. Syntax-Directed Definitions (SDD) SDD is a context-free grammar together with, attributes and rules . Attributes are associated with grammar symbols and rules are associated with productions. If X is a symbol and a is one of its attributes, then we write X.a to denote the value of a at a particular parse-tree node labeled X. Production Semantic Rules L → E return { print(E.val) } E → E 1 + T { E.val = E 1 .val + T.val } E → T { E.val = T.val } T → T 1 * F { T.val = T 1 .val * F.val } T → F { T.val = F.val } F → ( E ) { F.val = E.val } F → digit { F.val = digit .lexval } Symbols E, T, and F are associated with a synthesized attribute val . The token digit has a synthesized attribute lexval (it is assumed that it is evaluated by the lexical analyzer).

25. Annotated Parse Tree -- Example

26. Dependency Graph Input: 5+3*4 L E.val=17 E.val=5 T.val=12 T.val=5 T.val=3 F.val=4 F.val=5 F.val=3 digit.lexval =4 digit.lexval =5 digit.lexval =3 A dependency graph suggests possible evaluation orders for an annotated parse-tree.

27. Example2 exp -> exp + term exp1.val = exp2.val + term.val exp -> term exp.val = term.val term -> term * factor term1.val = term2.val * factor.val term -> factor term.val = factor.val factor ->num factor.val = num.lexval factor -> ( exp ) factor.val = exp.val Input : 2 * (4 + 5)

28. A Translation Scheme Example (cont.) Reading assignment S-attributed SDT L-attributed SDT Translation Schemes

29. Type Checking in Compiler Design Type is an idea that varies from language to language Limit the programmer what type may be used. Type checking is the process of verifying and enforcing constraints of types in values. A compiler must check that the source program should follow the syntactic and semantic conventions of the source language and it should also check the type rules of the language. It allows the programmer to limit what types may be used in certain circumstances and assigns types to values. The type-checker determines whether these values are used appropriately or not.

30. Type Checking in Compiler Design It checks the type of objects and reports a type error in the case of a violation, and incorrect types are corrected. Whatever the compiler we use, while it is compiling the program, it has to follow the type rules of the language. Every language has its own set of type rules for the language. We know that the information about data types is maintained and computed by the compiler.

31. Type Checking in Compiler Design The information about data types like INTEGER, FLOAT, CHARACTER, and all the other data types is maintained and computed by the compiler. The compiler contains modules, where the type checker is a module of a compiler and its task is type checking. Conversion from one type to another type is known as implicit if it is to be done automatically by the compiler. Implicit type conversions are also called Coercion and coercion is limited in many languages. Example: An integer may be converted to a real but real is not converted to an integer. Conversion is said to be Explicit if the programmer writes something to do the Conversion

32. Type Checking in Compiler Design Types of Type Checking: There are two kinds of type checking: 1. Static Type Checking. 2. Dynamic Type Checking. Static Type Checking: Static type checking is defined as type checking performed at compile time. It checks the type variables at compile-time, which means the type of the variable is known at the compile time

33. Type Checking in Compiler Design Task of static Type Checking Type checking . Operator applied to incompatible operands If array variable is added with the function variable Flow of control check: statement that result in a branch need to be determined correctly. Break statements Uniqueness check: object must be defined exactly once for some scenarios Labels in case statements need to be unique. Name related check: some name appear more than once

34. Type Checking in Compiler Design Dynamic Type Checking: Dynamic Type Checking is defined as the type checking being done at run time. In Dynamic Type Checking, types are associated with values , not variables. Implementations of dynamically type-checked languages runtime objects are generally associated with each other through a type tag, which is a reference to a type containing its type information . Dynamic typing is more flexible. A static type system always restricts what can be conveniently expressed. Dynamic typing results in more compact programs since it is more flexible and does not require types to be spelled out. Programming with a static type system often requires more design and implementation effort.

35. Next reading assignment rules of Type Checking in compiler Intermediate Languages Run time- Environments Code Generation and Optimization