|
TypeChecker
An explanation of the Kitsch type checker.
IntroductionThe end user never directly invokes the TypeChecker, but both the Compiler and Interpreter rely on it to do static type checking. Type Checker DesignThe TypeChecker source is available here. The design follows the standard Visitor pattern; pj2, which generates the parser for the language, is also kind enough to generate tree node classes and implement a visit() method for each of them. The type checker works by visiting tree nodes in a postfix fashion. All leaves should have a definite type; literals are obvious, and the type of identifiers is recorded in a miniature symbol table. Variable types are inferred based on the expressions they are set to. These types bubble upwards, with operators and statements making sure they have valid types. The parse tree is annotated with the type of each node so that the compiler/interpreter can easily check what type a particular node is. If a type conflict occurs, the type checker outputs an error and sets an internal error flag. It continues to try to check the rest of the tree for errors. This may result in some redundant error messages within a complex expression - but at least the user can see multiple typing errors from different areas of the code at once rather than having to fix one error and recompile each time. Type inference for recursive functions proved quite challenging. In the interests of simplicity, a return type is required for functions. |