CSC 533: Organization of Programming Languages
Spring 2010

HW3: Extending the SILLY Interpreter

For this assignment, you are to extend the SILLY interpreter from HW2 to allow for subroutines and local/global variables. The expanded EBNF for the SILLY language is as follows:

<statement> --> <assignment> | <output> | <if> | <while> | <repeat> | <sub> | <call> | <quit> <assignment> --> <identifier> '=' <expression> <expression> --> <term> | '(' <term> { ('+' | '-' | '*' | '/' | '%') <term> } ')' <term> --> <integer> | <identifier> <output> --> 'output' <expression> <if> --> 'if' <expression> { <statement> } [ 'else' { <statement> } ] 'end' <while> --> 'while' <expression> { <statement> } 'end' <repeat> --> 'repeat' <expression> { <statement> } 'end' <sub> --> 'sub' <identifier> '(' { <identifier> } ')' [ 'local' '(' { <identifier> } ')' ] { <statement> } 'end' <call> --> 'call' <identifier> '(' { <expression> } ')' <quit> --> 'quit' <identifier> --> <letter> { <letter> | <digit> } <integer> --> <digit> { <digit> } <letter> --> 'a' | 'b' | 'c' | ... | 'z' | 'A' | 'B' | 'C' | ... | 'Z' <digit> --> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

The Sub statement defines a simple subroutine, which may have an arbitrary number of parameters. There is an optional local variable declaration that can appear at the beginning of a subroutine, followed by the sequence of statements that make up the subroutine. The Call statement calls a specific subroutine, with a series of expressions specifying the input values that correspond to subroutine parameters.

When a subroutine is called, the expressions in the call are evaluated and assigned to the subroutine parameters in a new local scope. If any local variables are declared, then these must be created in the local scope as well. When executing the statements inside the subroutine, static scoping is used. That is, when looking up or assigning to a variable, the local scope is checked first. If that variable does not appear in the local scope (i.e., it is not a parameter or local variable), then the global scope is used. As before, if this is the first time the variable has been encountered, it will be considered to have value 0 (in the global scope).

For example:

SAMPLE CODE (output in red)
  >>> sub foo ( x  y )
        local ( z )
        z = ( x + y )
        output z
        output a
  >>> call foo ( 4 9 )
  >>> z = 10
  >>> a = 20
  >>> call foo ( ( z + a ) 5 )
  >>> output z
  >>> quit
  >>> sub countdown ( num )
        output num
        if num
          num = ( num - 1 )
          call countdown ( num  )
  >>> call countdown ( 5 )
  >>> quit

In the following impementation files, the VariableTable class has been replaced with a more general Bindings class, which keeps track of the stack of variable tables for local and global scopes, as well as a table of subroutine definitions. Skeletons for the Sub and Call classes have been provided so that the interpreter will execute as is. You must complete the implementations of these two classes to produce a full-featured interpreter.

It is strogly suggested that you complete this assignment in stages. It is much better to have code that works on a limited range of options as opposed to code that tries to do everything but succeeds at nothing. I would recommend the following breakdown:

STAGE 1: Basic subroutine declaration and call (60%)
As a first pass, ignore parameters and local variables. This simplifies the syntax of statements considerably, but still ensures that you get the mechanisms of storing a subroutine declaration and calling that subroutine. Note that the first thing that the Sub call method should do is call bindings.beginScope() to create a new scope for the subroutine (i.e., push it on the runtime stack), and the last thing it should do is call bindings.endScope() to end that scope (i.e., pop it off the runtime stack).
STAGE 2: Add local variables (20%)
Adding local variables is simpler than parameters and is completely enclosed within the Sub class. You will need to be able to recognize the optional local declarations and store each identifier token when you construct the Sub object. Then, when you call that Sub, you will need to declare each of those local variables by calling bindings.declare(t), where t is the token for that variable. After doing that, the methods of the Bindings class will do the right thing with respect to local vs. global.
STAGE 3: Add parameters (20%)
After you have successfully implemented local varibales, parameters will be much easier since they share some of the same behavior. In the Sub constructor, you will need to store each parameter token. Then, in call you will need to not only declare each parameter but also assign each a value (taken from the ArrayList passed into the call method). Within the Call statement, you will need to store the expressions that correspond to the subroutine parameters. When the Call statement is executed, it must evaluate each of the expressions, collect the corresponding values in an ArrayList, and pass that ArrayList as a parameter to the Sub call method.