CSC 533: Programming Languages
Spring 2017

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> | <comment> <assignment> --> <identifier> '=' <expression> ';' <expression> --> <term> | <unary_op> <term> | <term> <binary_op> <expression> <term> --> <identifier> | <integer> | <string> | <boolean> | '(' <expression> ')' <output> --> 'output' [ <expression> ] ';' <if> --> 'if' <expression> { <statement> } { 'elif' <expression> { <statement> } } [ 'else' { <statement> } ] 'end' <while> --> 'while' <expression> { <statement> } 'end' <repeat> --> 'repeat' <expression> { <statement> } 'end' <comment> --> '//' remainder of line <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 '+' operator can be applied to integers (where it represents addition) or strings (where it represents concatenation). If applied to a string and another data type, the data value is coerced into a string by placing quotes around it, then concatenated. 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. 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 ) + 1 ;
  31
  >>> num1 = ( y / 2 ) + ( x * 2 ) ;
  >>> output num1 ;
  13
  >>> word = "foo" ;
  >>> longer =  word + "bar" ;
  >>> output  "longer="  + longer ;
  "longer=foobar"
  >>> output longer + 123 ;
  "foobar123" 
  >>> 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
  >>> flag = true ;
  >>> output flag ;
  true
  >>> output  3 > 2 ;
  true
  >>> output "foo" == "bar" ;
  false
  >>> if true
        output "OKAY" ;
      end
  "OKAY"
  >>> count = 5 ;
  >>> // identify number type
      if count < 0
        output "neg" ;
      elif count > 0
        output "pos" ;
      else
        output "zero" ;
      end
  "pos"
  >>> while count > -1
        output count ;      // display
        count = count - 1 ; // increment
      end
  5
  4
  3
  2
  1
  0
  >>> opposite = not flag ;
  >>> output opposite ;
  false
  >>> output flag or not flag ;
  true
  >>> n1 = 4 ;
  >>> n2 = 2 ;
  >>> while ( n1 > 0 ) and ( n2 > 0 ) 
        n1 = n1 - 1 ;
        n2 = n2 - 1 ;
      end
      output n1 + "--" + n2 ;
  "2--0"      

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. The current implementation of the output statement requires that there be an expression to evaluate and print. According to the BNF rules, the expression should be optional - if no expression is there, then a blank line should be output when the statement is executed. Modify the Output class so that the expression is optional.
  2. Currently, the BooleanValue data type is implemented, but no Boolean operators are defined. As a result, the Boolean constants true and false can be output and assigned to variables, but no comparisons can be made. Update the Token and Expression classes so that the comparison operators ('==', '!=', '>', '>=', '<', and '<=') are recognized and can be used to build Boolean expressions (evaluating to true/false). If any of these comparison 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 a While class that defines while loops. This class should be similar to the Repeat class due to their structural similarity (both contain statements that are controlled by a test). However, a while statement is controlled by a Boolean expression and repeatedly executes the block of enclosed statements as long as the expression evaluates to true. Note that you will also need to make small additions to the Token and Statement classes.
  4. Implement an If class that defines 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 program file (Interpreter.java) need not be modified at all. Instead, you will primarily adding new 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.