Any program in any language must manipulate objects to perform its various tasks. These objects are characterized by their structure, which is mapped to the programmer level as data types.
Data types may be explicit, as in the C/C++ family of languages, or they may be inferred from the primitive objects and the operations they are subject to (e.g. CAML).
Type checking is the process of verifying whether the types used in the various language constructs are appropriate. It can be performed at compile type (static type checking) or at run time.
The type checking discussed here is the static approach, i.e., checking whether the types used for objects and the operations that manipulate them at compile time are consistent.
In the approach followed by CDK-based compilers, code generation is carried out by visitors that are responsible for traversing the abstract syntax tree and generate, evaluating each node. Node evaluation may depend on the specificities of the data types being manipulated, the simplest of which is the data type's size, important in all memory-related operations.
The package provided here contains the Compact compiler for CDK3.
Note that, even though it does not work (or even compile) with CDK4 and newer, the principles are the same.
This version has been improved to perform type checking in the C generator visitor. This visitor uses a second visitor to check types before deciding on which code to generate. The checks are related with the use of boolean expressions in tests (while, if, and if-else nodes) and with type consistency in operators (in this case, although we could have decided otherwise, operators such as + and - must have arguments of the same type and this type must be integer). In addition, the compiler now checks if a variable has the proper type in certain cases (for instance, in the tests mentioned above).
The visitor approach to type checking is justified by the independence of code generation from the details of type checking. In addition, the same type validator may be shared by several visitors performing code generation. In our example, the only changes to the original Compact are located in Cwriter.cpp (in each node we wish to check). The validation code is self-contained and is integrated as the drop-in class TypeValidator (TypeValidator.h and TypeValidator.cpp).
Example 1 from Compact: the original Compact compiler would accept the code, but the new one does not: since x is an integer and conditions must be boolean, it is rejected as a condition for if. <text> program x = 0; if (x) print x; while (x < 30) {
print x; x = x + 1;
} end </text>
Also, notice that type checking is only active for the C target code generator (as intended). The procedure for including the validator calls in the other targets is similar.
The following example considers a simple grammar and performs the whole of the semantic analysis process and, finally, generates the corresponding C code. The semantic analysis process must account for variables (they must be declared before they can be used) and for their types (all types must be used correctly).
The following example presents an old version of the Compact compiler. This case is no longer relevant, but shows how an existing compiler can be extended.
The following example considers an evolution of Compact, called Simple. Where Compact forces some verification via syntactic analysis (thus, presenting low flexibility), Simple has a richer grammar and, consequently, admits constructions that may not be correct in what concerns types of operators, functions, and their arguments. Type checking in this case is built-in, since, without it, it would be impossible to guarantee the correctness of any expression.