TYPE CHECKING
ERRORS
Compiler must check that the source program follows
both the syntactic and semantic conventions of the
source language.
Static checks - reported during the compilation phase.
Dynamic checks - occur during the execution of the program.
STATIC CHECKS
Type checks: A compiler should report an error if an operator
is applied to an incompatible operand.
Flow of control checks: Places for transfer of control should be
specified.
Uniqueness checks: An object must be defined exactly (like the
type of an identifier, statements inside a case/switch
statement.)
Name Related checks: Same name must appear two or more
times.
Procedure foo
end foo;
TYPE CHECKER
Type information gathered by a type checker may be
needed when code is generated.
In general operators could be overloaded.
TYPE CHECKING
Types help identify
Errors, if an operator is applied to an incompatible operand
Dereferencing of pointers only
Indexing is done only on an array
To correct number of parameters to a procedure
Which operation to use for overloaded names and
operators (polymorphism)
TYPE SYSTEM
The design of a type checker for a language is based on
the information about the syntactic constructs in the
language.
Each expression has a type associated with it.
Types are either basic or constructed.
Basic types are atomic with no internal structure as far as
the program is constructed. e.g. integer, real, character,
etc.
Pointers, arrays, functions, records can be treated as
constructor types.
TYPE SYSTEM
A type system is a collection of rules for assigning type
expressions to variables.
A type checker implements the type system.
Examples type rules
Ifboth operands of the arithmetic operators of addition, sub
and mul are of type integer, then the result is of type integer.
The result of the unary & operator is a pointer to the object
referred to by the operand. If the operand is of type “int”,
then the type of the result is a “pointer to int”.
TYPE EXPRESSIONS
A type expression is either a basic type or is formed by
applying an operator called type constructor to other
expressions.
1. A basic type is a type expression. “void” is also a basic
type. A special basic type, typeError will signal an error.
2. Since type expression may be named, a type name is a
type expression.
3. Type expressions may contain variables whose values
are type expressions.
4. A type constructor applied to a type expression is a type
expression.
CONSTRUCTORS
a. Array : If T is a type expression, then array(I,T) is a type
expression, denoting an array with elements of type T
and I is an index set.
b. Products: If T1 and T2 are type expressions, then so is
T1 x T2
CONSTRUCTORS
c. Records: differs from the products as fields of records have
names. The record type constructor applied to tuple formed
from field names and field types.
Declares type name row representing type expression:
CONSTRUCTORS
d. Pointers: If T is a type expression, then pointer(T) is a
type expression denoting the type “pointer to an object of
type T”.
e. Functions: Functions in a programming language map a
domain type D to a range type R. Often, for
implementation reasons, there are limitations on the
types a function can return.
ERROR RECOVERY
Since type checking has the potential for catching errors
in programs, it is important to do something when an
error is discovered.
Since the error handling affects the type checking rules,
it has to be designed into the type system right from the
start.
The rules must be prepared to cope with errors.
SPECIFICATIONS OF A SIMPLE TYPE
CHECKER
The type of each identifier must be declared before the
identifier is used. The type checker is a translation
scheme that synthesizes the type of each expression from
the type of its sub-expressions.
P --> D; E
D--> D; D | id: T
T--> char | integer | array[num] of T | * T
E--> literal | num | id | E mod E | E[E] | E*
Base Types: char, integer, type-error
TRANSLATION SCHEME
P --> D; E
D--> D;D
D--> id :T { addtype([Link],[Link]);}
T--> char {[Link]= char;}
T--> integer {[Link]=integer;}
T-->*T1 {[Link]=pointer([Link]);}
T--> array[num] of T1 { [Link] =array(1..[Link],[Link]);
}
TYPE CHECKING OF EXPRESSIONS
E--> literal { [Link]=char;}
E--> num { [Link] =integer;}
E--> id { [Link] =lookup([Link]);}
E--> E1 mod E2 { [Link] =If ([Link] ==integer) and
(E2. Type ==integer) integer; else
type-error;
E--> E1[E2] { [Link]=if
(([Link]==integer)&&
([Link]==array(s,t)) t; else type-
error;}
E--> *E1 { [Link] = if ([Link]
==pointer(t)) t else type-error;
TYPE CHECKING FOR STATEMENTS
S--> id=E { if ([Link]==[Link]) void; else
type-error;}
S--> if E then S1 { if ([Link]==boolean) [Link];
else type-error;}
S--> While E do S1 { if ([Link]==boolean) [Link];
else type-error;
S--> S1; S2 { if ([Link]==void) if ([Link]
==void) void; else type-error;}
TYPE CHECKING OF FUNCTIONS
E--> E(E)
T--> T ‘->’ T { [Link] = [Link] -> [Link]}
E--> E1(E2) {[Link] = I f (([Link] ==s) &&
([Link] == s--> t)) t; else type-
error;