Introduction: Many type-checking rules have the form, "if two type expressions are equal t h e n return a certain type else error." Potential ambiguities arise when names are given to type expressions and the names are then used in subsequent type expressions. The key issue is whether a name in a type expression stands for itself or whether it is an abbreviation for another type expression.

Since type names denote type expressions, they can set up implicit cycles; see the box on "Type Names and Recursive Types." If edges to type names are redirected to the type expressions denoted by the names, then the resulting graph can have cycles due to recursive types.

When type expressions are represented by graphs, two types are structurally equivalent if and only if one of the following conditions is true:

• They are the same basic type.
• They are formed by applying the same constructor to structurally equivalent types.
• One is a type name that denotes the other.

If type names are treated as standing for themselves, then the first two conditions in the above definition lead to name equivalence of type expressions.

Name-equivalent expressions are assigned the same value number; Structural equivalence can be tested using the unification algorithm.

Declarations: We shall study types and declarations using a simplified grammar that declares just one name at a time; declarations with lists of names can be handled as discussed in Example 5.10. The grammar is

D               T id ; D | e

T       ->     B C | record ' { ' D '}'

B       ->     int | float

C                e| [num] C

The fragment of the above grammar that deals with basic and array types was used to illustrate inherited attributes in Section 5.3.2. The difference in this section is that we consider storage layout as well as types. Nonterminal D generates a sequence of declarations. Nonterminal T generates basic, array, or record types. Nonterminal B generates one of the basic types int and float. Nonterminal C, for "component," generates strings of zero or more integers, each integer surrounded by brackets. An array type consists of a basic type specified by B, followed by array components specified by nonterminal C. A record type (the second production for T) is a sequence of declarations for the fields of the record, all surrounded by curly braces.

Previous Next