Type Checking CS308 Compiler Theory 1
Type Checking CS308 Compiler Theory 1
Type Checking A compiler has to do semantic checks in addition to syntactic checks ● Semantic Checks Static-done during compilation -Dynamic-done during run-time Type checking is one of these static checking operations we may not do all type checking at compile-time -Some systems also use dynamic type checking too. A type system is a collection of rules for assigning type expressions to the parts of a program. A type checker implements a type system. A sound type system eliminates run-time type checking for type errors. A programming language is strongly-typed,if every program its compiler accepts will execute without type errors. In practice,some of type checking operations are done at run-time(so,most of the programming languages are not strongly-typed). Ex:int x[100];...x[i]>most of the compilers cannot guarantee that i will be between 0 and 99 CS308 Compiler Theory 2
Type Checking • A compiler has to do semantic checks in addition to syntactic checks. • Semantic Checks Semantic Checks – Static – done during compilation – Dynamic – done during run-time • T h ki ype checking is one of these static checking operations is one of these static checking operations. – we may not do all type checking at compile-time. – Some systems also use dynamic type checking too. • A t t ype system i ll ti f l f i i t i t th t f is a collection of rules for assigning type expressions to the parts of a program. • A type checker implements a type system. • A sound type system eliminates run-time type checking for type errors. • A programming language is strongly-typed, if every program its compiler accepts will execute without type errors. – In practice, some of type checking operations are done at run-time (so, most of the programming languages are not strongly-typed). – Ex: int x[100]; … x[i] Î most of the compilers cannot guarantee that i will be between 0 and 99 CS308 Compiler Theory 2
Type Expression The type of a language construct is denoted by a type expression. .A type expression can be: A basic type a primitive data type such as integer,real,char,boolean,... type-error to signal a type error ·void:no type A type name a name can be used to denote a type expression. -A type constructor applies to other type expressions. arrays:If T is a type expression,then array(1,T)is a type expression where I denotes index range. Ex:array(0..99,int) products:If T and T2 are type expressions,then their cartesian product Tx T2 is a type expression.Ex:int x int pointers:If T is a type expression,then pointer(T)is a type expression.Ex:pointer(int) functions:We may treat functions in a programming language as mapping from a domain type D to a range type R.So,the type of a function can be denoted by the type expression D-R where D are R type expressions.Ex:int-int represents the type of a function which takes an int value as parameter,and its return type is also int. CS308 Compiler Theory 3
Type Expression • The type of a language construct is denoted by a type expression. • A type expression can be: – A basic type • a primitive data type such as integer, real, char, boolean, … • type-error to signal a type error • void : no type – A type name • a name can be used to denote a type expression. – A type constructor applies to other type expressions. • arrays: If T is a type expression, then array(I,T) is a type expression where I denotes index range. E (0 99 i ) Ex: array(0..99,int) • products: If T1 and T2 are type expressions, then their cartesian product T1 x T2 is a type expression. Ex: int x int • pointers: If T is a type expression then : If T is a type expression, then pointer(T) pointer(T) is a type expression Ex: pointer(int) is a type expression. Ex: pointer(int) • functions: We may treat functions in a programming language as mapping from a domain type D to a range type R. So, the type of a function can be denoted by the type expression D→R where D are R type expressions. Ex: int→int represents the type of a function which takes an int value t d it t t i l i t CS308 Compiler Theory 3 as parameter, and its return type is also int
A Simple Type Checking System P→D:E D→D:D D→id:T{ addtype(id.entry,T.type)) T→char{T.type=char} T→int {T.type=int T→real{T.type-real} T-T T.type=pointer(Ti.type)} T-array[intnum]of T{T.type=array(1..intnum.val,T.type)} CS308 Compiler Theory 4
A Simple Type Checking System P → D;E D → D;D D → id:T { addtype(id.entry,T.type) } T → char { T.type=char } T → int { T.type=int } T → real { T.type=real } T → ↑ T1 { T.type=pointer(T1.type) } T → array[intnum] of T1 { T.type=array(1..intnum.val,T1.type) } CS308 Compiler Theory 4
Type Checking of Expressions E→id E.type=lookup(id.entry)) E→charliteral E.type=char E→intliteral E.type=int} E→realliteral E.type=real E-E+E2 if(E1.type=int and E2.type=int)then E.type=int else if(E.type=int and E2.type=real)then E.type=real else if(E.type=real and E2.type=int)then E.type=real else if(E.type=real and E2.type=real)then E.type=real else E.type-type-error E→E1E2] if(E2.type=int and E.type=array(s,t))then E.type=t else E.type=type-error E→E1个 if(E1.type-pointer(t))then E.type=t else E.type-type-error CS308 Compiler Theory 5
Type Checking of Expressions E → id { E.type=lookup(id.entry) } E → charliteral { h} E.type=c har } E → intliteral { E.type=int } E → reallit l era l {Et l} . ype=rea l } E → E1 + E 2 { if (E1.type=int and E 2.type=int) then E.type=int else if (E else if (E type=int and E type=real) then E type=real 1.type=int and E 2.type=real) then E.type=real else if (E1.type=real and E 2.type=int) then E.type=real else if (E1 type =real and E 2 else if (E type =real) then E type =real 1.type real and E 2.type real) then E.type real else E.type=type-error } E → E1 [ E 2 ] { if ( E 2.type=in t a n d E1 E E .type = array(s,t)) t h en E.type = t 1 [E 2 ] { if (E 2.type int and E1.type array(s,t)) then E.type t else E.type=type-error } E → E1 ↑ { if ( E1.type= pointer ( t)) then E.type=t CS308 Compiler Theory 5 1 ↑ { ( 1 yp p ( )) yp else E.type=type-error }