Chapter 6,Data Types and Type Checking,Principal Task of Compiler,Type inference - the computation and maintenance of information on data types Type checking the use of the information to ensure that each part of the program makes sense under the type rules of the language. These two tasks are related, performed together, and referred as type checking.,Data Type,Data type is set of values with certain operations on those values. Example: integer refers to a subset of the mathematical integers, together with the arithmetic operations that are provided by the language definition. Data types are described by a type expressions, which is A type name (such as integer) or A structured expressions (such as array10 ) Operations are assumed or implied,Type Expressions,Type expressions can occur in several places in a program. Explicit type information int x; - associates a type to a variable name class Car defines a new type name Implicit type information const greeting = “Hello!”; - array of char in Pascal. Type information, that is contained in declarations, is maintained in the symbol table and retrieved by the type checker whenever the associated names are referenced. Example: ai. A range checking is not statically determinable.,Simple Types,There are build-in ( predefined ) types in a programming language. Example: int and double The predefined types correspond to Numeric data types that are provided by machine architectures and whose operations exist as machine instructions. Elementary types like boolean or char whose behavior is easy to implement. Such data types are simple types, their values have no internal structure.,New Simple Data Types,In some programming languages it is possible to define new simple types. typedef enum red, green, blue Color;,Structured Types,Given a set of predefined types, new data types can be created using type constructors, such as array and struct. Such types are often called structured types. Arrays are commonly allocated contiguous storage from smaller to larger indexes.,Type Definitions,Type definitions provides a mechanism to assign names to type expressions. Example: Type declarations cause the declared type names to be entered into the symbol table. Type names are associated with attributes (like scope) in the symbol table.,typedef struct double r; int i; RealIntRec;,RealIntRec x;,Recursive Data Types,Recursive data types include lists, trees, and other structures. Languages may or may not permit the direct use of recursion in type declarations. C allows recursion only indirectly, through pointers.,struct intBST int val; intBST *left, *right; ;,Type Equivalence,Are two type expressions equivalent? bolean typeEqual ( TypeExp t1, TypeExp t2) Takes two type expressions Returns true, if they represent the same type according to the type equivalence rules of the language. Returns false, otherwise How are type expressions are within a compiler? One method is to syntax tree representation.,Example 1,Simple grammar for type expressions. No new type names are allowed.,var-decls - var-decls ; var-decl | var-decl var-dec - id: type-exp type-exp - simple-type | struct-type simple-type - int | bool | real | char | void struct-type - array num of type-exp | record var-decls end | pointer to type-exp | proc(type-exps) type-exp type-exps - type-exps , type-exp | type-exp,Example 1 (cont),record x: pointer to real; y: array 10 of int end,record,var (x),var (y),pointer,real,array (10),int,Structural Equivalence,The only one available in the absence of names for types. Two types are the same if and only if they have the same structure. If syntax trees are used to represent types, two types are the same if and only if they have syntax trees that are identical in structure. Two array are not equivalent unless they have the same size and component type. Two records are not equivalent unless they have the same components with the same name and the same order. Different choices can be made.,Type expressions with type declarations.,var-decls - var-decls ; var-decl | var-decl var-dec - id: simple-type-exp type-decls - type-decls ; type-decl | type-decl type-decl - id = type-exp type-exp - simple-simple-type | struct-type simple-type-exp - simple-type | id simple-type - int | bool | real | char | void struct-type - array num of type-exp | record var-decls end | pointer to type-exp | proc(type-exps) type-exp type-exps - type-exps , simple-type-exp | simple-type-exp,Example 2,Example 2 (cont),record x: pointer to real; y: array 10 of int end,t1 = pointer to real; t2 = array 10 of int t3 = record x: t1 y: t2 end,Name Equivalence,Two type expressions are equivalent if and only if they are either the same simple type or are the same type name. t1 and t2 are not equivalent. Actual type names are entered into the symbol table. It is possible to retain structural equivalence . When a name is encountered, its corresponding type expression must be fetched from the symb