Project 4

Deadline	Tuesday, November 28, 11:59pm
Name on Marmoset	P4
To Submit	Standard Format: `wlp4type.cc` OR `wlp4type.rkt` Prescanned Format: `wlp4type-prescanned.cc` OR `wlp4type-prescanned.rkt` Preparsed Format: `wlp4type-preparsed.cc` OR `wlp4type-preparsed.rkt`
Marking Scheme	50 marks for release tests, 50 marks for secret tests

WLP4 Semantic Analyzer

In this project, you will implement the semantic analysis (also known as context-sensitive analysis) phase of compilation for the WLP4 programming language. The goal is to take the output of the WLP4 parser (Project 3), which is a parse tree for the input WLP4 program, and perform the following tasks:

Check for compile-time errors in the program that are not detected by the scanning and parsing phases, particularly errors related to names and types;
Annotate the parse tree with information about types of expressions, which will be used in the next phase, code generation.

Input and Output Requirements

There are three input formats. Which ones you can use depends on which previous projects you have completed.

Standard Format: Plain WLP4 source code.
Prescanned Format: The result of running a Standard Format input through wlp4scan, which is a sequence of tokens for the WLP4 program.
Preparsed Format: The result of running a Standard Format input through wlp4scan and then through wlp4parse, which is a text representation of the WLP4 program's parse tree. This format is also known as a WLP4 Intermediate (.wlp4i) file.

The semantic analysis phase requires examining a parse tree that represents the input WLP4 program.

If using Standard Format, you will need to scan the input yourself using your solution to Project 1B, then parse the scanned input using your solution to to Project 3, resulting in a parse tree.
If using Prescanned Format, you will need to read in the sequence of tokens from standard input, then parse the tokens using your solution to to Project 3, resulting in a parse tree. This option allows you to use your P3 parser code even if you didn't complete P1B (or aren't happy with your P1B solution).
If using Preparsed Format, you will need to read the representation of the parse tree from standard input and reconstruct the tree. The algorithm for reconstructing the tree is similar to the tree-building algorithm given in Question 10, with slight differences due to the fact that the information stored at each tree node is different, and Preparsed Format includes lines corresponding to tokens.

Reconstructing the Tree (from Preparsed Format)

Instead of a single field for the data stored at the root node, as in Question 10, you should have four string fields:

A field rule, which is only used in nonterminal nodes, and stores the CFG rule used to expand the node.
A field lhs, which is only used in nonterminal nodes, and stores the left-hand side of the CFG rule.
Two fields kind and lexeme, which are only used in terminal nodes, and store the kind and lexeme of the token, respectively.

This is just a very basic tree structure that gives you what you need to get started with the project. You are free modify this algorithm and your tree structure to to do extra processing and store additional useful information in the tree.

Read one line from standard input. This line represents the production rule used to expand the root of the tree.
Store the entire line in the rule field.
Read and consume the left-hand side of the rule, and store this in the lhs field.
Loop over the symbols on the right-hand side of the rule, and add one child to the root for each symbol. Determine whether the symbol is a terminal or nonterminal. In the WLP4 grammar, terminals are in ALL CAPS, and nonterminals are in lowercase, so you can just check whether the first character of the symbol is uppercase or lowercase to determine this.
- If the symbol is a terminal, the child should be a leaf node storing the terminal. Read the next line of standard input, which is guaranteed to represent a terminal token if you have implemented the rest of the algorithm correctly. Create a leaf node and store the kind of the token in the leaf node's kind field, and the lexeme in the leaf node's lexeme field. The leaf node should be created directly rather than through a recursive call.
- If the symbol is a nonterminal, construct the child by recursively calling this algorithm.

Don't forget: If the right-hand side of the rule is the special string .EMPTY, then there is nothing (no symbols) on the right-hand side, and you should not create any children in Step 4. Attempting to create a child in the .EMPTY case will result in an incorrect tree.

For this project, no output is required unless an error is detected.

This means all your program needs to do is determine if the program contains one of the semantic errors mentioned in the WLP4 Specification under the Context-Sensitive Syntax section. If so, print an error message containing ERROR in ALL CAPS to standard error and exit.

