Project, Phase 4: Type Checking

• Assigned: Monday, 7 November 2011
• Due: Wednesday, 23 November 2011

One important phase of semantic analysis is type checking. In particular, most programmers find it useful if the compiler identifies locations in which they are using types in what seems to be an inappropriate way.

In this phase of the project, you will build a type checker for Pascal. You already have much of the infrastructure necessary to do type checking. Your parser (phase 2) builds an attributed parse tree, so you can add rules for processing types in the tree (and storing types in certain locations). Your symbol table (phase 3) provides a mechanism for you to store information about various named types.

As you may have noted, there are a few primary that you will need to pay attention to when type checking.

• When a type is defined, you will need to store information about that type in the symbol table. The type name will serve as the key; a structure that represents the type will serve as the attribute.
  • If the type happens to be an enumerated type, you should also store its values in the symbol table.
• When a variable, function, or procedure is declared, you will need to store information about its type in the symbol table.
• When a variable is used, you will need to make sure that its use is compatible with the type information you have about it.
• When expressions are used in the program, you will need to assign a type to the expression. This type will probably be an attribute.

We will use a conservative type equivalence metric. In most cases, if two things have different types, they cannot be used in place of each other.

There is one exception: integer expressions can be used when the expected type is a subrange of the integers. For example, if we declare

type:
  Indices = 1..100;
  Stuff = array[Indices] of real;
var:
  i: integer;
  s: Stuff;

then it is safe to write

  s[i] = 3.0;
  s[i+1] = 2.3;

If you want to make your compiler more useful, you could add additional exceptions to the conservative type metric.

• If one type is an alias of another, values of one type can be used in locations in which the other is expected.
• Symbolic constants can be assigned to subranges, too.
• If one type is a subrange of another, values of the subrange type can be used in places in which the supertype is permitted. E.g., if x has type 1..10, x can be used wherever an integer is expected.
• Normal arithmetic coercion is used.

Because enumerated types can add significant complications, particularly when combined with subranges, you need not support enumerated types.

To further simplify this project, you need not support records. You also need not support sets or arrays of more than one dimension.

What's left? Still a lot: Some basic types, type aliases, subranges of integers, one-dimensional arrays, pointer types, and file types.

Here are some additional things to think about

• You should provide a way to represent types. You should be sure to handle the following issues:
  • Basic types
  • Records
  • Arrays
  • Type aliases
  • Subrange types for integers
  • Functions and procedures (which are effectively types)
• For array references, the index will be an expression, and you'll need to verify that the type of that expression matches the type of the index.
• For procedures and functions, you will need to distinguish between variable parameters and value parameters.
• You should find that dealing with arrays and dealing with functions are similar tasks.
• If you choose to implement records, you'll need to check that field names are valid. For example, if you see foo.bar, you will not only check that foo's type is a record and that the record has a field named bar, but also identify the type of bar and assign it to the expression.