Simple tree-based interpeter - ANTLR 3 wiki

Requires 3.0b6 or beyond, which added some required functionality.

This is a slightly tweaked version of http://www./wiki/display/ANTLR3/Expression+evaluator that adds simple function definitions; these files are uploaded as attachments to this page as well as shown as text here. Here is some sample input:

f(x) = 2*x
g(x) = 10*x
f(3)
f(g(3))

and here is the output using the test rig below:

$ java Test < input
(FUNC f x (* 2 x))
(FUNC g x (* 10 x))
(CALL f 3)
(CALL f (CALL g 3))
6
60

The basic idea is that the parser now maps function names to tree nodes and then the tree grammar will look up those functions when it sees a CALL expression. The evaluator (tree grammar) still has a memory HashMap, but now it is part of a stack of value scopes so that I can ask for a value with getValue(String name) and it will look in all of the value scopes for a value (all the way to memory map if necessary). We need a stack so that f(g(3)) works etc... HOWEVER, note that we are not doing dynamic scoping. Look only at stack top for value of an arg or jump to memory looking for the value. In our case, there is no way to set any of those intermediate values, but I‘m not looking in all the scopes just to be safe.

Here is the modified parser that defines functions and also tracks their node pointers for later use by the tree-based interpreter:

grammar Expr;
options {
output=AST;
ASTLabelType=CommonTree; // type of $stat.tree ref etc...
}
tokens {FUNC; CALL;} // define pseudo-operations
@header {
import java.util.HashMap;
}
@members {
/** Map function name to tree node where it is defined.
*  Must point at the FUNC node.
*/
HashMap functions = new HashMap();
}
// START:stat
prog:   ( stat {System.out.println($stat.tree.toStringTree());} )+ ;
stat:   expr NEWLINE        -> expr
|   ID ‘=‘ expr NEWLINE -> ^(‘=‘ ID expr)
|   func NEWLINE        -> func
|   NEWLINE             ->
;
func
@finally {
functions.put($name.text, $func.tree); // track name->tree node
}
:   name=ID ‘(‘ arg=ID ‘)‘ ‘=‘ expr -> ^(FUNC $name $arg expr)
;
// END:stat
// START:expr
expr:   multExpr ((‘+‘^|‘-‘^) multExpr)*
;
multExpr
:   atom (‘*‘^ atom)*
;
atom:   INT
|   ID
|   ‘(‘ expr ‘)‘    -> expr
|   ID ‘(‘ expr ‘)‘ -> ^(CALL ID expr)
;
// END:expr
// START:tokens
ID  :   (‘a‘..‘z‘|‘A‘..‘Z‘)+ ;
INT :   ‘0‘..‘9‘+ ;
NEWLINE:‘\r‘? ‘\n‘ ;
WS  :   (‘ ‘|‘\t‘)+ {skip();} ;
// END:tokens

The tree grammar is basically the same except for function definition and call statements. Note, however, that the tree grammar only evaluates expressions and so we want to make sure that the function definition alternative does not actually invoke rule expr. The alternative looks like:

    |   ^(FUNC name=ID arg=ID .)

The wildcard says skip the entire subtree (new in 3.0b6).

Upon a CALL expression, lookup the function name in the functions table and get the FUNC node. Ask the stream for the index of that AST node then jump to the index of the expr part of the FUNC. Use push/pop to save and restore the current stream index. To invoke rule expr, just call expr().

Here is the entire tree grammar that does evaluation:

tree grammar Eval;
options {
tokenVocab=Expr;
ASTLabelType=CommonTree;
}
// START:members
@header {
import java.util.Map;
import java.util.Stack;
import java.util.HashMap;
}
@members {
/** Map variable name to Integer object holding value */
Map memory = new HashMap();
/** Points to functions tracked by tree builder / parser. */
HashMap functions;
/** Stack of value scopes.  Stack<Map>; each map holds set of
*  name/value pairs.
*/
Stack scopes = new Stack();
/** Get value of name.  Either on top of stack as arg or in memory. */
public int getValue(String name) {
Map values = (Map)scopes.get(scopes.size()-1);
Integer vI = (Integer)values.get(name);
if ( vI!=null ) {
return vI.intValue();
}
vI = (Integer)memory.get(name);
if ( vI!=null ) {
return vI.intValue();
}
// not found in any scope including global memory
System.err.println("undefined variable "+name);
return 0;
}
}
// END:members
// START:rules
prog
@init {
scopes.push(memory); // push memory as outermost scope
}
:   stat+ ;
stat:   expr
{System.out.println($expr.value);}
|   ^(‘=‘ ID expr)
{memory.put($ID.text, new Integer($expr.value));}
|   ^(FUNC name=ID arg=ID .)
;
expr returns [int value]
:   ^(‘+‘ a=expr b=expr)  {$value = a+b;}
|   ^(‘-‘ a=expr b=expr)  {$value = a-b;}
|   ^(‘*‘ a=expr b=expr)  {$value = a*b;}
|   ID                    {$value = getValue($ID.text);}
|   INT                   {$value = Integer.parseInt($INT.text);}
|   call                  {$value = $call.value;}
;
call returns [int value]
@init {
Map argScope = new HashMap();
scopes.push(argScope); // push new arg scope
}
@finally {
scopes.pop();          // remove arg scope
}
:   ^(CALL ID expr)
{
CommonTreeNodeStream stream = (CommonTreeNodeStream)input;
CommonTree funcRoot = (CommonTree)functions.get($ID.text);
int addr = stream.getNodeIndex(funcRoot);
if ( addr>=0 ) {
CommonTree argNode = (CommonTree)funcRoot.getChild(1);
String argName = argNode.getText();
int exprIndex = addr + 4; // skip over FUNC DOWN ID ID to expr
argScope.put(argName, new Integer($expr.value));
((CommonTreeNodeStream)input).push(exprIndex);
$value = expr(); // invoke expr and set CALL‘s value
((CommonTreeNodeStream)input).pop();
}
else {
System.err.println("no such function: "+$ID.text);
}
}
;
// END:rules

Here is a simple test rig:

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
public class Test {
public static void main(String[] args) throws Exception {
ANTLRInputStream input = new ANTLRInputStream(System.in);
ExprLexer lexer = new ExprLexer(input);
CommonTokenStream tokens = new CommonTokenStream(lexer);
ExprParser parser = new ExprParser(tokens);
ExprParser.prog_return r = parser.prog();
// walk resulting tree
CommonTree t = (CommonTree)r.getTree();
CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
nodes.reverseIndex(ExprParser.FUNC);
Eval walker = new Eval(nodes);
walker.functions = parser.functions;
walker.prog();
}
}