Detecting these errors is a complicated process, which is discussed in detail in the lectures, the course notes, and the stepping stones below.

Annotating the Parse Tree?

Earlier, we said that in addition to error checking, you need to annotate the parse tree with types of expressions, and these annotations will be used in the code generation phase (the next project). You are not required to output any representation of these type annotations, which means this annotation process is technically not required to pass the Marmoset tests. However, to correctly detect errors, you will need infrastructure to compute the types corresponding to certain subtrees of the parse tree, and once you have this infrastructure, annotating the tree is only slightly more work.

The reference implementation wlp4type does output a representation of the parse tree with type annotations (WLP4 Typed Intermediate (.wlp4ti) format). Even if you do not complete this project, you will be able to do the code generation project by reading and reconstructing the type-annotated tree.

Reference Implementation

Since output is not required for this project, only error checking, the purpose of the reference implementation is just to check whether an error should be produced for a given input or not.

The reference implementation tries to give informative error messages. Your error messages do not need to be informative and do not need to match the ones produced by the reference implementation. However, making your error messages informative will help significantly with debugging, since you will be able to tell whether your code is producing an error for the correct reason, or if it is doing something unexpected.

Checking for Errors: Standard Format

If using Standard Format input, you can pass the input to the wlp4c course tool, which will attempt to compile the program into MIPS machine code.

wlp4c < program.wlp4 > /dev/null

Sending the result to /dev/null means that the output (MIPS machine code) will be ignored, but error messages will not. If the input program contains an error, you will see an error message.

Note that wlp4c will produce error messages for all phases of compilation, including scanning and parsing. You can confirm your input program does not have an error related to scanning or parsing using the following command line:

wlp4scan < program.wlp4 | wlp4parse > /dev/null

If the above command does not produce an error, this confirms the program is free of scanning and parsing errors.

Checking for Errors: Prescanned or Preparsed Format

If using Preparsed Format input, you can feed the input to the wlp4type course tool to check if it contains semantic errors.

wlp4type < program.preparsed

Note that if there are no errors, the wlp4type tool will produce an WLP4 Typed Intermediate (.wlp4ti) file representing a version of the parse tree that is annotated with type information. Your program is not required to produce output like this, but this output may be useful for understanding the requirements of WLP4 type computations.

Preparsed Input can be generated from Standard Format input (a plain WLP4 program) using the following command line:

wlp4scan < program.wlp4 | wlp4parse > program.preparsed

Or from Prescanned Input using the following command line:

wlp4parse < program.prescanned > program.preparsed

Examples

To complete this project, you will need to become familiar with the structure of a WLP4 parse tree. The cs241.treeprint tool may help with this.

Consider the following WLP4 program:

int wain(int a, int b) {
  return c;
}

This WLP4 program has a semantic error: The return expression is a variable c but this variable is not declared anywhere. Therefore, your program must print an error message containing ERROR to standard error when given this WLP4 program as input.

Detecting the Above Error

To understand how your program would detect this, it helps to look at the WLP4 program's parse tree. By running this program through wlp4scan, then through wlp4parse, then through cs241.treeprint with the --wlp4 option, we obtain the following output showing the structure of the tree.

wlp4scan < program.wlp4 | wlp4parse | cs241.treeprint --wlp4
start
├─BOF BOF
├─procedures
│ ╰─main
│   ├─INT int
│   ├─WAIN wain
│   ├─LPAREN (
│   ├─dcl
│   │ ├─type
│   │ │ ╰─INT int
│   │ ╰─ID a
│   ├─COMMA ,
│   ├─dcl
│   │ ├─type
│   │ │ ╰─INT int
│   │ ╰─ID b
│   ├─RPAREN )
│   ├─LBRACE {
│   ├─dcls
│   ├─statements
│   ├─RETURN return
│   ├─expr
│   │ ╰─term
│   │   ╰─factor
│   │     ╰─ID c
│   ├─SEMI ;
│   ╰─RBRACE }
╰─EOF EOF

