CSC 533: Organization of Programming Languages
Spring 2012

HW3: Implementing a Simple Interpreter

For this assignment, you are to complete an interpreter for a simple, procedural programming language named SILLY (Simple, Interpreted, Limited Language for You). The grammar rules for the SILLY language are 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' <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 '"'

For simplicity's sake, each token in the language is separated by spaces and/or tabs.

The SILLY language is case sensitive, so variables a and A are considered unique. There are two data types in SILLY, integer and string. Variables are not explicitly declared but must be assigned a value before they can be used in an expression or statement. An assignment statement assigns a value to a variable. An output statement displays a value on a line by itself. If statements and while loops are controlled by an expression, where any nonzero integer value or nonempty string value is considered to be true. A repeat loop is controlled by an integer value and iterates that set number of times. Finally, a quit statement terminates the interpreter.

For example:

SAMPLE CODE (output in red) 
  >>> x = 4
  >>> output x
  4
  >>> y = ( x + 1 )
  >>> x = ( 1 + 5 - 2 )
  >>> output ( y + x )
  9
  >>> word1 = "foo"
  >>> word2 = "bar"
  >>> output ( word1 + word2 )
  "foobar"
  >>> output ( word1 + 99 )
  "foo99"
  >>> val1 = 1023
  >>> val2 = 1024
  >>> output ( val1 % 2 )
  1  
  >>> output ( val2 / 10 % 2 )
  0  
  >>> output ( 65 - 1 / 8 / 2 )
  4  
  >>> quit
  BYE
 
  >>> num1 = 4
  >>> if num1
        output ( "num1=" + num1)
      else
        output "nope"
      end
  "num1=4"
  >>> x = 10
  >>> y = 1
  >>> while ( x - y )
        x = ( x - 1 )
        y = ( y + 2 )
      end
  >>> output x
  7
  >>> step = 1
  >>> repeat 5
         step = ( step * 2 )
         output step
      end
  2
  4
  8
  16
  32
  >>> quit
  BYE

An incomplete version of the SILLY interpreter is provided for you via the following classes/files:

To produce a fully functional interpreter for the SILLY language, you will need to augment/modify the provided code so that it:

  1. Allows for expressions to involve multiplication ('*'), integer division ('/'), and remainder ('%'). All of these operators have the same precedence and left associativity, so expressions can be evaluated in a simple left-to-right order.
  2. Allows for an else case in if statements. Note that there is only one 'end' keyword for an if statement - if there is an else case, the keyword 'else' separates the statements to be executed if the test expression evaluates to true (i.e., nonzero/nonempty) or false (i.e., zero/empty).
  3. Implements while loops. The class that defines a while loop should be similar to the if statement class due to their structural similarity. However, when executed a while loop should repeatedly execute the enclosed statements as long as the test expression evaluates to true (i.e., non-zero).
  4. Implements repeat loops. Note that a repeat loop executes the enclosed statements as many times as is indicated by the loop expression.

Note that in making these additions, the main progam file (Interpreter.java) need not be modified at all. Instead, you will primarily be making changes to the various Statement classes, with some minor modifications to Statement and Expression. As you add new features, be sure that syntax errors result in exceptions being thrown with informative messages.

For extra credit, add a comment feature to the language. A comment can begin at any point on a line, starting with '//', and continues to the end of that line. A comment is ignored when executing the program.