Type checking compiler construction Chapter #6

Chapter 6
Type Checking
Compiler Design

1. Type checking Muhammad Daniyal Salman Saif Ali

2. Lexical Analyzer Tokens Syntax Analyzer Context free grammar Parse tree(Parser)

3. Semantic Analyzer Before we don’t have rules and attributes in CFG Then we add some semantic rule with productions Rule Syntax Directed Definition Each grammar symbol associate with some attributes that gives information CFG + Semantic Rules = Syntax directed definition

4. Do not specify the order in which semantic actions should be executed. Translation Scheme explicitly specify the ordering of the semantic actions

5. TYPES OF ATTRIBUTES Synthesized Inherited Synthesized These attributes get value from child node attributes Inherited These attributes get value from parent node or from siblings

6. What Semantic Analyzer do ? Scope resolution Variables should be declare at least once before usage Array Bound Checking When boundaries of an Array exceed Type Checking Check type Eg: int x = 15.5;

7. Type Checking Type checking is the process of verifying that each operation executed in a program respects the type system of the language. This generally means that all operands in any expression are of appropriate types and number. Much of what we do in the semantic analysis phase is type checking.

8. How to design a Type C hecker? When designing a type checker for a compiler, here’s the process: Identify the types that are available in the language Identify the language constructs that have types associated with them Identify the semantic rules for the language A language is considered strongly- typed if each and every type error is detected during compilation.

9. Type Checking Preventions A pplication of a function to wrong number of arguments A pplication of integer functions to floats U se of undeclared variables in expressions F unctions that do not return values , D ivision by zero A rray indices out of bounds

10. Two Types of Type Checking Static Type Checking Dynamic Type Checking Static Type Checking : Check on Compile time 1- Type Check 2+2.5 = Error 2- Flow of Control Flow of control stop at somewhere

11. 3- Uniqueness Check Int a = 2; a should be unique 4- Name Related Check Calling add() Definition add() Example: For example, if a and b are of type int and we assign very large values to them, a * b may not be in the acceptable range of ints , or an attempt to compute the ratio between two integers may raise a division by zero. These kinds of type errors usually cannot be detected at compiler time.

12. Dynamic Type Checking : Check on Runtime Common dynamically typed languages are : JavaScript, Php and Python etc. Most of the languages used both. Static or Dynamic doesn’t mean Weak or strong

13. Type System Type system is a collection of rules applied on Type expression Designing of type checker vary from language to language E.G : 2+2 = 4 Each expression has a type associated Basic types: Boolean, Int , Char

14. Constructed types : Pointer, Array , Structures Type Expression A basic type is a type expression A type name is a type expression A type expression can be formed by applying the array type constructor to a number and a type expression . A record is a data structure with named field A type expression can be formed by using the type constructor for function types

15. If s and t are type expressions, then their Cartesian product s*t is a type expression Type expressions may contain variables whose values are type expressions Error Recovery Type checker found an error They report the location and nature of an error Ideal type checker recover the error and move on to detect more

16. Type Checking of Statements S -> id := E { S.type := if id.type = E.type then void else error} S -> if E then S1 { S.type := if E.type = boolean then S1.type else error} S -> while E do S1 { S.type := if E.type = boolean then S1.type} S -> S1; S2 { S.type := if S1.type = void ∧

17. Equivalence of Type Expression Structural Equivalence Name for Type Expression Structural Equivalence: Two expression have same basic type Formed by applying same constructor type Name for Type Expression: In some languages type expression can given some name

18. Type Conversion Expression X + I (The X is real and I is int type) First compiler check both of the operand are of same type or not Usually convert int type into real type and perform real operand operation How to Convert X + I (int convert into real) X I intoreal real +

19. Intoreal operation convert I intoreal Or real+ operation perform real addition in between both real operands Coercions Convert one type to another automatically called implicit or coercions like ASCII It is limited in many language in case of no information loss Integer convert into real but no vice versa because of some memory loss When programmer write something to convert called Explicit

20. Over Loading Functions The same name is used for several different operations over several different types. Type checker is used to detect the error while creating overloading functions Polymorphic Functions A piece of code that can be executed with arguments of different types

21. Thank you