Your program (the semantic analyzer) begins at the "start" node at the top of this tree. It descends into the "procedures" subtree.

There is only one procedure, the wain procedure which is represented by the "main" subtree. Upon encountering this procedure, your program can create a symbol table for wain to store information about the local variables of wain.

The "main" subtree has many children. Your program should look at the two "dcl" children:

dcl
├─type
│ ╰─INT int
╰─ID a

dcl
├─type
│ ╰─INT int
╰─ID b

By examining these subtrees, your program can determine that wain declares two parameter variables, both of type int, named a and b. Your program should store this information in the symbol table of wain for future reference.

Notice that the "dcls" child of "main" has no children. This subtree is normally where non-parameter local variable declarations would appear, but there are none in this WLP4 program.

The "statements" child of "main" also has no children. There are no statements the body of wain in this WLP4 program.

The "expr" child of "main", which represents the return expression of wain, is the following tree:

expr
╰─term
  ╰─factor
    ╰─ID c

Your program should now descend into the "expr" subtree to determine the type of the expression. All WLP4 procedures must return an int value, so if the type of the return expression is not int, this is a semantic error.

When the program reaches the bottom of the "expr" subtree, the node "ID c" (corresponding to a token with kind "ID" and lexeme "c"), it looks up "c" in the symbol table for wain to determine the type of the variable. However, no variable named c is declared in wain. The program reports a semantic error (something like "variable c used in wain without being declared") and exits.

Here is a more complicated example:

int p(int b) {
  int c = 241;
  return b - c;
}
int wain(int *a, int b) {
  println(p(b));
  return a + b;
}

In this case, the semantic error is that the return expression of wain, a + b, is of type int* and WLP4 procedures must return an int value.

Detecting the Above Error

Once again, we look at the parse tree.

wlp4scan < program.wlp4 | wlp4parse | cs241.treeprint --wlp4

The Parse Tree

start
├─BOF BOF
├─procedures
│ ├─procedure
│ │ ├─INT int
│ │ ├─ID p
│ │ ├─LPAREN (
│ │ ├─params
│ │ │ ╰─paramlist
│ │ │   ╰─dcl
│ │ │     ├─type
│ │ │     │ ╰─INT int
│ │ │     ╰─ID b
│ │ ├─RPAREN )
│ │ ├─LBRACE {
│ │ ├─dcls
│ │ │ ├─dcls
│ │ │ ├─dcl
│ │ │ │ ├─type
│ │ │ │ │ ╰─INT int
│ │ │ │ ╰─ID c
│ │ │ ├─BECOMES =
│ │ │ ├─NUM 241
│ │ │ ╰─SEMI ;
│ │ ├─statements
│ │ ├─RETURN return
│ │ ├─expr
│ │ │ ├─expr
│ │ │ │ ╰─term
│ │ │ │   ╰─factor
│ │ │ │     ╰─ID b
│ │ │ ├─MINUS -
│ │ │ ╰─term
│ │ │   ╰─factor
│ │ │     ╰─ID c
│ │ ├─SEMI ;
│ │ ╰─RBRACE }
│ ╰─procedures
│   ╰─main
│     ├─INT int
│     ├─WAIN wain
│     ├─LPAREN (
│     ├─dcl
│     │ ├─type
│     │ │ ├─INT int
│     │ │ ╰─STAR *
│     │ ╰─ID a
│     ├─COMMA ,
│     ├─dcl
│     │ ├─type
│     │ │ ╰─INT int
│     │ ╰─ID b
│     ├─RPAREN )
│     ├─LBRACE {
│     ├─dcls
│     ├─statements
│     │ ├─statements
│     │ ╰─statement
│     │   ├─PRINTLN println
│     │   ├─LPAREN (
│     │   ├─expr
│     │   │ ╰─term
│     │   │   ╰─factor
│     │   │     ├─ID p
│     │   │     ├─LPAREN (
│     │   │     ├─arglist
│     │   │     │ ╰─expr
│     │   │     │   ╰─term
│     │   │     │     ╰─factor
│     │   │     │       ╰─ID b
│     │   │     ╰─RPAREN )
│     │   ├─RPAREN )
│     │   ╰─SEMI ;
│     ├─RETURN return
│     ├─expr
│     │ ├─expr
│     │ │ ╰─term
│     │ │   ╰─factor
│     │ │     ╰─ID a
│     │ ├─PLUS +
│     │ ╰─term
│     │   ╰─factor
│     │     ╰─ID b
│     ├─SEMI ;
│     ╰─RBRACE }
╰─EOF EOF

