Type Expression in Compiler Design | Equivalence of Type Expressions
Equivalence of Type Expressions
- If two type expressions are equal then return a certain type else return type_error.
- Key Ideas:
- The main difficulty arises from the fact that most modern languages allow the naming of user-defined types.
- For instance, in C and C++ this is achieved by the typedef statement.
- When checking equivalence of named types, we have two possibilities.
- Structural Equivalence
- Names Equivalence
Structural Equivalence of Type Expressions
- Type expressions are built from basic types and constructors, a natural concept of equivalence between two type expressions is structural equivalence. i.e., two expressions are either the same basic type or formed by applying the same constructor to structurally equivalent types. That is, two type expressions are structurally equivalent if and only if they are identical.
- For example, the type expression integer is equivalent only to integer because they are the same basic type.
- Similarly, pointer (integer) is equivalent only to pointer (integer) because the two are formed by applying the same constructor pointer to equivalent types.
- The algorithm recursively compares the structure of type expressions without checking for cycles so it can be applied to a tree representation. It assumes that the only type constructors are for arrays , products, pointers, and functions.
- The constructed type array(n1 , t1) and array(n2 , t2) are equivalent if n1 = n2 and t1 =t2
Equivalance of Type Expression
Algorithm
sequiv(s,t)
if (s and t are same basic type) then
return true
else if ( s = array(s1 , s2) and t = array(t1 , t2)) then
return (sequiv(s1 ,t1) and sequiv(s2 ,t2))
else if ( s = s1 x s2 and t = t1 x t2 ) then
return (sequiv(s1,t1) and sequiv(s2,t2))
else if ( s = pointer (s1) and t= pointer (t1) then
return (sequiv(s1 ,t1))
else if ( s = s1<s2 and t = t1<t2 ) then
return (sequiv(s1 ,t1) and sequiv(s2,t2))
else return false
Names for Type Expressions
- In some languages, types can be given names (Data type name). For example, in the Pascal program fragment.
Type Checking
- The identifier link is declared to be a name for the type cell. The variables next, last, p, q, r are not identical type, because the type depends on the implementation.
- Type graph is constructed to check the name equivalence.
- Every time a type constructor or basic type is seen, a new node is created.
- Every time a new type name is seen, a leaf is created.
- Two type expressions are equivalent if they are represented by the same node in the type graph.
Example: Consider Pascal program fragment
Names Equivalence
- The identifier link is declared to be a name for the type ‡cell. new type names np and nqr have been introduced.
- since next and last are declared with the same type name, they are treated as having equivalent types. Similarly, q and r are treated as having equivalent types because the same implicit type name is associated with them.
- However, p, q, and next do not have equivalent types, since they all have types with different names.
Pascal Program-Fragment
Note that type name cel1 has three parents. All labeled pointer. An equal sign appears between the type name link and the node in the type graph to which it refers.