CSC 533: Programming Languages
Spring 2019

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 SILLY v. 18.0 are as follows:

<statement> --> <vardec> | <assignment> | <output> | <repeat> | <import> | <while> | <if> <vardec> --> 'var' <assignment> <assignment> --> <identifier> '=' <expression> <output> --> 'output' <expression> | 'output' '{' { <expression> } '}' <repeat> --> 'repeat' <expression> '{' { <statement> } '}' <import> --> 'import' <string> <while> --> 'while' <expression> '{' { <statement> } '}' <if> --> 'if' <expression> '{' { <statement> } [ '}else{' { <statement> } ] '}' <expression> --> <identifier> | <integer> | <string> | <boolean> | '(' <expression> ')' | '(' <unary_op> <expression> ')' | '(' <expression> <binary_op> <expression> ')' | <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' | 'len' <binary_op> --> '+' | '-' | '*' | '/' | '%' | '==' | '!=' | '>' | '>=' | '<' | '<=' | 'and' | 'or' | 'index'

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.

The interpreter relies heavily on run-time type checking when evaluating expressions. Every variable must be declared and initialized before it can be used in expressions or assigned new values. Referencing an undeclared variable (e.g., in an expression or assignment statement) will result in a run-time error, as will redeclaring a variable that already exists. The 'index' operator is used to access a 1-character substring in a string, and must be applied to a string and an integer value (e.g., ( "foo" index 0 ) evaluates to "f"). All other operators must be applied to values of the same type. The '+' operator can be applied to two integers (where it represents addition) or two strings (where it represents concatenation). The other math operators ('-', '*', '/', and '%') can only be applied to integers; the Boolean operators ('and', 'or', and 'not') can only be applied to Boolean values; the unary string length operator ('len') can only be applied to a string. 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 expressions in a repeat loop must evaluate to an integer. Any type mismatch will result in a runtime error.

For example:

SAMPLE CODE (output in red)
  >>> var x = 5
  >>> output x
  5
  >>> var y = ( x + 1 )
  >>> output y
  6
  >>> output ( ( x * y ) + 1 )
  31
  >>> x = ( ( x / 2 ) + ( y * 2 ) )
  >>> output x 
  14
  >>> var word = "foo"
  >>> var longer =  ( word + "bar" )
  >>> output  ( "longer=" + longer )
  longer=foobar
  >>> repeat 5 {
        output "howdy"
      }
  howdy
  howdy
  howdy
  howdy
  howdy
  >>> var rep = 3
      var num = 1
      repeat ( 2 * rep ) {
        output num
        num = ( num * 2 )
      }
  1
  2
  4
  8
  16
  32
  >>> var flag = true
  >>> output flag
  true
  >>> output ( flag == true )
  true
  >>> output ( "foo" != "foo" )
  false
  >>> output  ( 3 > 2 )
  true
  var test = ( "smith" <= "smooth" )
  >>> output test
  true
  >>> output ( ( 3 / 2 ) )
  1
  >>> var str = "foobar"
  >>> output ( len str )
  6	
  >>> output { ( str index 0 ) "..." 
               ( str index ( ( len str ) - 1 ) ) }
  f ... r	
  >>> var boo = true
  >>> var opp = ( not boo )
  >>> output { boo opp }
  true false	
  >>> output ( true and ( false or true ) )
  true		
  >>> output  {  }
  
  >>> var count = 5
  >>> while ( count > -1 ) {
        output count 
        count = ( count - 1 )
      }
  5
  4
  3
  2
  1
  0
  >>> var text = "Jays"
  >>> var i = 0
  >>> while ( i < ( len text ) ) {
        output ( text index i )
        i = ( i + 1 )
      }
  J
  a
  y
  s
  >>> if ( 5 > 3 ) {
        output "yes"
      }
  yes
  >>> var wordy = "banana"
  >>> if ( ( len wordy ) <= 3 ) {
        output { wordy "is" "short" }
      }else{
        if ( ( len wordy ) <= 8 ) {
          output { wordy "is" "medium" }
        }else{
          output { wordy "is" "long" }
        }
      }
  banana is medium

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

For this assignment, you will need to make the following modifications/additions:

  1. Currently, the comparison operators ('==', '!=', >', '>=', '<', and '<=') are implemented, as is the '+' operator that adds integers or concatenates strings. The other string operators, 'len' and 'index', are not yet implemented. Make the appropriate additions to the Expression class so that these operators are recognized and evaluated correctly. Recall that 'len' must be applied to a single string value, and it evaluates to the length of that string (i.e., the number of characters in that string, not counting the quotes). The 'index' operator must be applied to a string and an integer, and returns the 1-character substring at the specified index. A runtime exception should be thrown if either operator is applied to inappropriate types.
  2. Similarly, further update the Expression class so that the Boolean operators ('not', 'and', and 'or') are recognized and evaluated correctly. A runtime exception should be thrown if any of these operators is applied to a non-Boolean value.
  3. The current definition of the output statement only implements this simplest form: the keyword 'output' followed by a single expression. Modify the Output class so that the other option, which allows you to print multiple expressions contained in curly-braces, is implemented and correctly handled. Note: this requires storing all the expressions when an output statement is created, since the expressions cannot be evaluated until the statement is executed. Be sure to also update the toString method so that it accommodates both output formats.
  4. 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 update the Statement class to recognize this new type of statement.
  5. Implement an If class that defines if statements. This class will have significant similarities to the While class due to their structural similarity (both contain statements that are controlled by a Boolean test). However, an if statement has an optional else case that must be handled. As before, you will also need to update the Statement class to recognize this new type of statement.

Note that in making these additions, the driver class (Interpreter) need not be modified at all. Instead, you will be adding new derived classes (While and If), with some modifications to Statement, Output, and Expression. As you add new features, be sure that syntax and runtime errors result in exceptions being thrown with informative messages.

Also note that an import statement is especially useful as you debug your interpreter. You may enter SILLY statements in a text file, then use an import statement (e.g., import "prog.txt") to read in and execute those statements in sequence.