The tree is large this time, so let's break it down. The tree contains two procedures called p and wain.

start
├─BOF BOF
├─procedures
│ ├─procedure
│ │ ├─INT int
│ │ ├─ID p
│ │ ... ... ...
│ ╰─procedures
│   ╰─main
│     ├─INT int
│     ├─WAIN wain
│     ... ... ...
╰─EOF EOF

By traversing the procedures subtree, you can process these procedures in order.

The procedure p

procedure
├─INT int
├─ID p
├─LPAREN (
├─params
│ ╰─paramlist
│   ╰─dcl
│     ├─type
│     │ ╰─INT int
│     ╰─ID b
├─RPAREN )
├─LBRACE {
├─dcls
│ ├─dcls
│ ├─dcl
│ │ ├─type
│ │ │ ╰─INT int
│ │ ╰─ID c
│ ├─BECOMES =
│ ├─NUM 241
│ ╰─SEMI ;
├─statements
├─RETURN return
├─expr
│ ├─expr
│ │ ╰─term
│ │   ╰─factor
│ │     ╰─ID b
│ ├─MINUS -
│ ╰─term
│   ╰─factor
│     ╰─ID c
├─SEMI ;
╰─RBRACE }

We create a symbol table for the procedure p.

By traversing the "params" subtree, we find that there is one parameter variable called b with type int, and we add this variable to the symbol table for p.

We also take note of the procedure's signature: it expects exactly one parameter, which must be type int. We can use this information to verify later whether the procedure is being called correctly.

The "dcls" subtree has children, meaning that this procedure contains non-parameter local variable declarations. Traversing the subtree, we find a declaration of an int variable called c. We also observe that this variable is initialized to a NUM, which is okay because it has int type. If this variable was initialized to the pointer constant NULL, this would be a type error.

The "statements" subtree is empty. This procedure has no statements in the body.

The "expr" subtree looks as follows:

expr
├─expr
│ ╰─term
│   ╰─factor
│     ╰─ID b
├─MINUS -
╰─term
  ╰─factor
    ╰─ID c

We now try to compute the type of this expression to ensure it is int, since WLP4 procedures must return an int value. We annotate the tree with type information, working from the leaves to the root.

First, for this subtree:

expr
╰─term
  ╰─factor
    ╰─ID b

The ID "b" has type int as determined earlier. According to the type rules in the WLP4 Specification:

The type of the "factor" node is the same as the type of the "ID" child.
The type of the "term" node is the same as the type of the "factor" child.
The type of the "expr" node is the same as the type of the "term" child.

Therefore, we can annotate the subtree with types as follows:

expr : int
╰─term : int 
  ╰─factor : int
    ╰─ID b : int

The other operand of the MINUS is represented by this subtree:

term
╰─factor
  ╰─ID c

Through the same process, we annotate it:

term : int
╰─factor : int
  ╰─ID c : int

Looking back at the full "expr" subtree, we have the following annotations:

expr
├─expr : int
│ ╰─term : int
│   ╰─factor : int
│     ╰─ID b :int
├─MINUS -
╰─term : int 
  ╰─factor : int
    ╰─ID c : int

Since this subtree represents the subtraction of two int variables, the resulting type is int, so we can annotate the root of the full "expr" subtree as well:

expr : int
├─expr : int
│ ╰─term : int
│   ╰─factor : int
│     ╰─ID b :int
├─MINUS -
╰─term : int 
  ╰─factor : int
    ╰─ID c : int

We have now confirmed that the return expression has type int as required, so we are done processing the procedure p and did not encounter any semantic errors. We move on to the next procedure, wain.

