CSC 533: Organization of Programming Languages
Spring 2012

HW4: Extending the SILLY Interpreter

For this assignment, you are to extend the SILLY interpreter from HW3 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> { ('-' | '*' | '/' | '%') <int_term> } ')' <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> } <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 Sub 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 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 (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
      end
  >>> a = 0
  >>> call foo ( 4 9 )
  13
  0
  >>> z = 10
  >>> a = 20
  >>> call foo ( ( z + a ) 5 )
  35
  20
  >>> output z
  10
  >>> quit
  BYE
  >>> sub countdown ( num )
        output num
        if num
          num = ( num - 1 )
          call countdown ( num  )
        end
      end
  >>> call countdown ( 5 )
  5
  4
  3
  2
  1
  0
  >>> quit
  BYE

To model the more complex memory structures required in this extension, the Bindings class has been rewritten. Instead of storing a single variable table, it now maintains a runtime stack of variable tables. It also provides methods for creating a new scope (i.e., pushing a new variable table on the runtime stack) and ending the current scope (i.e., popping the variable table off the runtime stack). To handle subroutine declarations, it also maintains a code segment that stores subroutines and allows for lookup as needed. Note that all of the previously existing methods still behave as before, so this new Bindings class can be inserted into your project seamlessly.

You must complete the implementations of the Sub and Call classes to produce a full-featured interpreter. Skeletons of these classes are provided for your convenience.

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. Note that the first thing that the Sub callSub method should do is call bindings.beginNewScope() 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.endCurrentScope() 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.declareLocal(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 callSub you will need to not only declare each parameter but also assign each a value (taken from the ArrayList passed into the callSub 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 callSub method.