Type checking in compiler design

Type checking in compiler design

1. In syntax-directed translation, we attach ATTRIBUTES to grammar symbols. The values of the attributes are computed by SEMANTIC RULES associated with grammar productions. Conceptually, we have the following flow:

2. There are two ways to represent the semantic rules we associate with grammar symbols. SYNTAX-DIRECTED DEFINITIONS (SDDs) do not specify the order in which semantic actions should be executed TRANSLATION SCHEMES explicitly specify the ordering of the semantic actions.

3. Synthesized attributes Synthesized attributes depend only on the attributes of children. They are the most common attribute type.

4. Calculating synthesized attributes 3*5+4newline

5. Inherited attributes An inherited attribute is defined in terms of the attributes of the node ’ s parents and/or siblings.

6. Calculating Inherited attributes id1, id2, id3

7. Dependency Graphs

8. S-Attributed example

9. Type Checking • Language comes with type system – Set of rules – What types are there? – Where do they appear? • Compiler’s job – Assign type expression to each component – Determine that these type expressions – conform to the type system

10. The purpose of types To define what the program should do. e.g. read an array of integers and return a double To guarantee that the program is meaningful. that it does not add a string to an integer that variables are declared before they are used To document the programmer's intentions. better than comments, which are not checked by the compiler To optimize the use of hardware. reserve the minimal amount of memory, but not more use the most appropriate machine instructions

11. What belongs to type checking Depending on language, the type checker can prevent application of a function to wrong number of arguments, application of integer functions to floats, use of undeclared variables in expressions, functions that do not return values, division by zero array indices out of bounds, Languages differ greatly in how strict their static semantics is: few of the things above is checked by all programming languages!

12. Type Checking: Dynamic and Static • Type checking can be done dynamically for any language ( i.e at run-time) – compiler generates code to do the checks at runtime • Better to do it statically (i.e. at compile-time) • A sound type system eliminates the need for dynamic checking. • A language is strongly typed if compiler guarantees that program it accepts will run without type error. – Examples of strongly typed: Java, C#, Pascal, Ruby, Python

13. Rules for Type Checking • Type Synthesis – Builds the type of an expression from the types of its subexpressions – Requires names to be declared before usage • Type inference – determines the type of a construct from the way it is used

14. Type Conversions • Type conversion rules vary from language to language • Explicit type conversion – Must be done by the programmer – Called cast • Implicit type conversion – Done automatically by the compiler – Called coercions – Widening (used most often) vs narrowing