CSC 533: Programming Languages
Spring 2026

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. 25 were provided in HW1. There can be no spaces between the characters in an identifier, integer or string. Delimiters (e.g. '{' and '}') and operators (e.g., '=' and '*') do not require spaces to separate them from other tokens, but all others do. The SILLY language is case-sensitive, so variables a and A are considered unique.

There are four data types in SILLY: integer, Boolean, string, and list. 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 must be explicitly declared before they are used, and a run-time error should occur if a variable is used in an expression before being declared. The bodies of control statements and subroutines specify nested scopes. If a variable is declared inside a body, it is local and will not exist outside of that scope.

There are multiple predefined operators in SILLY for building expressions, as listed below. Note that expressions are enclosed in parentheses. 

 DESCRIPTION    OP(S)       OPERAND(S)                    EXAMPLE
 -------------  -------     ----------------------        ----------------------------
 math ops       + * /       applied to 2 integers         (1 + 2) → 3
                                                          ((1 + 2) + 3) → 6
 Boolean ops    = \ < >     applied to 2 values           (3 = 2) → false
                              of same type                (3 > 2) → true
                !           applied to 1 Boolean          (! true) → false
                & |         applied to 2 Booleans         (& true (! true)) → false                               
                                                          (| false (! true) true) → true
 sequence ops   #           applied to 1 string/list      (# "foo") → 3
                                                          (# [10 20]) → 2
                @           applied to 1 string/list      ("foo" @ 0) → 'f'
                              & 1 integer value           ([10 20] @  1) → 20
                +           applied to 2 strings/lists    ("foo" + "bar") → "foobar"
                              of same type                ([1 2] + [3 4]) → [1 2 3 4]

Note that all data types in SILLY are comparable within their own 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) and lists are ordered by their string values (e.g., ["a", "b"] < ["x", "y"]). You may note that there is no subtraction operator in SILLY. Instead, subtraction can be accomplished by adding a negative integer, e.g., (5 + -1) → 4. Any type mismatch within an expression (e.g., applying the * operator to two non-numeric values or comparing values of different types) should result in a run-time error with a descriptive message.

SILLY provides a variety of statement types, including assignment, 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 "start"
"start"
>>> var x gets 6
>>> print x
6
>>> var y gets (x + 1)
>>> x gets ((2 * x) + y)
>>> print x
19
>>> print y
7
>>> print (x > y)
true
>>> print ((3+2) \ (4+1))
false
>>> print (!((3+2) \ (4+1)))
true
>>> print [(2^3) "foo" (!true) y]    
[8 "foo" false 7]
>>> var num gets 5
>>> while (num > 0) do
  print num
  num gets (num + -1)
endwhile
5
4
3
2
1
>>> var reps gets 0
>>> var str gets ""
>>> while (reps < 3) do
  str gets (str + "foo")
  reps gets (reps + 1)
endwhile
>>> print str
"foofoofoo"

>>> print (true & false)
false
>>> print (true | false)
true
>>> var word gets ("foo" + "bar")
>>> var index gets 0
>>> while (index < (# word)) do
  var letter gets (word @ index)
  print letter
  index gets (index + 1)
endwhile
"f"
"o"
"o"
"b"
"a"
"r"
>>> var nums gets ([1 2] + [3 4])
>>> index gets 0
>>> while (index < (# nums)) do
  var n gets (nums @ index)
  print n
  index gets (index + 1)
endwhile
1
2
3
4
>>> var word gets "banana"
>>> var reverse gets ""
>>> var index gets 0
>>> repeat (# word) times
  reverse gets ((word @ index) + reverse)
  index gets (index + 1)
endrepeat
>>> print reverse
"ananab"

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. Variable declarations and assignments, print statements and while loops are fully implemented, and some but not all the operators are defined. 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 in this assignment:

  1. [20 pts] The Boolean operator '!' (not) is currently implemented, but the '&' (and) and '|' (or) operators are not. Modify the evaluate method of the Expression class so that these two operators are defined for Boolean values. Note: if these operators are applied to non-Boolean values, your code should throw an exception with a meaningful error message.
  2. [10 pts] The '+' operator is currently implemented for integers (addition) and strings (concatenation), but not for lists. Modify the evaluate method of the Expression class so that '+' can be applied to concatenate lists, producing a new list that contains the combined contents of the lists. For example, ([1 2] + ["a" "b"]) should produce [1 2 "a" "b"].
  3. [20 pts] The '#' (length) and '@' (indexing) operators are currently not implemented. The '#' operator can be applied to either a string or list and evaluates to the length of that item (i.e., number of characters for a string, number of items for a list). The '@' operator takes two inputs, either a string or list and an integer. It returns the character or list item at that index (where the index of the first character/item is 0). Modify the evaluate method of the Expression class so that these two operators are defined. Note: as before, any type mismatches should result in an exception with a meaningful error message.
  4. [10 pts] Currently, the interpreter will allow you to redeclare a variable in a scope. For example: 
        var y gets "foo"
    while (x < 10) do
        var y gets "bar"
        print y
        var y gets "biz"
        print y
        x gets (x + -1)
    endwhile
    The first declaration of y inside the while statement is legal — it creates a local variable that overrides the existing variable (declared outside the while statement). However, the second declaration should be illegal, since a local variable with the same name has already been declared within the while statement. Add a method isLocal to the MemorySpace class that returns true if the specified token is declared within the current scope. Then, modify the execute method in the Var class so that an exception is thrown if the variable is already local.
  5. [40 pts] Define a new class named Repeat that inherits from Statement and provides the required methods for a repeat statement. A repeat statement is similar to a while statement, except its expression should evaluate to an integer. The repeat statement executes the code in its compound statement as many times as the expression specifies. Your class should throw an exception if the structure of the statement is invalid (syntax error) or if the test does not evaluate to an integer value (runtime error).

Submit a ZIP file of the entire src folder for your project (including files you did not modify).