CPS710	Assignment 5
	Evaluator - Part 2: Symbol Tables	Due: December 14

Objectives

However, you still do not need to handle errors in programs. This functionality will be addressed in the final assignment.

With this assignment you should become much more familiar with symbol tables and scoping schemes. The learning objectives covered in this assignment are:

• 7Cb (which automatically includes 7Da and 7Ca)
• 7Bb (which automatically includes 7Db and 7Ba)
• 7Ab (which replaces a component of 7Bb and includes it)

Solutions to the previous assignment, assignment 4, will not be provided. You will therefore need to complete the level objectives of that assignment at the same level as the ones on this assignment as a base for this one and for the one that follows. (i.e. you need the A4 C-level objectives for the A5 C-level objectives, and so on)

Preparation

• Revised IdBoolToken.java, IdNumToken.java, and IdSetToken.java and a new superclass for them called IdentifierToken.java. This is to support the changes that you need to make to the scanner starting at level C. Take a look at the three files for the specific tokens. As you can see, the only work now done by these three classes is to record the type of token that is being scanned. Everything else has been moved to their superclass IdentifierToken.java. This reorganization does not affect the operation of the scanner.

• A new java file: EvaluationException.java. This is a subclass of Exception that is specific to evaluation exceptions. This class will be mostly used in the next assignment to handle evaluation errors, but it does have one use for this assignment: you should define a ReturnException subclass of EvaluationException to be used in the evaluation of return statements to end the execution of the function's body and return the return value to the evaluator of the function call.

• The two test scripts for this assignment: runtests, and the unit test t.

Assignment

In addition to the semantic of HL described in HL semantics - Part 1 handed out in the fourth assignment, the remaining semantics of HL can be found in HL semantics - Part 2.

Below are the components that you will need to implement in this assignment. As you do so, remember that, as with previous assignments, you can continue to assume that the HL programs are error free. This means that your program does not need to handle invalid uses of variables or function calls or returns yet.

7Cb: Global variables and while statement

• Implement a global identifier/name table, and modify your identifier tokens and ASTs so that their value is the identifier's key into that table instead of the name of the identifier.

• Implement a minimal (i.e. global) symbol table for your identifiers where you will keep the value of each identifier in addition to its information.

• Write eval visitors for declarations, assignments, and identifiers used in expressions and conditions.

• Write the eval visitor for while statements.

Implementation Suggestions:

• Because the name table defines a relationship between the lexeme of an identifier and a key representing that lexeme, and because the interaction between the interpreter and the name table primarily takes place during scanning, the natural place to locate the name table functionality is with the scanner, particularly in the class IdentifierToken, where the name table can be a static table in that class.

  In the Javadoc comments of the IdentifierToken.java handout there is a proposed API that can support all the requirements of this assignment at all levels.

• This proposed API assumes that a function call HLSymbTab.newIdName(key) will be triggered whenever a new name is encountered. newIdName would be a static method in a class HLSymbTab where the symbol table is implemented. This function call will be needed for learning objectives C and B, and can possibly be moved elsewhere when implementing static scoping for the A learning objective.

  No matter how far you go in implementing the symbol table mechanisms in this assignment, you will need Java classes to support this functionality. In all implementations you will need a class for the symbol table entries. I have called this class HLSymbTab (but no handout is provided for it). An instance of this class keeps information about a single variable. The functionality of this class is very minimal at the C level when all variables are global. It will increase in complexity with the implementation of the other scoping mechanisms.

  If an instance of this class is a symbol table entry, a symbol table is simply an table of these entries, i.e. an ArrayList of these entries. At the C level all that is needed is a single symbol table for the entire program. This ArrayList can simply just be a static variable in this class.

7Bb: Dynamic Scoping and for loop

• Implement the evaluation of for statements.

• Implement the evaluation of function calls (including Boolean function calls which are parsed separately), return statements, and variable declarations, assuming that the HL language is dynamically scoped.
  If you are feeling very confident, you can skip this particular component of the 7Bb learning objective, and implement 7Ab, which is static scoping, instead. However, many of the comments below also apply to 7Ab.

