CHAPTER FIVE:

TYPE CHECKING

1
OUTLINE
 Introduction
 Type Systems

 Type Conversions

2
 INTRODUCTION
What are types?
 Type: the value computed during the execution of the program
is described by type.
 Type error: improper or inconsistent operation during program
execution.
 Type safety: is absence of type error and no any completion
error.
 By using Semantic checks rule to check whether or not
semantic error. 3
INTRODUCTION(CONT…)
 The two main kinds of Semantic checks are:
 Static – done during compilation
 Dynamic – done during run-time

 The compiler must check that the source program follows

both the syntactic and semantic conventions of the source
language.
 This checking is called static checking (to distinguish it
from dynamic checking executed during execution of the
target program).
 Static checking ensures that certain kind of errors will be
4
detected and reported.
 STATIC CHECKS
 Why static checking?
 Efficient code, but in dynamic checking slow downs the
program.
 Guarantees that all execution is safe.

 Typical examples of static checking are:

 Type checks
 Flow-of-control checks
 Uniqueness checks
 Name related check…

5
 STATIC CHECKING(CONT…)

 Type checks: A compiler should report an error if an

operator is applied to an incompatible operand.
 Example: if an array variable and a function variables are
added together.

 Flow of control check:

 Statements that cause flow of control to leave a
construct must have some place to which to transfer
the flow of control.
6
 STATIC CHECKING(CONT…)

 Example: a break statement in C causes control to leave the

smallest enclosing while, for, or switch statement.
 An error occurs if such an enclosing statement does not
exist.

7
 STATIC CHECKING(CONT…)
 Uniqueness check:
 Variables or objects must be defined exactly once.
 A compiler should report an error if Redefined variable.
 Example: in most programing language, an identifier must be
declared uniquely.

8
 STATIC CHECKING(CONT…)

 Name related check. the same name should be used to

start and end the loop.
It uses specific name due to case sensitivity.
Example: During the declaration of variables
int A!= int a

9
STATIC CHECKS(CONT…)
 Parsing finds syntactic errors
 An input that can't be derived from the grammar

 Static checking finds semantic errors.

 Using undeclared variables
 inappropriate instruction such as, return, break,
continue used in wrong place.
 Calling a function with the wrong number/kind of
arguments.
 Invalid conditions (not Boolean) in conditionals
10
 Applying operators to the wrong kinds of arguments
 STATIC CHECKS(CONT…)
Other Static Checks
 A variety of other miscellaneous static checks can be
performed
 Check for return statements outside of a function.
 Check for case statements outside of a switch statement.
 Check for duplicate cases in a case statement.
 Check for break or continue statements outside of any loop.
 Check for goto statements that jump to undefined labels.
 Check for goto statements that jump to labels not in scope.
11
 TYPE CHECKING
 Type checking is one of these static checking
operations.
 A type checker verifies that the type construct matches

that expected by its context.

For example, a type checker should verify that the
type value assigned to a variable is compatible with
the type of the variable.
For instance, mod (%) expects two integer

operands.

12
 TYPE CHECKING(CONT..)

Position of type checker

 If any errors are found, they will be reported by the type checker.
 Type information produced by the type checker may be needed
13
when the code is generated.
 THE NEED FOR TYPE CHECKING

 We want to generate machine code

 Memory layout

 Different data types have different sizes

 In C, char, short, int, long, float, double usually have

different sizes.
 Need to allocate different amounts of memory for different

types
 Choice of instructions

 Machine instructions are different for different types.

 add (for i386 ints)

 fadd (for i386 floats)

14
 TYPE SYSTEMS
 Type systems is a collection of rules implemented by the
type checker for assigning type expressions to the various
parts of a program.
 A type checker implements a type system.
 In almost all languages, types are either basic or constructed.
 In C++, for example: int, float, double, char,… are basic
types
 Array, struct, … are constructed types

15
TYPE EXPRESSION
 The type of a language construct will be denoted by
a type expression.
 A type expression is either a basic type or formed
by applying an operator called type constructor to
the type expression.

16
TYPE EXPRESSIONS(CONT…)
 The type expression may be obtained by using the following
definition.
 A basic type is a type expression:

 It is a primitive data type.

 Example: Boolean, char, integer, double and real .
 A type name is a type expression

 A type constructor applied to a type expression is a type

