Comp 271 Lab 5 - The Compiler

Goals

All of these can be done entirely in the SymbolTable class, by editing Symboltable1.java. An optional goal is to implement a multi-level symbol table.

An IntelliJ project for the whole compiler is available at compilerij.zip. The compiler notes are at compiler.html; this includes discussion of individual files.

Symbol Table

The existing symbol table, in symboltable1.java, is not very efficient. When a local scope (a function) is entered, a cloned copy of the symbol table is saved. During the local scope, new declarations are added to the original table. When the local scope is exited, the symbol table is replaced with the cloned copy, thus restoring the symbol table to its earlier state..

A better implementation of a two-level symbol table is to use the built-in Dictionary class but create separate dictionaries for the global scope and for each separate local scope. When you reach the end of a local scope (endscope(), likely corresponding to the end of a function), the current local-scope Dictionary will be discarded. There may be additional global declarations before the next local scope is entered; at this point you will create a new local scope.

For the two-level scope model, we are at any point either in the global scope (scopecount == 0) or the local scope (scopecount > 0).

Suppose the two Dictionaries are named GlobalDict and LocalDict. If we are currently in a local scope, then allocation will always involve creating entries in LocalDict. GlobalDict will only receive new entries when we are in the global scope..

However, variable lookup while in the local scope will involve first looking up the identifier in LocalDict, and then, if it is not found there, looking in GlobalDict.

The two-level changes here should functionally be equivalent to how the module symboltable1.cs works, but should be more efficient since the approach here avoids cloning the Dictionary. After you finish implementation of this step, the following should still compile:
The improved two-level symbol table leads naturally to a multi-level symbol table that supports arbitrary nesting. The idea is to have a List of Dictonarys, from global to most local. Variable declarations are looked up in this list starting at the most-local end. New declarations are added at the most-local end. See compiler.html for further discussion.

Duplicate Declarations

The current compiler will give an error message indicating an identifier is undefined if the call to SymbolTable.lookup() returns null, so undeclared identifiers are detected. A declaration is a duplicate if there is a previous declaration of that identifier at the same level. This would occur if we had

int n;
int n;

You can detect this by noticing if, when allocVar()/allocConst()/allocProc() are called, there is already a declaration of the identifier in question at the same level. In the following code, the first n is at global scope and the second is at local scope; this is legal.

int n;
foo() {
    int n;
}

Functions are always declared at the global scope, but you still have to check if a function is redeclared (or if a global variable or constant is declared with the same name as the function).

If you detect a duplicate declaration, call t.error(string) with a suitable error-message string that includes the identifier in question. This will print the string and halt the compiler.

The file dupdecl.mjava should not compile after your changes.

Constants

To implement constants, all you have to do is make sure allocConst() works. The compiler syntax for defining constants is

final int two = 2;
final int three = 3;
final int costPerYear = 10000;

The file consts.mjava should then be able to run.

The only file you should have to modify is symboltable.cs (or, preferably, symboltable1.cs).