The wain procedure

main
├─INT int
├─WAIN wain
├─LPAREN (
├─dcl
│ ├─type
│ │ ├─INT int
│ │ ╰─STAR *
│ ╰─ID a
├─COMMA ,
├─dcl
│ ├─type
│ │ ╰─INT int
│ ╰─ID b
├─RPAREN )
├─LBRACE {
├─dcls
├─statements
│ ├─statements
│ ╰─statement
│   ├─PRINTLN println
│   ├─LPAREN (
│   ├─expr
│   │ ╰─term
│   │   ╰─factor
│   │     ├─ID p
│   │     ├─LPAREN (
│   │     ├─arglist
│   │     │ ╰─expr
│   │     │   ╰─term
│   │     │     ╰─factor
│   │     │       ╰─ID b
│   │     ╰─RPAREN )
│   ├─RPAREN )
│   ╰─SEMI ;
├─RETURN return
├─expr
│ ├─expr
│ │ ╰─term
│ │   ╰─factor
│ │     ╰─ID a
│ ├─PLUS +
│ ╰─term
│   ╰─factor
│     ╰─ID b
├─SEMI ;
╰─RBRACE }

As before, we create a symbol table for wain and add the two parameters. This time, a has type int* and b has type int. It is not an issue that the variable name b was already used in procedure p, because p and wain have separate symbol tables.

The "dcls" subtree has no children this time, but the "statements" subtree has children. There is a println statement in the wain procedure.

statements
├─statements
╰─statement
  ├─PRINTLN println
  ├─LPAREN (
  ├─expr
  │ ╰─term
  │   ╰─factor
  │     ├─ID p
  │     ├─LPAREN (
  │     ├─arglist
  │     │ ╰─expr
  │     │   ╰─term
  │     │     ╰─factor
  │     │       ╰─ID b
  │     ╰─RPAREN )
  ├─RPAREN )
  ╰─SEMI ;

In general, the "statements" subtree might contain a sequence of statements and you have to go through each individual statement and perform type checking. In this case, there is just one statement.

statement
├─PRINTLN println
├─LPAREN (
├─expr
│ ╰─term
│   ╰─factor
│     ├─ID p
│     ├─LPAREN (
│     ├─arglist
│     │ ╰─expr
│     │   ╰─term
│     │     ╰─factor
│     │       ╰─ID b
│     ╰─RPAREN )
├─RPAREN )
╰─SEMI ;

This tree has an "expr" subtree, the expression to be printed. According to the type rules in the WLP4 Specification, this expression must have type int.

We perform the type annotation process discussed earlier, working from the leaves to the root. By looking up b in the symbol table for wain, we find that the variable b has type int.

expr
╰─term
  ╰─factor
    ├─ID p
    ├─LPAREN (
    ├─arglist
    │ ╰─expr : int
    │   ╰─term : int 
    │     ╰─factor : int
    │       ╰─ID b : int 
    ╰─RPAREN )

Now, the variable b is used in a procedure call p(b). The return type of a procedure call is always int in WLP4. However, we need to ensure the number and types of arguments for the procedure are correct.

Earlier, we mentioned that we took note of the procedure p's signature, the expected sequence of argument types. By comparing the types of expressions in the "arglist" subtree to the procedure signature, we confirm that the procedure call matches the signature and there is no semantic error. We can conclude that the "factor" subtree representing the procedure call is valid and has type int. We can therefore conclude the entire "expr" tree has type int.

expr : int
╰─term : int 
  ╰─factor : int
    ├─ID p
    ├─LPAREN (
    ├─arglist
    │ ╰─expr : int
    │   ╰─term : int 
    │     ╰─factor : int
    │       ╰─ID b : int 
    ╰─RPAREN )

This means the println statement is valid and does not contain a semantic error. We are done checking statements and we move on to the return expression of wain.

expr
├─expr
│ ╰─term
│   ╰─factor
│     ╰─ID a
├─PLUS +
╰─term
  ╰─factor
    ╰─ID b

