Symbol table

Introduction

In this project, you will build a symbol table for the programming language from the AST Construction project. I will provide you with a grammar to use so we are all starting from the same place. In order to populate the symbol table and resolve references, you will need to create two tree pattern matchers (tree grammars with filter=true): Def.g and Ref.g. You will track symbol definitions and place them in appropriate scopes. Further, you will have to chase references to classes by loading them from the disk (assume a file extension of .sl for our programming language) and adding them to the symbol table. To complete this project, you will need to study materials from the symbol table lectures carefully (and can look at the old online Symbol tables notes).

As an example of what I expect, consider the following 3 SL class definitions.

and

There will be two passes using two tree pattern matchers: Def.g and Ref.g. During the first pass, as you fill your symbol table, you will print out definitions of symbols. At the close of every scope, you will print out the list of symbols in that scope along with the name of that scope. For the above classes, you would see the following:

***** Running Def *****
Load S
define class S line 1
define variable a line 2
define method blort line 3
Scope S: [a, blort]
define class T line 1
define variable i line 2
Load U
define class U line 1
define variable i line 2
define variable s line 3
Scope U: [i, s]
define variable u line 3
define method foo line 4
define variable q line 4
define variable w lines 5
define variable x lines 6
define variable i lines 10
Scope local foo level 1: [i]
Scope local foo level 0: [w, x]
Scope foo: [q]
define method bar line 16
Scope local bar level 0: []
Scope bar: []
Scope T: [foo, i, u, bar]

Then executing the reference phase tree parser from Ref.g, you must emit the following messages for the references:

***** Running Ref *****
ref class S line 1
ref class U line 3
ref variable q type string line 5
ref method bar type list line 6
ref variable x type list line 7
ref variable u type U line 8
ref class U line 8
ref variable x type list line 9
ref variable i type int line 11
ref variable a type int line 13
ref method blort type void line 14
ref variable i type int line 17

Note at the Def.g tree pass must chase references to classes by loading them from the disk in the current directory whereas the reference Ref.g pass already sees them in the symbol table and does not need to reload them.

It is okay if you're output is slightly different or the order is slightly different, but you must track all of the information above and printed out in a sensible fashion.

Tasks and deliverables

Your grammar file will build an AST as before and we will do symbol table management in the tree grammar Def.g. You need to add actions at definition. You also need to add actions to push and pop new scopes. You must allow forward references to fields and methods. Forward references are dealt with by having two passes.
Emit an error message if a symbol is not defined. If it is defined, print the message per the above.
For each definition of a variable (parameter, field, or local variable), method, or class, you must print out a message per the above.
For references to classes, load them from the disk during the definition phase. You do not need to run the Ref.g references pass on the loaded classes. You only run the Def.g phase so that we can learn about the fields and methods. Create a new Def.g tree parser instance each time you go to the disk looking for a type. Assume all types are in the current directory and with file extension ".sl".
For each reference to a variable, method, or class, you must print out a message per the above.
For expr.method() and expr.field references you will not know the type of expr and so you do not need to deal with member access expressions--just deal with isolated identifier references like x and foo().
Once you reach the end of a scope (class definition, method definition, or {...} block), you must print the list of symbols and that scope per the above.
Create a TestSym class with a main() method that accepts a file name on the commandline as the first argument. That method should open the file, parse and build and AST, run the Def.g tree parser on the tree, run the Ref.g tree parser on the tree, and then terminate.
Deal properly with cyclic class references: C has a field of type D and D has a field of type C.
The first pass should save current scope information in each identifier node so that the second, Ref.g, pass can use it to resolve symbols.
You must resolve type references only during the second phase not the first. That means that superclass references and method return types and variable types cannot be determined until the resolve phase. We need two different phases to handle forward references.
You must identify the types of all expressions except those involving arithmetic operators like + and *. Make sure you identify and print out the type of things like a.b, a.b.c, a.f().c, a[i].b etc... Note that you still need to walk expressions like a.b+c.d so your tree walker gets to the a.b and c.d operands. As you print out "found x" etc... identify the type:
You must be careful not to allow forward references of local variables. Do the trick where you check the token index of the reference and the definition to make sure they are in the correct order IF the reference is in a local or global scope. For example, this is illegal:

Sample symbol table objects

You should create a class hierarchy as described in the following diagram:

The following code snippets may be useful to you.

Submission

You will create a jar file called sym.jar containing grammars, source, and *.class files and place in your lib directory:

https://www/svn/userid/cs652/proj3/trunk/lib

You can use the svn account for development of the software to if you would like, but I will only be looking at your sym.jar file in the lib directory.

Grading

Make sure your jar has the TestSym in the default package with a main method so that I can test your code. You can give me a number of samples in your jar at the top level so that I can test your code using your samples.

You will be graded on the actions within the grammar as well as the symbol table code. I will test your program on valid and invalid input.