Comp 271 Lab 5 - The Compiler
- Implement a multi-level symbol table
- Make sure that duplicate declarations are detected
- Implement constants
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
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.
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
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
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
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.
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
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.
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.
To implement constants, all you have to do is make sure allocConst() works.
The compiler syntax for defining constants is
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,