Interpreter Lab

The purpose of this lab is to familiarize yourself with the code we'll be using to make an interpreter for our own programming language.

As you work on this lab, you should also be planning the kind of programming language you want to make.

Consider what kind of syntax you want to use. Maybe you like Java's syntax, or maybe you have ideas for improving on Java. Do you want your language to read more like English? Would you be more motivated to develop a language with some really silly syntax.

Consider the kind of grammar you want to use. Prefix notation, where the operator always comes first (like Scheme or Chumpanese)? Postfix notation (where the operator always comes last)? A mix of prefix and infix (like Java)? Do you want your grammar to consist exclusively of a sequence of statements (like Chumpanese)? Exclusively of nested expressions (like Scheme)? A mix of statements and expressions (like Java)?

Consider what kind of programs you want to be able to write in your language. Programs that perform mathematical calculations? Programs that draw pictures or animations? Programs that play games?


Exercise 1:  Tokenizer

Download interpreterlab.zip.

A simple Tokenizer class has already been written for you. Compile Tokenizer.java. Execute the following code segment. What does it do?

Tokenizer t = new Tokenizer("print 3 + 12");

System.out.println(t.next());

System.out.println(t.next());

System.out.println(t.next());

System.out.println(t.next());


Exercise 2:  Whitespace

Execute the following code segment. What does it do?

Tokenizer t = new Tokenizer("     print     3+ \n 12     ");

System.out.println(t.next());

System.out.println(t.next());

System.out.println(t.next());

System.out.println(t.next());


Exercise 3:  Parser

A simple Parser class has already been written for you. It uses the Tokenizer class to parse a string into an abstract syntax tree--usually a list of lists.

Compile Parser.java. Execute the following code segment. What does it do?

Parser p = new Parser();

System.out.println(p.parse("print 3 + 12"));

The parser expects your program to consist of a single expression or statement. By default, it treats nearly everything as a number or variable name. It therefore assumes that print is a variable name, and having finished parsing that expression, the parser believes it is done and returns print.


Exercise 4:  addPrefix

Let's teach the parser about a print command, using the following grammar:

print expression

The following code creates a Parser and tells it to expect a command that begins with the prefix print and is followed by a single argument. Execute this code. What does it do?

Parser p = new Parser();

p.addPrefix("print", 1);

System.out.println(p.parse("print 3 + 12"));

Now, whenever the parser encounters the word print, it expects it to be followed by a single expression. It knows that 3 is an expression. The parser stops there, since we haven't taught it about addition yet. The parse method returns the abstract syntax tree in the form of a List, whose first element is the String "print" and whose second element is the Integer 3.

Exercise 5:  addInfix

Some programming languages use prefix notation, where the operator precedes the operands. Here are a few examples using prefix notation:

print 3

storeto x

goto loop

(define x 3)

(+ 3 12)

Other languages use postfix operators, where the postfix notation, where the operator appears after the operands. Here are a few examples using postfix notation:

3 print

3 12 +

3 12 + print

Java, like many programming languages, uses a mixture of prefix and infix notation. In infix notation, the operator appears in between two operands. Here are a few examples using infix notation:

3 + 12

size / 2

15 mod 4

x < length

condition1 && condition2

x = 0

The following code creates a Parser and tells it that the + operator uses infix notation, appearing between two arguments. Execute this code. What does it do?

Parser p = new Parser();

p.addPrefix("print", 1);

p.addInfix("+", 2);

System.out.println(p.parse("print 3 + 12"));

Now, when the parser reaches the 3, it looks ahead and discovers the infix operator +. It therefore now considers 3 + 12 to be the expression to pass to the print instruction, just as we would want. The parse method returns a List of two elements, whose first element is the String "print" and whose second element is itself another List. That List consists of three elements: the Integer 3, the String "+" and the Integer 12.

Exercise 6:  Evaluating Integers

Compile Interpreter.java. Execute the following code. What does it do?

System.out.println(Interpreter.eval(new Integer(3)));

The eval method takes in an expression in the form of an abstract syntax tree and evaluates it. An Integer is perhaps the simplest possible expression. The value of an Integer is itself. What is the value of 12? It's just 12. Look at the eval method to find the code that evaluates integers, and you'll see the following, which should make sense to you.

public static Object eval(Object exp)

