CSC 533: Programming Languages
Spring 2014

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> | <quit> <assignment> --> <identifier> '=' <expression> <expression> --> <add_expr> | <other_expr> <add_expr> --> <term> | '(' <term> { '+' <term> } ')' <other_expr> --> '(' <int_term> { ('+' | '-' | '*' | '/') <int_term> } ')' <output> --> 'output' <expression> <if> --> 'if' <expression> { <statement> } [ 'else' { <statement> } ] 'end' <while> --> 'while' <expression> { <statement> } 'end' <repeat> --> 'repeat' <expression> { <statement> } 'end' <subdecl> --> 'sub' <identifier> '(' { <identifier> } ')' [ 'local' '(' { <identifier> } ')' ] { <statement> } 'end' <subcall> --> 'call' <identifier> '(' { <expression> } ')' <quit> --> 'quit' <quit> --> 'quit' <identifier> --> <letter> { <letter> | <digit> } <integer> --> [ - ] <digit> { <digit> } <string> --> '"' { <char> } '"' <int_term> --> <integer> | <identifier> <term> --> <string> | <int_term> <letter> --> 'a' | 'b' | 'c' | ... | 'z' | 'A' | 'B' | 'C' | ... | 'Z' <digit> --> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' <char> --> any non-whitespace character other than '"'

The SubDecl statement declares 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 SubCall 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 (local variables are initialized to 0 by default). 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.

For example:

SAMPLE CODE (output in red)
  >>> sub foo ( x  y )
        local ( z )
        z = ( x + y )
        output z
        output a
  >>> a = 0
  >>> 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

To model the more complex memory structures required in this extension, the MemoryStack class has been rewritten. Instead of storing a single stack of variable bindings, it now maintains a runtime stack of activation records (each of which contains a stack of variable bindings). The MemoryStack class also provides methods for creating a new scope (i.e., pushing a new activation record on the runtime stack) and ending the current scope (i.e., popping the current activation record off the runtime stack). Note that all of the previously existing methods still behave as before, so this new MemoryStack class can be inserted into your project seamlessly.

You must implement the SubDecl and SubCall classes to produce a full-featured interpreter. The SubDecl class models a subroutine declaration. When executed, a copy of the subroutine code is stored in memory so that it can be accessed and invoked by a subroutine call. The SubCall class models a subroutine call. When executed, it locates the code for that subroutine, calls the createScope method of MemoryStack to push an activation record on the runtime stack, executes the statements in the subroutine, and then calls endScope to pop the activation record. If the subroutine has parameters or local variables, these must be created and initialized at the beginning of the call.

It is strongly 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.
STAGE 2: Add local variables (20%)
Adding local variables is simpler than parameters and is completely enclosed within the SubDecl class. You will need to be able to recognize the optional local declarations and store each identifier token when you construct the SubDecl object. When the subroutine is later invoked (by the execute method of SubCall), then each of those local variables must be created in the current scope (by calling Interpreter.STACK.declareLocal).
STAGE 3: Add parameters (20%)
After you have successfully implemented local variables, parameters will be much easier since they share some of the same behavior. In the SubDecl constructor, you will need to store each parameter token. When executing a subroutine call, you will need to not only declare each parameter but also assign each a value.