Compiler Design CSE 504
Type Checking
Department of Computer Science, Stony Brook University
Static Checking
Token Stream
Parser
Abstract Syntax Tree
Static Checker
Decorated Abstract Syntax Tree
Intermediate Code Generator
Intermediate Code
Static (Semantic) Checks
Type checks: operator applied to incompatible operands? Flow of control checks: break (outside while?) Uniqueness checks: labels in case statements Name related checks: same name?
Department of Computer Science, Stony Brook University
Type Checking
Problem: Verify that a type of a construct matches that expected by its context. Examples: mod requires integer operands (PASCAL) * (dereferencing) applied to a pointer a[i] indexing applied to an array f(a1, a2, , an) function applied to correct arguments.
Information gathered by a type checker: Needed during code generation.
3
Department of Computer Science, Stony Brook University
Type Systems
A collection of rules for assigning type expressions to the various parts of a program. Based on: Syntactic constructs, notion of a type. Example: If both operators of +, -, * are of type integer then so is the result. Type Checker: An implementation of a type system.
Syntax Directed.
Sound Type System: eliminates the need for checking type errors during run time.
Department of Computer Science, Stony Brook University
Type Expressions
Implicit Assumptions:
Each program has a type Types have a structure
Basic Types
Expressions Statements
Type Constructors
Arrays Records Sets Pointers Functions
Boolean
Real Enumerations Void Variables
Character
Integer Sub-ranges Error Names
Department of Computer Science, Stony Brook University
Representation of Type Expressions
-> ->
cell = record
x
x char char
pointer integer
x char
pointer integer
x ptr
info int next
Tree
DAG
(char x char)-> pointer (integer)
struct cell { int info; struct cell * next; };
Department of Computer Science, Stony Brook University
Type Expressions Grammar
Type -> int | float | char | | void | error | name | variable | array( size, Type) | record( (name, Type)*) | pointer( Type) | tuple((Type)*) | arrow(Type, Type)
Basic Types
Structured Types
Department of Computer Science, Stony Brook University
A Simple Typed Language
Program -> Declaration; Statement Declaration -> Declaration; Declaration | id: Type Statement -> Statement; Statement | id := Expression | if Expression then Statement | while Expression do Statement Expression -> literal | num | id | Expression mod Expression | E[E] | E | E (E)
Department of Computer Science, Stony Brook University
Type Checking Expressions
E E E E -> int_const { [Link] = int } -> float_const { [Link] = float } -> id { [Link] = sym_lookup([Link], type) } -> E1 + E2 {[Link] = if [Link] {int,
float} | [Link] {int, float} then error else if [Link] == [Link] == int then int else float }
Department of Computer Science, Stony Brook University
Type Checking Expressions
E -> E1 [E2] E -> *E1
{[Link] = if [Link] = array(S, T) & [Link] = int then T else error} {[Link] = if [Link] = pointer(T) then T else error}
E -> &E1 E -> E1 (E2) E -> (E1, E2)
{[Link] = pointer([Link])}
{[Link] = if ([Link] = arrow(S, T) & [Link] = S, then T else err}
{[Link] = tuple([Link], [Link])}
10
Department of Computer Science, Stony Brook University
Type Checking Statements
S -> id := E S -> if E then S1
{[Link] := if [Link] = [Link] then void else error} {[Link] := if [Link] = boolean then [Link] else error}
S -> while E do S1
S -> S1; S2
{[Link] := if [Link] = boolean then [Link]}
{[Link] := if [Link] = void [Link] = void then void else error}
11
Department of Computer Science, Stony Brook University