{

  if (exp instanceof Integer)

  {

    //the value of an integer is itself

    return exp;

  }


Exercise 7:  Evaluating print statements

Execute the following code. What does it do?

ArrayList program = new ArrayList();

program.add("print");

program.add(new Integer(3));

Interpreter.eval(program);

Note: Depending on how you test this code, you may need to import the ArrayList class first, like this:
import java.util.*;

The first three lines create an abstract syntax tree for the instruction print 3 and stores it in the variable program. The last line evaluates this program. As a side effect of evaluating the print instruction, the value of its argument (3) is printed to the console.

Let's look at what the eval method does when it encounters this instruction. First, it establishes that exp is not an Integer or a String, so it must be a List. It therefore runs the following code.

List list = (List)exp;

if (list.get(0).equals("print"))  // print EXP

{

  Object argument = list.get(1);

  System.out.println(argument);

  return "OK";

}

This code identifies that the list begins with the keyword print. It then knows the next element must be the argument to be printed. It uses System.out.println to print that argument. The eval method treats everything as an expression that returns a value. But the print statement isn't meant to return a value, so the code simply returns the String "OK".


Exercise 8:  Evaluating Sums

Execute the following code. What does it do?

ArrayList sum = new ArrayList();

sum.add(new Integer(3));

sum.add("+");

sum.add(new Integer(12));

System.out.println(Interpreter.eval(sum));

The first four lines create an abstract syntax tree for the instruction 3 + 12 and stores it in the variable sum.

The last line finds the value of this expression:  15.

Let's look at what the eval method does when it encounters this expression.

if (list.get(1).equals("+"))  // EXP + EXP

{

  Object argument1 = list.get(0);

  Object argument2 = list.get(2);

  return (Integer)argument1 + (Integer)argument2;

}

It detects that the second element of the list (at index 1) is the + token, and therefore that list represents a sum. It identifies the first and third elements (at index 0 and 2) as the arguments to be added. It then promises that both are Integer objects, adds those integers together, and returns their sum (to be auto-boxed as a new Integer).


Exercise 9:  Print Troubles

Execute the following code. What does it do?

ArrayList sum = new ArrayList();

sum.add(new Integer(3));

sum.add("+");

sum.add(new Integer(12));

ArrayList program = new ArrayList();

program.add("print");

program.add(sum);

Interpreter.eval(program);

The first seven lines correctly build the following abstract syntax tree.

Evaluating this program should print 15 to the console, but it doesn't. That's because when the eval method handles the print statement, it currently prints the argument [3, +, 12] instead of printing the value of that argument (15). The code should have passed the argument [3, +, 12] to the eval method, and printed the result of that method call. In other words, eval often needs to recursively evaluate any subexpressions.

Go ahead and modify the eval method so that the code segment above prints 15 instead of [3, +, 12].


Exercise 10:  Sum Troubles

Execute the following code. What does it do?

ArrayList sum = new ArrayList();

sum.add(new Integer(3));

sum.add("+");

sum.add(new Integer(12));

ArrayList bigSum = new ArrayList();

bigSum.add(new Integer(5));

bigSum.add("+");

bigSum.add(sum);

System.out.println(Interpreter.eval(bigSum));

The first eight lines correctly build the following abstract syntax tree.

But evaluating it results in a ClassCastException. That's because the eval code currently assumes that both arguments in a sum are Integer objects. But in this case, one argument is an Integer (5) and the other is a List [3, +, 12].

We saw that the print operator should print the value of its argument. Likewise, the + operator should add the values of each argument.

Modify the eval method so that + adds the value of each argument. Although the argument expressions may not be Integer objects, you should assume that their values are Integer objects.

Go ahead and modify the eval method so that the code segment above prints 20.


Exercise 11:  Parsing and Evaluating

It's great that we can create abstract syntax trees by hand, but it's so much easier to use the parser to generate abstract syntax trees. For example, the following code has already been written for you in the Interpreter class's main method.

Parser p = new Parser();

p.addPrefix("print", 1);

p.addInfix("+", 2);

Object program = p.parse("print 5 + 3 + 12");

eval(program);

Go ahead and run it. It should now print 20. From now on, you can simply modify the main method any time you want to run a different instruction.


Exercise 12:  Subtraction

Go ahead and introduce support for subtraction to your language, so that the expression 7 - 3 evaluates to 4.

Whenever you add a new construct to the language, you'll need to make changes in two places in Interpreter.java:

1.  In the main method, you'll need to tell the parser to expect your new construct.

2.  In the eval method, you'll need to describe how to evaluate your new construct.

When you're done, modify the main method to run the following program. Test that it prints the correct answer.

print 7 - 3

Then modify the main method to run the following program instead. Test that it prints the correct answer.

print 6 + 4 - 1


Exercise 13:  Parentheses

Try running the following program. What should it print? What does it actually print, and why?

print 9 - 5 + 3

Our parser doesn't understand order-of-operations. The parse method returns the following abstract syntax tree.

Later, you might choose to improve the parser so that it handles operator precedence correctly. For now, however, we'll add support for parentheses so that the programmer can explicitly tell the interpreter which operator to handle first.

Try running the following program.

print (1 + 2)

Since we haven't taught the parser about parentheses, it treats them as variable names. It therefore assumes we're trying to print the value of a variable named (.

In the main method, after constructing the Parser but before calling the parse method, add the following line to teach the parser about parentheses.

p.addDelimiters("(", ")");

Now try running print (1 + 2) again. This time the parser correctly produces the following abstract syntax tree.

 Not surprisingly, though, we get an error, because the eval method doesn't know what to do with the following chunk yet.

In eval, add a new if that identifies when a List begins with an open parenthesis. Assume that such a list will always consist of exactly three elements:  an open parenthesis, a subexpression, and a closing parenthesis. Simply return the value of the subexpression.

Test that your code now correctly runs instructions like the following.

print (1 + 2)

print (9 - 5) + 3

print (((3)))


Exercise 14:  Blocks

It's time for our interpreter to learn to run programs with multiple statements, like the following.

{

  print 3 + 12

  print 8

}

We'll therefore create a new kind of statement--a block statement. A block is just a sequence of zero or more statements surrounded by curly brace delimiters.

Modify the Interpreter class's main method so that the program above is parsed into the following abstract syntax tree.

Executing a block statement simply means evaluating each of the statements inside it.

Modify the eval method so that it evaluates each of the statements inside a block. A block is only meant to be evaluated for its side effects, so you can simply return OK as its value.

Test that your code now correctly runs instructions like the following.

{ print 1 print 2 print 3 }

{ print 3 + 12 print 8 }

{ }

{ print 1 print 2 { print 3 } print 4 { } }


Exercise 15:  Programs in Text Files

Now that our programs are getting longer, it'll be helpful to store programs in text files. A sample program is already stored in a file called program.txt.

Modify the Interpreter class's main method so that it parses and runs this program. For example:

Object program = p.parse(load("program.txt"));

eval(program);

Make sure the behavior you see when you run it matches the instructions you see in program.txt.


Exercise 16:  State

Before we can use variables in our programs, we need to define the State class, which will store and let us retrieve the values of variables. (In the future, you'll use this class for any state information required by your programming language--not necessarily variables.)

Consider the following code segment.

State s = new State();

s.setVariableValue("count", 1);

s.setVariableValue("meal", "fish");

System.out.println(s.getVariableValue("count"));  // prints 1

System.out.println(s.getVariableValue("meal"));   // prints fish

s.setVariableValue("count", 2);

System.out.println(s.getVariableValue("count"));  // prints 2

System.out.println(s.getVariableValue("meal"));   // prints fish

Complete the State class definition so that it works as described above.

Hint:  What data structure would make this task really easy?


Exercise 17:  Passing State

Modify the eval method so that it also takes in a State object as a second parameter. Be sure to pass that same State object to each recursive call. You'll also need to construct a State object in the main method. Test that your code compiles and still does what it did before. We'll begin using the State object in the next exercise.


Exercise 18:  Assignment Statements

Consider the following assignment statement.

sum = 3 + 12

Modify the main method so that the statement above is parsed into the following abstract syntax tree.

Modify the eval method so that it evaluates the expression on the right side of the equal sign and updates the State object to associate that value with the variable name on the left side of the equal sign. For example, the statement above should associate the variable sum with the value 15 in the State object. An assignment statement is only meant to be evaluated for its side effects, so you can simply return OK as its value.

Test that your code can now run instructions like the following without errors.

{

  count = 5

  sum = 3 + 12

  numSpiders = 0

}


Exercise 19:  Variables as Expressions

Consider the following code segment.

{

  count = 5

  sum = 3 + 12

  print sum

  count = count + 1

  sum = count

  print sum + 2

}

The purpose of an assignment statement is to store a value in a variable. On the other hand, when a variable is used as an expression (the boldfaced words above), then the value of that variable is retrieved and used by the program.

The parser will already correctly parse variable names, so you will not need to change the main method.

In the eval method, you should assume (for now) that any String expression must be a variable name. Go ahead and modify eval so that it looks up and returns the values of variables.

Test your interpreter on the code segment above.


Exercise 20:  Testing Your Work

Download LucasMonster.txt and show your teacher that your interpreter runs it correctly.

Congratulations! You've programmed the beginnings of a simple interpreter. 


Programming in Your Own Language

Now decide what kind of programming language you want to make. Go back and read the suggestions at the top of this page.

When you're ready, write a simple program in your own language. It might be about 5 - 10 lines long. It should probably involve some kind of loop. Send it to your teacher in an email. Discuss your program with your teacher and incorporate any feedback.

Do not start coding in Java until your teacher has approved of your language!!!


Language Features

Your choice of what programming features to support in your language will depend on the kind of language you're making. Here are a list of features you might consider supporting, if appropriate.


Write-Up

Using just 1 page of text (and as many screenshots as you like) , provide annotated examples of a program (or programs) in your language.

If your language is sufficiently complex, you may include additional reference pages, etc., as long as you provide 1 page of clearly annotated program(s).


Sample Write-Ups: Irena, MayaStar, Cyrus, Tara Smily Code