Tree-based interpreter - USF Computer Science 652 - Programming Languages

Introduction

In this project, you will build another interpreter (for language SL) but one that does not translate to bytecodes first. In a bytecode interpreter, the final phase walks the tree to generate bytecodes. You will replace this final phase with an evaluator that directly interprets the trees. Unlike a bytecode interpreter, the tree-based interpreter must handle symbol table scopes at the same time as execution contexts.

Unfortunately, this combination of symbol table management and execution environment management makes tree-based interpreters more difficult. There are two other difficulties. First, it is harder to understand how the parser can jump around the tree to execute while loops and method calls than it is to understand how a stack-based bytecode interpreter does this. Second, the parser is using the hardware stack to do method calls but also must maintain a stack of execution contexts that hold local variables and parameters. To do a return requires that we unroll the Java stack as well as the execution contexts associated with SL method calls. As we discussed in class, you will throw an exception to interpret the return statement.

Because ANTLR consumes all input before it starts parsing at the moment (and I didn't have time to correct this), your interpreter will not work interactively statement by statement. The interpreter will read until end of file like all the other programs we have written. You will read in statements like:

x = 1;
print x;

and generate output ("1" in this case).

You are given a complete parser that builds suitable AST structures. The Test class also provides an -ast commandline option that will print out tree structure for the input. You can use this to discover the nature of the trees built by the parser. "All" you have to do is fill in the actions in the tree grammar to get the 10 examples in the next section to work properly. That and add some functionality to Interpreter.java. That's it. I do the rest for you since you know how to parse, build trees, do symbol table management, and walk trees.

Examples

x=1;
{
	y=2;
        print y;
        print x;
}
print x;

one() = 1;
print one();

f(x) = 2*x;
print f(3);

g(x,y) {
   z = 2;
   return x*y*z;
}
print g(4,5);

class Point {
  x = 0;
  y = 0;
  new(a,b) { x=a; y=b; } 
}

p = Point.new(1,2);
p.x = 3;
print p;
print p.x;

class Point {
  x = 0;
  y = 0;
  new(a,b) { x=a; y=b; } 
  add(p) { return Point.new(x+p.x, y+p.y); }
}

p = Point.new(1,2);
q = Point.new(3,4);
print p.add(q);

class Point {
  x = 0;
  y = 0;
}

p = Point.new();

class Point {
  x = 0;
  y = 0;
  new(a,b) { x=a; y=b; } 
}

class Point3D extends Point {
  z = 0;
  new(a,b,c) { x=a; y=b; z=c;} 
}

p = Point3D.new(3,4,5);
print p;

class A {
  speak() { return id(); }
  id() { return 1; }
}

class B extends A {
  id() { return 2; }
}

a = A.new();
print a;
b = B.new();
print b;
print a.speak();
print b.speak();

x = 1;
if ( x <= 2 ) print 99;
else print 100;

x=1;
while ( x<=10 ) {
	print x;
	x = x+1;
}

Here is the correct output, which I generate with a little bash FOR loop:

$ for f in t*; do echo "--" $f "--" ; java Test $f; done
-- t1 --
1
-- t10 --
1
2
3
4
5
6
7
8
9
10
-- t2 --
2
1
1
-- t3 --
1
6
40
-- t4 --
<Point:{x=3, y=2}>
3
-- t5 --
<Point:{x=4, y=6}>
-- t6 --
<Point:{x=3, y=0}>
-- t7 --
<Point3D:{x=3, y=4, z=5}>
-- t8 --
<A:{}>
<B:{}>
1
2
-- t9 --
99

Implementation

Support code

Here are the classes I provide for you and a description of what they are for. Please find the support code in the attachment to this page: treeinterp.tar.gz

Address. Elements on the left-hand side of an assignment or written to not read from. Therefore, we must distinguish between getting value of x on the right of an assignment and x on the left-hand side of an assignment. In one case we read from x any other we must write to its memory location. The parser constructs trees like this: ^('=' ^(ADDR ID) expr) for simple assignments like x=expr. For member access assignments, p.x, you get ^('=' ^(ADDR ^(. p x)) expr).

The interpreter must create Address objects to handle ADDR subtrees.

ExecContext. A set of name/value pairs that records global variables, locals, parameters, and even the fields of an instance of an SLObject. These contexts operate like a stack because they know their enclosing context. You can walk up the stack of context, looking for a value.

This is easy to confuse with the scoping objects and semantics. They are obviously related, but for any scope there is exactly one scope object in the symbol table. In contrast, there may be multiple execution contexts for a single scope, such as a function scope. Every function call creates a new execution context (the enclosing context is the previous invocation's context).

FuncExecContext and SLObject are direct subclasses.

FuncExecContext extends ExecContext. Because we do not want dynamic scoping (we want lexical scoping), looking up a local variable should not look of words in the stack past a function call in the stack of execution contexts. Override resolveContext so that, when it is looking for the context holding a local variable, it looks only in the current function execution scope.

Interpreter. This class merely collects a number of the functions that do the work of interpretation. Further, it tracks all of the relevant data such as the symbol table and global context.

ReturnValue. To perform a return statement in SL, we not only need to set a return value but we need to unroll the Java stack as well. The only way to do that is to use an exception. We use a RuntimeException because those are not checked by the Java compiler. Having a checked exception would mean putting a throws claws everywhere.

The exception holds the return value.

We only create one of these because it is the creation of an exception that takes all the time. Throwing the actual exception is quick. You will need a try/catch block around the call to the parser rule that executes the statements of a method.

Interpreter. This class merely collects a number of the functions that do the work of interpretation. Further, it tracks all of the relevant data such as the symbol table and global context.

SLAST extends CommonTree. We need some special fields, so we subclass the normal tree. Consequently, we need to tell the parser about a new tree adapter that you will see in Test. The new tree adapter creates these tree nodes instead of the usual tree node. Also node in a grammar you will see ASTLabelType=SLAST.

SLObject extends ExecContext. All instances of SL classes are instances of this class. They have a pointer to their class definition object so that you can tell what kind of thing it is. You cannot use the Java type system to mirror the SL type system; you would have to create a new class definition for every SL definition in the input stream.

Here is the class hierarchy associated with a symbol table and the execution scopes:

Maintaining current scope

As with your symbol table project, your tree walking phase must keep currentScope field up-to-date by pulling scopes out of tree nodes as it parses. You must be able to reconcile the scopes and execution contexts in your head and in the grammar. Remember that as you walk the tree to execute code, you do not execute function definitions. You execute the body of a method if someone calls that method. In rule func, you will notice I use a wildcard ('.') to skip over the block of function definitions.

Entering a BLOCK subtree is a bit tricky. You are not always returning to enclosing scope (such as the surrounding class) since the interpreter can jump around making method calls to different objects. Save and restore, don't pop scope by setting to currentScope.enclosingScope as you are used to.

Fields

Fields are essentially assignments and, when constructing an SL object, the interpreter must execute these assignments to initialize a class.

Expressions

I have a few actions filled in so you know what to do. Essentially you are evaluating the expression and returning either an Integer, a Boolean, an Address, or an SLObject.

Assignments

The first time x=1 is executed, x must be defined in the current scope unless it is defined above. In rule stat in the assign alternative, add an action to resolve the left hand side if it's a simple ID. If the symbol is not defined, define it in the current scope.

Return statement

Set the value of the returnObject and then throw it. You will need a trick to make Eval.java compile. It will see a throw then a break, which is unreachable. Trick it with a true expression; e.g., the following would compile in a switch:

boolean v=true; if(v) do-something;
break;

Stream indexes

Each node in the tree input "stream" has a unique number, the stream index, that you can use to tell the parser where to jump to. Using ExtendibleNodeStream, I set the stream index of each AST node as it's added to the tree node stream.

Interpreter methods

You must fill in these methods:

public void ifstat(Eval evaluator, Boolean condition, SLAST stat, SLAST elsestat)
  throws RecognitionException
{   
}   
    
public void whilestat(Eval evaluator, SLAST condition, SLAST stat)
  throws RecognitionException
{   
}   
         
public Object call(Eval evaluator, FunctionSymbol sym, SLObject self, List args)        
  throws RecognitionException
{   
}   

public SLObject newInstance(Eval evaluator, ClassSymbol sym, List argsValues)
  throws RecognitionException
{       
}   
    
public void initFields(Eval evaluator, ClassSymbol sym)
  throws RecognitionException
{       
}

Submission

You will create a jar file called interp.jar containing grammars, source, and *.class files and place in your lib directory:

https://www/svn/userid/cs652/proj5/trunk/lib

You can use the svn account for development of the software to if you would like, but I will only be looking at your sym.jar file in the lib directory.

Please bring a printout of Eval.g and Interp.g as well as the output generated from all examples t1-t10.

Grading

Make sure your jar has the Test class in the default package with a main method so that I can test your code. I will run all of the t1-t10 examples through your project.