expression.
 The type checker uses two more basic types:

 Void→indicates absence of type error.

 Type-error →indicates the presence of a type error.

17
TYPE CONSTRUCTOR
 The following are type constructors:
 Arrays: if I in an index set and T is a type expression, then

Array (I, T) is a TE(type expression):

 In C++ int A[10];
 In java, int[] A = new int[10];
 In pascal var A: array [1…10] of integer; associates the
type expression array(1..10, integer) with A.
 Products: if T1 and T2 are type expressions, the Cartesian

product T1 x T2 is a TE. X is left associative.

 Example: f(int, char), int x char -> (1,‟a‟), (2,‟b‟),
 In function parameters f(True, 5) = Boolean X int…

18
 TYPE CONSTRUCTOR(CONT…)

 Records: Record( (field1 X T1)X(field2 X T2)X...)

For example, struct{ int age; float cgpa;}
 record( ( age X integer ) X ( cgpa X float ) )
 Pointers: if T is a TE then pointer (T) is a TE. Denotes
the type “pointer to an object of type T.”
For example - var p: ^integer -> pointer(integer)

- int *a;
19
 TYPE CONSTRUCTOR(CONT…)
 Functions: the TE of a function has the form

D -> R where:
D is the type expression of the parameters and
 R is the TE of the returned value.
For example: int* f(char a, char b)
 char X char → Pointer( Integer ).

20
TE: DAG REPRESENTATION
 A convenient way to represent a type expression is to use a
graph (tree or DAG).
 For example, the type expression corresponding to the
above function declaration is shown below:

21
ERRORS

 Errors: At the very least, the compiler must report

the nature and location of errors.
 Error Recovery: It is also desirable that the type
checker recovers from errors and continues
parsing the rest of the input.

22
 SPECIFICATION OF A SIMPLE TYPE CHECKER
Declarations
 The purpose of the semantic actions is to determine the type

expression of a variable and add the type expression in the

symbol table.

23
SPECIFICATION OF A SIMPLE TYPE CHECKER(CONT…)
 The transition scheme of expressions

24
SPECIFICATION OF A SIMPLE TYPE CHECKER(CONT…)
 The transition scheme of statement

25
 EQUIVALENCE OF TYPES
 So far we compared the type expressions using the equal
operators. However, such an operator is not defined except
perhaps between basic types.
 In fact we should rather use the equivalent operator which is

more appropriate.
 A natural notion of equivalence is structural equivalence:

 two type expressions are structurally equivalent if and only

if they are the same basic type or are formed by applying
the same constructor to structurally equivalent types.
 For example,

 integer is equivalent only to integer

 pointer (integer) is structurally equivalent to pointer
(integer)
26
EQUIVALENCE OF TYPES(CONT…)
 In some languages, types may be given names. For example in
Pascal we can define:
 Type:

 Ptr = ^Integer;
 Var

 A : Ptr;
 B : Ptr;
 C : ^Integer;
 D, E : ^Integer;
 Have the variables A, B, C, D, E the same type? Surprisingly,

the answer varies from implementation to implementation.

27
 EQUIVALENCE OF TYPES(CONT…)
 When names are allowed in type expressions, a new notion of
equivalence is introduced: Name equivalence.
 We have name equivalence between two type expressions if

and only if they are identical.

 Under structural equivalence, names are replaced by type

expressions they define,

 so two types are structurally equivalent if they represent
two structurally equivalent type expressions when all
names have been substituted.
 For example, ptr and pointer (integer) are not name
equivalent but they are structurally equivalent.
 N.B Confusion arises from the fact that many
implementations associate an implicit type name with each
declared identifier. 28
 Thus, C and D of the above example may not be name
equivalent.
 TYPE CONVERSATION
Consider expressions like R + I, where R is of type real and I
of type integer.
 Of course, the machine cannot execute this operation as it
involves different types of values.
 However, most languages accept such expressions to be
used; the compiler will be in charge of converting one of
the operand into the type of the other.
 The type checker can be used to insert these conversion

operations into the intermediate representation of the source

program.
 For example, an operator int to real may be inserted
whenever an operand needs to be implicitly converted.

29
TYPE CONVERSIONS(CONT…)
 Typeconversions may be implicit or explicit
 Explicit – done by the programmer .
For example,

float pi = 3.14;
int x = (int)pi;
Implicit – done by the compiler.
 For example,

int x = 10;
float y = x

30