CSC 533: Programming Languages
Spring 2014

HW2: 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> } ')' <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 '"'

There are no spaces between the characters in an identifier, integer, or string. Otherwise, tokens in the other rules are all separated by whitespace.

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 will repeat its statements a specified number of times, specified either by a number or the length of a string. 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 + 1 / 2 )
  512  
  >>> output ( val1 - val2 )
  -1  
  >>> 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 + "," + y )
  "7,7"
  >>> repeat ( 2 + 1 )
        output "foo" 
      end
  "foo"
  "foo"
  "foo"
  >>> val = 0
  >>> repeat "abcd"
        val = ( val + 1 ) 
      end
      output val
  4
  >>> 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 make the following modifications/additions:

  1. Currently, only positive integers can be read in and stored. Modify the code so that negative integers (with a leading '-') can be handled.
  2. Currently, the '+' operator can be applied to two integers (resulting in addition) or two strings (resulting in concatenation). Modify the code so that mixed expressions are allowed. If the '+' operator is applied to a string and an integer, the integer should be converted to a string and the two values concatenated. For example, ( 12 + "foo" ) --> ( "12" + "foo" ) --> "12foo".
  3. Currently, only the '+' operator is implemented. Add code to handle the other math operations, '-' (subtraction), '*' (multiplication) and '/' (division). All of these operators have the same precedence and left associativity, so expressions can be evaluated in a simple left-to-right order. Note that applying any of these operators to a string value should produce a run-time error.
  4. Currently, the optional else-case for the if statement is not implemented. Add this functionality to the if statement. 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).
  5. Implement 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).
  6. Implement repeat loops. Note that a repeat loop executes the enclosed statements as many times as is indicated by the loop expression. If the loop expression evaluates to a string, then the number of iterations is determined by the length of the string.

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.