上海交通大学：《编译原理》教学资源_教学资料_第五周讲义_Type Checking

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 }

Type Checking of Statements S→id=E if(id.type=E.type then S.type=void else S.type-type-error S→if E then S, if(E.type=boolean then S.type=S1.type else S.type=type-error S-→while E do S, if (E.type=boolean then S.type=S1.type else S.type-type-error CS308 Compiler Theory 6

Type Checking of Statements S → id = E { if (id.type=E.type then S.type=void else S.type=type-error } S → if E then S1 { if (E.type=boolean then S.type=S1.type else S.type=type-error } S → while E do S1 { if (E.type=boolean then S.type=S1.type else S.type=type-error } CS308 Compiler Theory 6

Type Checking of Functions E->E(E2){if (E2.type=s and E1.type=s >t)then E.type=t else E.type=type-error Ex: int f(double x,char y){...} f double x char→int argument types return type CS308 Compiler Theory 7

Type Checking of Functions E → E1 ( E 2 ) { if (E 2.type=s and E1.type=s →t) then E.type=t else E.type=type-error } Ex: int f(double x, char y) { ... } f: double x char → int argument types return type CS308 Compiler Theory 7

Structural Equivalence of Type Expressions How do we know that two type expressions are equal? As long as type expressions are built from basic types (no type names), we may use structural equivalence between two type expressions Structural Equivalence Algorithm (sequiv): if(s and t are same basic types)then return true else if(s=array(s,s2)and t=array(t,t2))then return(sequiv(s1,t)and sequiv(s2,t2) else if(s=sx s2 and t=tx t2)then return (sequiv(s,t)and sequiv(s2,t2)) else if(s=pointer(s)and t=pointer(t)then return(sequiv(s,t)) else if(s=s>s2 and t=t>t)then return (sequiv(s1,t)and sequiv(s2,t2)) else return false CS308 Compiler Theory 8

Structural Equivalence of Type Expressions • How do we know that two type expressions are equal? • As long as type expressions are built from basic types (no type names), we may use structural equivalence between two type expressions Structural Equivalence Algorithm (sequiv): if (s and t are same basic types) then return true else if (s=array(s1,s 2) and t=array(t1,t 2)) then return (sequiv(s1,t1) and sequiv(s 2,t 2)) el if ( se if (s = s dt t t ) th t ( i ( t ) d i( t )) 1 x s 2 an d t = t1 x t 2 ) then re turn (sequiv ( s1,t1) an d sequiv ( s 2,t 2)) else if (s=pointer(s1) and t=pointer(t1)) then return (sequiv(s1,t1)) else if (s = s1 → s 2 and t = t1 → t 2) then return (sequiv(s1,t1) and sequiv(s 2,t 2 else if (s s )) 1 → s 2 and t t1 → t 2 ) then return (sequiv(s1,t1) and sequiv(s 2,t 2)) else return false CS308 Compiler Theory 8

Names for Type Expressions In some programming languages,we give a name to a type expression, and we use that name as a type expression afterwards. type1ink=个cell; p,q,r,s have same types var p,q link; varr,s:个cel1 How do we treat type names? Get equivalent type expression for a type name(then use structural equivalence),or Treat a type name as a basic type. CS308 Compiler Theory 9

Names for Type Expressions • In some programming languages, we give a name to a type expression, and h if d d we use t hat name as a type express ion a fterwar ds. type link = ↑ cell; ? p,q,r,s have same types ? var p,q : link; var r,s : ↑ cell • How do we treat type names? – Get equivalent type expression for a type name (then use structural equivalence), or – Treat a type name as a basic type Treat a type name as a basic type. CS308 Compiler Theory 9

Cycles in Type Expressions type1ink-个cell; type cell record x int, next:link end We cannot use structural equivalence if there are cycles in type expressions. We have to treat type names as basic types. >but this means that the type expression link is different than the type expression Tcell. CS308 Compiler Theory 10

Cycles in Type Expressions type link = ↑ cell; type cell = record x : int, next : link end; • We cannot use structural equivalence if there are cycles in type expressions. • We have to treat type names as basic types. Î but this means that the type expression link is different than the type expression ↑cell. CS308 Compiler Theory 10