We proceed with the usual type annotation process, but note that a has type int*. This means a + b is a pointer arithmetic expression that resolves to type int*.

expr : int*
├─expr : int*
│ ╰─term : int*
│   ╰─factor : int*
│     ╰─ID a : int*
├─PLUS +
╰─term : int
  ╰─factor : int
    ╰─ID b : int

Since the return expression has type int*, and WLP4 procedures can only return int, we have discovered a semantic error. Produce an error message and stop.

Stepping Stones

Throughout the process of writing this program, it is important to be familiar with the structure of a WLP4 program's parse tree. Each node of the parse tree is either:

A nonterminal node corresponding to one of the context-free grammar rules in the Context-Free Syntax section of the WLP4 Specification. The children of the node correspond to the symbols on the right-hand side of the grammar rule. If the right-hand side is empty, there are no children.
A terminal node corresponding to one of the tokens in the Lexical Syntax section of the WLP4 Specification. The node has no children and stores the kind and lexeme of the token.

Even if you understand this concept, it might not be obvious how the rules and tokens fit together into a complete tree for the program. You can view the explicit parse tree for a program with the following command:

wlp4scan < program.wlp4 | wlp4parse | cs241.treeprint --wlp4

Or in terms of the web tools, use the WLP4 tools page to produce wlp4parse output, then give this output to cs241.treeprint with the "Input is in .wlp4i or .wlp4ti format" checkbox enabled.

The examples in the above section may also be helpful for understanding the tree.

Step 1: Parse Tree Setup

If you are using the Preparsed Format, you can use the tree data structure from Question 10 as a starting point, and follow the instructions in the "Reconstructing the Tree (from Preparsed Format)" section earlier on this page. In addition to the four string fields recommended there, you may want to add a field called rhs (right-hand side) which is a vector of strings. For nonterminal nodes, this vector should contain one element for each symbol on the right-hand side.

If you are using Standard or Prescanned Format input, you can reuse your tree data structure from Project 3. Ensure that you can easily access the following information:

For nonterminal nodes, a representation of the CFG rule used to expand the node. You should be able to check which rule it is, as well as examine the left-hand side and the symbols on the right-hand side individually.
For terminal nodes, the kind and lexeme of the token.

Wite a helper function called getChild for finding a child of a tree node that satisfies certain conditions. In C++, this should be a method of the parse tree struct or class. In Racket, it could be a function that takes a parse tree struct as its first parameter.

The function should take in a string and a positive integer n, and return the n-th child of the tree such that the rule LHS (for nonterminal nodes) or the token kind (for terminal nodes) matches the string. Return a null pointer (in C++) or false (in Racket) if no such child is found. For example:

If getChild("term", 1) is called for a nonterminal node corresponding to the rule expr → expr PLUS term, the function should return the third child of the node (corresponding to the term subtree).
If getChild("ID", 1) is called for a nonterminal node corresponding to the rule dcl → type ID, the function should return the second child of the node (corresponding to the ID subtree).
If getChild("expr", 2) is called for a nonterminal node corresponding to the rule test → expr EQ expr, the function should return the third child of the node (corresponding to the second expr subtree, the one to the right of the EQ).

This function only makes sense for nonterminal nodes, which store a CFG rule, and can be implemented by looping over the right-hand side of the rule to look for the desired symbol.

Most of the time, the integer argument will be 1, so it is convenient to make it an optional argument that defaults to 1. That is, getChild("...", 1) should be equivalent to getChild("...").

Step 2: Collecting Procedure & Variable Information

Create the following structs or classes to hold information about procedures and variables.

