#### EQUIVALENCE OF EXPRESSIONS IN TYPE CHECKING

Type checker find whether two type expressions are equivalent or not.

This type equivalence is of two categories:

- Structural equivalence
- Name equivalence.

#### 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.**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.