Implementation Suggestions:

• You will need a few additional classes to support the symbol table functionality described in the lectures. Here are the ones I implemented:

  • As described in the C learning objective, HLSymbTab describes a symbol table entry about a single variable. In the C learning objective you also defined a single symbol table for the entire program. The symbol table entries are needed at the B level, but the static symbol table is not needed any more. Instead:

  • I have defined a class HLNameStack for the name stacks used to implement dynamic scoping, as follows:

    public class HLNameStack extends ArrayDeque < HLSymbTab > 

    Each name has its own stack, which is accessed via that name's key. HLNameStack keeps a static array of all these stacks, just like HLSymbTab kept a static array of all the symbol table entries at the C level. You will want to keep this class separate from HLSymbTab and HLActivation (described next) because you will not need it for static scoping, unlike the other two classes.

  • HLActivation for the single activation stack that keeps track of all activations of all variables. Popping this stack when returning from a function call controls what name stacks also get popped.

• As described in the lectures, return statements are implemented by throwing exceptions. For this purpose a generic EvaluationException class is provided in handouts to be used for all exceptions thrown during evaluation. This class will be used for evaluation errors in the next assignment, but you should also define a subclass for return exceptions that is more focused on supporting the evaluation of return statements including passing the return value to the evaluator of the function call.

7Ab: Static scoping

• Implement the evaluation of function calls, return statements, and variable declarations assuming that HL is statically scoped instead of dynamically scoped.

  Note: 7Ab is not a complete replacement for 7Bb: You still need to implement the other component of 7Bb consisting of the evaluation of for loops.

Implementation Suggestions:

• At this level the parser will be involved in implementing some of the scoping functionality. You will therefore need to modify HL.jjt to interact with the symbol table. I have also found it useful to modify the main program in TestHL.java to initialize the global scope. You can see two lines I have added before the parse-eval loop to do this in the TestHL.java provided in the Aonly Handouts directory:

• For static scoping it is useful to think of the two types of occurrences of identifiers in the HL.jjt parser as being parsed differently.
  • Declaring an identifier creates a new entry for that identifier in the symbol table for the currently active scope.
  • When an identifier is being used, then the ASTidentifier needs a reference to the scope of that identifier in addition to its name key

• A word of warning when implementing the evaluation of function calls: make sure that you evaluate all the parameters being passed to the function before pushing a new scope onto the activation stack. This is particularly important with recursive function calls because parameters may contain expressions that depend on local variables and parameters in the calling scope.

7A⁺b: Set formers

• Implement the evaluation of set formers.

Implementation Suggestions:

• Please read carefully the semantics of set formers in the HL semantics - Part 2 document.
• You will be implementing block scopes for set formers. You can reuse a lot of the functionality you developed for function scopes. However, these scopes are much simpler: they only have a single entry for the set former variable, and they are also unnamed which means that no entry in the symbol table will point to these scopes (unlike function scopes where the symbol table entry defining the function points to a function's scope).

References

• ArrayDeque to implement stacks.
• ArrayList to implement lists of parameter values.

Testing your assignment

The tests and results are in the Tests directory.

Submitting the assignment

• Zip up together HL.jjt, IdentifierToken.java and all the other java files that you have modified into A5C.zip, A5B.zip, or A5A.zip to indicate which learning objectives should be assessed.
  There is no need to include EvaluationException.java, SimpleNode.java, TestHL.java, and the java token file other than IdentifierToken.java as we will provide these, or the AST files because they will be recreated automatically when we compile your submission. However, if you do change one of these files, you should include them in your zip file.
• Submit electronically your A5 zip file.

• Make a copy of your A5 zip file and call it A4A.zip, A4B.zip, or A4C.zip, depending on how far you got in the learning objectives for assignment 4 and submit that A4 zip file.
• Send an email to cps710@cs.torontomu.ca telling us that you have resubmitted assignment 4 because we won't know otherwise. Be sure to include your moons userid in the email, so we can find your assignment.