[antlr-interest] Building an interpreter

[dcmailbag-antlr at yahoo.com]

This a fairly long item regarding using antlr for building interpreters.

I have a situation where I would like to use antlr to build interpeters.  The
examples found do not build interpreters as needed, and I'm hoping someone
can point me to how to do the job.

The problem with the interpreter examples seen is that they require the
ultimate
input stream to the interpreter being constructed be the same stream as the
input to the parser building the interpreter (the token and node streams are
derived from the input stream).

The "Simple tree-based interpreter" (STBI for short) can be used to show the
problem. It is located at

  http://www.antlr.org/wiki/display/ANTLR3/Simple+tree-based+interpeter


The program is first entered followed by the input to that program.  For the
STBI example, the "program" source is

    fact(0) = 1
    fact(n) = fact(n-1)*n
    square(x)=x*x
    catalan(n)=fact(2*n)/square(fact(n))


followed, on the same stream, by the input to the program

    fact(10)
    catalan(10)



Considering a compiled program, the program source is run through the compiler
on one stream, then the compiled program is started and it receives its
input from a different stream. This same needs to be done with the interpreter
-
having to make a new instance of the interpreter for each input expression is
too expensive, and the general problem does not permit feeding all the data as
above with all the output generated at once.  The requirement is to evaluate
something and get a result back before the next item is evaluated.

The following illustrates the concept by modifying the Test2 code from STBI
(please overlook the "you can't do that" detail regarding nodes and go for
understanding the concept)


        ANTLRInputStream input = new ANTLRInputStream(System.in);
        Expr2Lexer lexer = new Expr2Lexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        Expr2Parser parser = new Expr2Parser(tokens);
        CommonTree t  = (CommonTree) parser.prog().getTree();

        CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
        Eval2 evaluator = new Eval2(nodes);

       while(!done) {
          evaluatorprog_ReturnType result;

   	  String evalme = getString();
          result = evaluator.prog(evalme);   /* HERE IS THE ISSUE */
          done = ... ;
       }


Down through "Eval2 evaluator ..." is directly from the STBI example.

While "evalme" is shown as String, it could be any desired appropriate
stream.  The point is that the data stream to the evaluator is different from
the "source code" stream of the evaluator itself.  It is not necessary to
reconstruct the evaluator each iteration - the first one built is reused.

Another case would be a special situation where the invocation is

    result = evaluator.prog();

where there is no input stream, but rather some form of lookup is done.  The
STBI shows this with

    $value = getValue($ID.text);

The while loop shown above would deal with ensuring new values would be
supplied by getValue().  Details of how are not important.

For those wanting a super simplified example of what is being done, the user
would enter a "formula" such as

     2*x*y     (this would be placed on the ANTLRInputStream)

which the interpreter can evaluate, and then the while() loop would iterate
across all values of x and y, with each (x,y) pair's result returned.  The
"done =" calculation would utilize the value of "result".  This example uses
"result = evaluator.prog();" input lookup.

Can anyone point me to an example that shows how to do this?

thanks!