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

Equivalance of Type Expression


    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 Expressions

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

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

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.

Related Searches to Type Expression in Compiler Design