A Variable struct or class, which has a name field and a type field. It should have a constructor function which, given a tree whose root rule has dcl on the left-hand side, produces a Variable instance with the name and type filled in.
A VariableTable struct or class, which is a wrapper for a map of strings (variable names) to instances of the Variable struct/class. It should support the following operations:
- An Add operation which takes a Variable as an argument. It attempts to insert the Variable into the table; if a Variable with the same name is already in the table, it throws or produces a "duplicate variable declaration" error.
- A Get operation which takes a string as an argument. It looks up the string in the table and returns the Variable with that name, if it exists; if the string is not found, it throws or produces a "use of undeclared variable" error.
A Procedure struct or class, which has a name field, a signature field (vector or list of parameter types), and a local symbol table field which is an instance of the VariableTable struct/class. It should have a constructor function which, given a tree whose root rule has procedure or main on the left-hand side, produces a Procedure instance with the name, signature, and local symbol table filled in.
A ProcedureTable struct or class, which is a wrapper for a map of strings (procedure names) to instances of the Procedure struct/class. It should support the following operations:
- An Add operation which takes a Procedure as an argument. It attempts to insert the Procedureinto the table; if a Procedure with the same name is already in the table, it throws or produces a "duplicate procedure declaration" error.
- A Get operation which takes a string as an argument. It looks up the string in the table and returns the Procedure with that name, if it exists; if the string is not found, it throws or produces a "use of undeclared procedure" error.

Note that the constructor for Procedure will be complicated. You will need to understand the parse tree structure for procedures to implement this constructor. There are two slightly different structures depending on whether you are dealing with wain or another procedure.

There is more than one strategy for extracting the signature and filling out the local symbol table. You must explore the appropriate subtrees to find dcl nodes (which you can access with getChild, and pass to the Variable constructor). The parameters are in the params subtree for non-wain procedures; for wain, the two dcl children of the main node are the parameters. The non-parameter local variables are in the dcls subtree.

Store the parameter types in the signature, and store the Variable instances for all declarations (parameters and non-parameters) in the local symbol table using the Add operation. This can be done with simple loops within the constructor itself, or recursively by creating appropriate helper functions. If you take a recursive approach, we recommend you create separate helper functions for extracting the signature and filling out the local symbol table, instead of trying to combine these steps into one function.

Once these structs/classes are set up, write a function called collectProcedures which traverses the procedures subtree of the parse tree root and creates or fills out a ProcedureTable with all the procedures in the program by calling the Procedure constructor on the appropriate subtrees, then adding the newly constructed Procedure to the table using the Add operation. Since WLP4 procedures can only be used after they are declared, it is important that this function processes the procedures in order of declaration.

As a natural consequence of the behaviour of the Add operations, your program should now catch the following errors:

Duplicate variable declarations in the same scope
Duplicate procedure declarations

Right now, "use of undeclared procedure or variable" errors will not be detected since the Get operation is not being used yet. You will use this operation in the following steps.

Step 3: Computing Types For Expressions

Add a type field to your parse tree data structure. For nodes representing expressions, this will store the type of the expression (int or int*). For other nodes, it can just be blank or store an "undefined" value.

Write a function called annotateTypes which takes in a subtree of the parse tree (it could be a method on the tree class or an external function). It should explore the tree and fill in the type field for each nonterminal node that represents an expression. Nonterminal nodes that represent expressions are those which have expr, term, factor or lvalue on the left-hand side of the rule.

Technically, some terminal nodes have types: NUM tokens, NULL tokens, and ID tokens that correspond to variables (rather than procedures). Our function will not annotate terminal nodes, because it is not really necessary, and having to distinguish between variable IDs and procedure IDs makes the annotation code less clean.

The annotateTypes function is called with respect to a procedure, which we refer to as the "current procedure", and should have access to the signature and local symbol table of that procedure. It should also have access to the top-level symbol table containing all procedures (either through a parameter or as a global variable).

Call annotateTypes from the collectProcedures function. Every time a new Procedure is added to the ProcedureTable, immediately call annotateTypes to process the tree corresponding to the procedure. This ensures that the top-level symbol table only contains the procedures that have been declared "so far", which is necessary for handling use-before-declaration errors correctly; it also ensures the table contains the procedure being currently processed, which is necessary for handling recursion correctly.

The first thing the annotateTypes function should do is loop over the children of the input tree and recursively call annotateTypes on each child. This ensures that the types of children are computed before their parents.

