PL0 Compiler - Type Checking

if x < 0 then z := -x else z := x

Suppose we required the above code to by syntactically correct - what are our requirements?
- The condition x < 0 should be type Boolean
- The statement z := -x is type correct.
- The statement z := x is type correct.
For the statement z := -x to be type correct, the variable z must be a reference type (must have an allocated spot in memory)
- We need a variable to have a memory address for it to be assigned to a new value.
- The expression -x must evaluate to an expression which is type compatible with the type of z
As we perform type-checking, we update the our abstract syntax tree and separately our symbol table with type information
- For example, to resolve the expression x < 0 we will need to resolve the type of IDENTIFIER(”x”)
- Therefore, in the type checking phase we update the abstract syntax tree with type information
- To resolve the expression z := x we may need to perform some coercions

Type Checking the AST

The IdentifierNode is only used during the parsing phase to represent a reference to either a symbolic constant or a variable.

As part of the static semantics (type checking) phase, it will be transformed to either a ConstNode or VariableNode

ExpNode(Location loc, Type t) with subclasses
    ConstNode(int value)
    IdentifierNode(String id)
    VariableNode(SymEntry.VarEntry entry)

Coercions

A number of other node types are only introduced in the static semantics phase:
- A DereferenceNode represents a dereference of a variable address (left value) to access its (right) value
- NarrowSubrangeNode An expression of a type, T, can be narrowed to a subrange of T (for the purpose of coercing a larger subrange into a smaller subrange)
- WidenSubrangeNode An expression of a subrange type can be widened to the base type of the subrange
```
ExpNode(Location loc, Type t) with subclasses
    DereferenceNode(ExpNode leftVaue)
    NarrowSubrangeNode(ExpNode e)
    WidenSubrangeNode(ExpNode e)
```

Type Checking the AST

In this example, we are type checking the abstract syntax tree for the following PL0 code
```
if x < 0 then z := -x else z := x
```

Untitled

We first evaluate the expression x < 0 - we need to determine whether the expression has a Boolean value.
- We’re essentially checking the BinaryNode and its children nodes (as indicated by the orange box)
- We notice that the BinaryNode specifies the use of LESS_OP which is the less than operator.
  - The less than operator takes two integers and returns a Boolean value, i.e.
    $\text{LESS\_OP}:(\text{int}\times\text{int})\rightarrow\text{bool}$
- We need to check that both the Identifier “x” and the Constant 0 are both integers, or coerce them into Integers if they are not.
  - We resolve the type of the identifier “x” by looking it up in our symbol table.
  - By looking up the type of the identifier “x” we may see that its type is ref(int) (that is, a reference to an integer)
  - We need to dereference the identifier “x” - so we’re actually performing the LESS_OP operation on the dereferenced (reference to) an integer and a constant integer.
- Therefore, the statement is type correct for its usage within this specific conditional statement.
- After type checking the expression x < 0 our symbol table looks like this:
We then evaluate the expression z := -x to check whether it’s well formed.
- The AssignmentNode has a left value of IdentifierNode(”z”) and we need to resolve the identifier node’s reference just as we did for IdentifierNode(”x”) in the step above.
- By looking up the type of Identifier(”z”) in our symbol table, we may discover that it has type ref(int)
- We now want to check the right child of the AssignmentNode to see whether it is an expression that evaluates to be the same type - the expression is the minus operator (MINUS_OP) being applied to the identifier “x”
  - The MINUS_OP takes an integer and returns an integer ( $\text{MINUS\_OP}:\text{int}\rightarrow\text{int}$
  - Therefore, this expression should be well typed as long as the input value we’re passing it is an integer.
  - We’ve already looked up IDENTIFIER(”x”) before and we know it’s an integer variable.
  - It’s not exactly an integer, so we have to coerce it into an integer (this is done by dereferencing the integer).
Likewise, we check the other assignment.

Example Summary

Lexical Analysis of the sequence of program characters produced a sequence of lexical tokens
Syntax Analysis of the sequence of lexical tokens was used to produced
- A concrete syntax tree (not actually produced by the compiler)
- An abstract syntax tree (AST)
Static Analysis was used to:
- Resolve references to identifiers;
- Type check the abstract syntax tree
- Update the Abstract Syntax Tree with type coercions