Type analysis is the process of associating a type with every construct that yields a value. That information is necessary to report violations of context conditions imposed by the language definition. It is also needed to select appropriate target code when a program is being translated.
We often find similar concepts in languages other than programming languages, and therefore need to carry out a type analysis task when implementing those languages.
The modules of this library represent each type by a distinct
This definition table key can have properties that further characterize
NoKey is used to represent an unknown or non-existent type.
DefTableKey-valued attributes named
Type are associated with
grammar symbols to carry the type of a program construct.
This strategy supports analysis of languages that have a wide range of
features, but provides simple solutions for simple cases.
This document explains how to carry out type analysis for a number of language features. The features are discussed in order of increasing complexity:
Moving from one feature to the next may require additional specifications, but existing solutions need not be changed. Thus an incremental development strategy can be followed, in which components of the type analysis problem are solved independently. It is also not necessary to understand more complex features when solving a specific analysis problem.
The examples in this document are based on a simple language called Mystery (see Overview). Mystery was designed to demonstrate key concepts in programming languages, while minimizing complexity. Its syntax is based on that of Modula-3, but the intent of a Mystery program should be clear to anyone familiar with common programming languages.
Our strategy with respect to examples is to provide only the specification fragments needed to illustrate the relevant principles. In most cases, these fragments will be LIDO rules. We expect that the meaning of the abstract syntax for these rules will be obvious, although we will sometimes show snippets of Mystery code to make the application clearer.