Then, implement all of the type computation rules in the Context-Sensitive Syntax section of the WLP4 Specification. The type computation rules are the ones that tell you what the type of a node should be (as opposed to the ones that simply state conditions that the types must satisfy).

Because the types of children are computed before their parents, most of the rules are straightforward to implement. For example, consider this rule:

The type of a factor deriving LPAREN expr RPAREN is the same as the type of the expr.

This is saying for a node corresponding to the rule factor → LPAREN expr RPAREN, you can just compute the type as follows:

type = getChild("expr")->type;

Some rules are of course more complicated and require checking the types of multiple children, and some rules have error conditions. For example:

The type of a term directly deriving anything other than just factor is int. The term and factor directly derived from such a term must have type int.

This is referring to rules like term → term STAR factor (multiplication). The type of a node with this rule will always be int. However, you need to look at the types of the term and factor children and make sure they are both int. If either child does not have type int, you should produce or throw an error.

The most complicated rules to deal with are probably the ones for procedure calls (factor → ID LPAREN RPAREN and factor → ID LPAREN arglist RPAREN) These rules are discussed separately in Step 5 and you may wish to defer the implementation of these rules until later.

Note that during this process, you will use the Get operations of the VariableTable and ProcedureTable to look up ID names (variable and procedure names) which will naturally produce an error if the name is not found, therefore handling "use of undeclared variable/procedure errors" (although beware the edge case of a procedure and local variable sharing the same name, discussed further in Step 5).

Step 4: Detecting Additional Type Errors

In the Context-Sensitive Syntax section of the WLP4 Specification, there are a number of type rules at the bottom of the section that don't assign types to certain nodes, but simply state conditions that the types of nodes need to satisfy. Check all of these conditions and produce an error if they are not satisfied.

The appropriate place to check the conditions varies. Here are some suggestions.

You can check that the second parameter of wain has type int in the Procedure constructor, or by examining the signature of wain after the constructor returns.
You can check that the type of the return expr of a procedure is int in collectProcedures immediately after annotateTypes finishes.
For the conditions on statements and tests, you could write a helper function checkStatements that searches the tree for the relevant statement rules, and checks the conditions for each rule. This would again be called from collectProcedures after annotateTypes finishes.
For the conditions on declarations, you can add this logic to the part of the Procedure constructor that adds declarations to the local symbol table. After constructing the Variable, check that its type matches the type of the initialization value.

Step 5: Handling Procedure Calls

The type computation rules for procedure calls, factor → ID LPAREN RPAREN and factor → ID LPAREN arglist RPAREN, have more complicated error checking requirements than other type computation rules.

First, you need to check that the ID actually refers to a declared procedure. There is an edge case here: if a local variable is declared that has the same name as a procedure, the local variable takes priority. Therefore, this is actually a two-step process:

Check that the ID's lexeme is not in the local VariableTable for the current procedure. Note the "current procedure" refers to the procedure in which the call occurs, not the procedure being called. For example, if wain calls the procedure proc then this lookup should be done in wain's local symbol table.
If the lexeme is not in the local symbol table (meaning it does not refer to a local variable in this context), now check that the ID's lexeme is in the top-level ProcedureTable. If it's not, this is a "use of undeclared procedure" error.

The other part is checking that the signature matches the sequence of arguments. Note the signature you are checking is the signature of the procedure being called. So if wain calls the procedure proc, you need to look up proc's signature for this step.

If the rule is factor → ID LPAREN RPAREN, the call has no arguments and therefore the signature must be empty, or this is an error.

If the rule is factor → ID LPAREN arglist RPAREN, the arglist subtree contains a number of expr children (whose types have already been computed through recursion). Using the same process you used to extract the signature, extract the types from the arglist, and compare it with the signature.

If the process you used to extract the signature doesn't work for the arglist, you probably overcomplicated the extraction of the signature. The paramlist and arglist subtrees basically have the same structure as linked lists, and you can use either a simple loop or a simple recursive helper function to extract the information from these subtrees into an easier-to-use data structure (like a C++ vector or Racket list).

WLP4 procedures always return int, so after this error checking is done, you simply need to assign int as the type of the node.