Equivalence of expression in type checking

RGPV: Compiler Design: Unit 3

EQUIVALENCE OF EXPRESSIONS IN TYPE CHECKING

 

The job of type checker is to find whether two type expressions are equivalent or not. This type equivalence is of two categories:-Name equivalence or Structural equivalence.

In type checking if two type expressions are equal then return a certain type else return type-error.

#Structural equivalence :

Replace the named types by their definitions and recursively check the substituted                     trees.  If type expressions are built from basic types and constructors then those expressions             are called structurally equivalent.

For instance, to check whether the constructed types array(n1,T1) and array(n2,T2) are equivalent

we can check that the integer values n1 and n2 are equal and recursively check that T1 and T2 are equivalent,

or we can be less restrictive and check only that T1 and T2 are equivalent.

Example :

S1

S2

Equivalence

Reason

Char

Char

S1 equivalent to S2

Similar basic types

Pointer(char)

Pointer(char)

S1 equivalent to S2

Similar constructor ptr to the char type

 

#Name equivalence :

Two type expressions are name equivalent if and only if they are identical, that is if they can be represented by the same syntax tree, with the same labels.

Example :

typedef struct Node

{

    Int x;

}  node;

Node *first,*second;

Struct Node *last1,*last2;

 

The variables first and second are name equivalent similarly last1 and last2 are name       equivalent.

 

BY:

ROMA CHANDANI

TSEC BURHANPUR

COMING SOON...

Related topics

Professor Jayesh video tutorial

Please use contact page in this website if you find anything incorrect or you want to share more information about the topic discussed above.