CSC 533: Programming Languages
Spring 2024

HW2: Implementing a Simple Interpreter

For this assignment, you are to complete an interpreter for a subset of the SILLY (Simple, Interpreted, Limited Language for You) programming language. Recall that the syntax rules for SILLY v. 23 were provided in HW1. There can be no spaces between the characters in an identifier, integer, or string. Otherwise, whitespace is allowed between tokens. 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 language is dynamically typed, meaning that a variable does not have a set type but is defined by the value assigned to it. Variables are not explicitly declared - the first time an assignment is made to a variable, that variable is implicitly declared and initialized. If a variable is used in an expression before having a value assigned to it, a run-time error should occur. Compound statements represent new, nested scopes. If a variable is initialized inside a compound statement, it is local and will not exist outside of that scope.

There are a number of operators in SILLY for building expressions, as listed below. Note that '~' is used for subtraction, as the '-' symbol is used for representing negative integer values (e.g., -3). 

 DESCRIPTION                  OPERATOR(S)       OPERAND(S)                           EXAMPLE
 ------------------------     -----------       -------------------------------      ----------------------------
 standard math operations     + ~ * / % ^       applied to 2 integers                (4 ~ 1) → 3
 string concatenation         +                 applied to 2 strings                 ("foo" + "bar") → "foobar"
 string length                #                 applied to a string                  (# "foo") → 3 
 string indexing              @                 applied to a string and integer      ("foo" @ 0) → "f" 
 Boolean negation             not               applied to a Boolean                 (not true) → false
 Boolean connectives          and or            applied to 2 Booleans                (true or false) → true
 comparison operators         == != < > <= >=   applied to two value of same type    (3 <= 4) → true

Note that the '+' operator can be applied to two numbers (addition) or to two strings (concatenation). The comparison operators 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"); and Booleans are ordered truthfully (e.g., false < true). Any type mismatch within an expression (e.g., applying the '*' operator to two string values or comparing values of different types) should result in a run-time error with a descriptive message.

SILLY provides a number of different statement types, including assignment, compound, print, if and while. Sample interpretations of SILLY code are provided below, with user input prefaced by ">>>" and the interpreter's output highlighted in red:

SAMPLE CODE (output in red)
>>> print(-11)
-11
>>> print("foobar")
foobar
>>> x = 9
>>> print(x)
9
>>> y = (2 * x)
>>> print(y)
18
>>> word = "foo"
>>> print(word)
foo
>>> print(((word + "bar") + (word + "biz")))
foobarfoobiz
>>> flag = true
>>> print(flag)
true
>>> print((not flag))
false
>>> if (x < y) {
        print("ok")
        print("still-ok")
    } noelse
ok
still-ok
>>> if (x > y) {
        print("not-ok")
        print("still-not-ok")
    } noelse
>>> count = 5
>>> while (count > 0) {
        print(count)
        count = (count ~ 1)
    }
5
4
3
2
1
>>> stop = false
>>> num = 2
>>> while (not stop) {
        print(num)
        num = (2 * num)
        if (num > 1000) {
            stop = true
        } noelse
    }
2
4
8
16
32
64
128
256
512

>>> print(1, (15 / 3), (true or false), ("ab" + "cd"))
1 5 true abcd
>>> text = "banana"
>>> print((# text), (text @ 0))
6 b
>>> reverse = ""
>>> i = 0
>>> while (i < (# text)) {
        reverse = ((text @ i) + reverse)
        i = (i + 1)
    }
>>> print(text, reverse)
banana ananab 
>>> grade = 88
>>> if (grade >= 90) {
        print("excellent")
    } else {
        if (grade >= 75) {
            print("good")
        } else {
            print("needs_work")
        } 
    }
good
>>> current = 5
>>> while (current != 1) {
        if ((current % 2) == 0) {
            current = (current / 2)
        }
        else {
            current = ((3 * current) + 1)
        }
        print(current)
    }
16
8
4
2
1
>>> for rep from 1 to 5 {
        print(rep, (rep^2))
    }
1 1 
2 4
3 9
4 16
5 25
>>> for j from 1 to 3 {
        for k from j to 3 {
            print(j, k)
        }
    }
1 1 
1 2
1 3
2 2
2 3
3 3

An incomplete version of the SILLY interpreter is provided for you via the following classes/files (which are also downloadable as SILLY.zip):

As provided, the interpreter runs a subset of the SILLY language. Assignments, while loops and compound statements are fully implemented. If and print statements are partially implemented (see details below). Note that statements in the left column above will execute given the existing code; statements in the right column depend on language features that you will be implementing.

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

  1. Within the Expression class, all the required operators are defined except for two string operators: # and @. Modify the Expression constructor so that expressions involving these two operators can be read in and stored. Then, modify the evaluate method so that the operators are evaluated as specified.
  2. The current definition of the if statement is incomplete in that it does not support the else case. Modify the If class so that it can handle this additional case. This will require adding field(s) and modifying the constructor (to be able to read and store the statements associated with the else case), the execute method (to execute those statements when the test fails), and the toString method (to display all formats).
  3. The current definition of the print statement is incomplete in that it can only display a single expression. Modify the Print class so that it can print multiple expressions, separated by commas. When printed, the values should all appear on the same line, separated by a single space. This will require adding field(s) and modifying the constructor (to be able to read and store an arbitrary number of expressions), the execute method (to display all the expression values on a single line), and the toString method (to display the general format).
  4. Implement the for statement in a class named For. A for statement specifies a loop variable and a range for values. The loop variable is assigned a value from that range for each pass through the loop. For example, the statement: for i from 1 to 10 { print(i) } would loop 10 times when executing, printing the values 1, 2, ..., 10 on separate lines. Note that the range is assumed to be increasing, so the statement: for i from 10 to 1 { print(i) } would not loop at all and so nothing would be printed. Be sure to implement all the required methods of the Forclass, including toString.

Note that these additions/modifications may also require updating other files in the project so that all new operators, keywords and statements are recognized. All syntax errors (e.g., malformed expressions) and runtime errors (e.g., type mismatches) must be caught by your code and result in meaningful error messages.