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

UNDER CONSTRUCTION

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

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

• 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.

• Revised IdBoolToken.java, IdNumToken.java, and IdSetToken.java to support the C level objectives.

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, unindexed assignments, and identifiers used everywhere else.

• 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 Handout IdentifierToken.java you can see 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, is predicates, and for loop

• Implement the evaluation of for statements.

• Add three predicates to HL to verify the type of a value. These predicates are called isint, isstr, and islst, and you can see how they are meant to be used in the test 7Bb2-is.hl and 7Bb2-is.expected

• Implement the evaluation of function calls, 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 and indexed assignments

• Implement the evaluation of indexed assignments. Their semantics were defined on the fourth page of HL Semantics - Part 1.

• 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 and the three is predicates.

Implementation Suggestions:

• For the indexed assignments, the tests only check positive indexes because that is enough work for a toy language. Here are a few suggestions:
  1. Implement HLStrings before HLLists.
  2. For HLLists, it is easier to work at a high level using already defined HLList operations instead of working at a lower level with ArrayLists.
  3. You may find it useful to tweak HLObject.java.

• 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

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 and all the 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 and TestHL.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@scs.ryerson.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.