Type Checking

Lexing and parsing will reject many texts as not being correct programs. However, many languages have well-formedness requirements that can not be handled exclusively by the techniques seen so far. These requirements can, for example, be static type correctness, or a requirement that pattern-matching or case-statements are exhaustive. These properties are most often not context-free, i.e., they can not be checked by membership of a context-free language. Consequently, they are checked by a phase that conceptually comes after syntax analysis (though it may be interleaved with it). These checks may happen in a phase that does nothing else, or they may be combined with the actual execution or translation to another language. Often, translation to another language (such as machine language) may exploit or depend on type information, which makes it natural to combine calculation of types with the actual translation or to pass type information from a type-check phase to the translation phase. In Chap. 4, we covered type-checking during execution, which is normally called dynamic typing. We will in this chapter assume that type checking and related checks are done in a phase previous to execution or translation (i.e., static typing), and similarly assume that any information gathered by this phase is available in subsequent phases.