CSC 533: Programming Languages
Spring 2016

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> --> <term> | '(' <unary_op> <expression> ')' | '(' <expression> <binary_op> <expression> ')' <output> --> 'output' '(' { <expression> } ')' <if> --> 'if' <expression> { <statement> } { 'elif' <expression> { <statement> } } [ 'else' { <statement> } ] 'end' <while> --> 'while' <expression> { <statement> } 'end' <repeat> --> 'repeat' <expression> { <statement> } 'end' <quit> --> 'quit' <term> --> <identifier> | <number> | <string> | <boolean> <identifier> --> <letter> { <letter> | <digit> } <integer> --> [ - ] <digit> { <digit> } <string> --> '"' { <char> } '"' <boolean> --> 'true' | 'false' <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 '"' <unary_op> --> '-' | 'not' <binary_op> --> '+' | '-' | '*' | '/' | '%' | '.' |'==' | '=/=' | '>' | '>=' | '<' | '<=' | 'and' | 'or'

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 three data types in SILLY: integer, string and Boolean. Variables are not explicitly declared but must be assigned a value before they can be used in an expression or statement. The interpreter relies heavily on run-time type checking when evaluating expressions The math operators ('+', '-', '*', '/', and '%') can only be applied to integers, whereas the Boolean operators ('and', 'or', and 'not') can only be applied to Boolean values. The concatenation operator '.' can be applied to values of any type, with non-strings being converted to strings by placing quotes around them. Comparison operators ('==', '=/=', '>', '>=', '<', and '<=') can be applied to any two values of the same type. Integers are ordered numerically (e.g., 2 < 3); strings are ordered alphabetically (e.g., "bar" < "foo"); Booleans are ordered truthfully (e.g., false < true). In addition, the expressions in if statements and while loops must evaluate to Boolean values, whereas the expression in a repeat loop must evaluate to an integer. Any type mismatches will result in a runtime error.

For example:

SAMPLE CODE (output in red)
  >>> x = 5
  >>> output ( x )
  5
  >>> y = ( x + 1 )
  >>> output ( y )
  6
  >>> output ( ( x * y ) )
  30
  >>> word = "foo"
  >>> longer = ( word . "bar" )
  >>> output ( "longer="  longer )
  "longer=" "foobar"
  >>> output ( ( "longer=" . longer ) )
  "longer=foobar"
  >>> output ( ( ( y / 2 ) + ( x * 2 ) ) )
  13
  >>> output ( "foo"  ( 3 - 1 ) )
  "foo" 2
  >>> repeat 3
        output ( "howdy" )
      end
  "howdy"
  "howdy"
  "howdy"
  >>> num = 1
  >>> N = 5
  >>> repeat N
        output ( num )
        num = ( num * 2 )
      end
  1
  2
  4
  8
  16
  >>> quit
  BYE
  >>> output ( 15 4 ( 15 % 4 ) )
  15 4 3
  >>> flag = true
  >>> output ( flag )
  true
  >>> output ( ( 3 > 2 ) )
  true
  >>> output ( ( "foo" =/= "bar" ) )
  true
  >>> opposite = ( not flag )
  >>> output ( opposite )
  false
  >>> output ( ( flag or ( not flag ) ) )
  true
  >>> output ( ( ( not flag ) and flag ) )
  false
  >>> count = 5
  >>> if ( count < 0 )
    output ( "neg" )
  elif ( count > 0 )
    output ( "pos" )
  else
    output ( "zero" )
  end
  "pos"
  >>> while ( count > -1 )
        output ( count )
        count = ( count - 1 )
      end
  5
  4
  3
  2
  1
  0
  >>> 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, all of the mathematical operators except the remainder operator, '%', are implemented. Add code so that this operator can be used in mathematical expressions as well as the existing one. If the remainder operator is applied to values other than integers, an exception with appropriate runtime error message should be thrown.
  2. Currently, only the data types IntegerValue and StringValue are implemented. Add the BooleanValue type to the language. In addition to recognizing the tokens true and false, you will need to update the Expression class so that a BooleanValue can be used in an expression. You will also need to implement the comparison operators ('==', '=/=', '>', '>=', '<', and '<=') which return Boolean values. If any of these operators are applied to values of different types (e.g., a string and an integer), an exception with appropriate runtime error message should be thrown.
  3. Implement while loops. The class that defines a while loop should be similar to the repeat statement class due to their structural similarity. However, the test for a while loop must evaluate to a Boolean value, and the enclosed statements should repreatedly be executed as long as the test evaluates to true.
  4. Implement if statements, which may include optional elif and else cases. Note that there can be arbitrarily many elif cases, each with its own test, but at most one else case.
  5. Add the Boolean operators and, or, and not. If any of these operators are applied to non-Boolean values, an exception with appropriate runtime error message should be thrown.

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 Token, Statement and Expression. As you add new features, be sure that syntax and runtime 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. When executed, a comment does nothing.