Subj : Re: How-to on writing an interpreter?
To   : comp.programming
From : Rob Thorpe
Date : Sat Jul 16 2005 05:01 am

C. Rebert wrote:
> Actually, I've already taken care of parsing, I'm more in need of how
> to write the interpreter that executes the parse tree.

There are three schemes commonly used:
1 Execute the tree directly
2 Compile the tree into a form of bytecode
3 Compile procedures into executable code, then branch to them.

#3 is compilcated and not necessary unless you need the speed

#2 is also quite complicated, it boils down to:
  * Compile code for a fictional processor
    (normally a simple stack machine)
  * Emulate that processor
This is too complex to explain briefly.
To learn how to do this read the Dragon book by Aho, Sethi & Ullman
that Richard Heathfield mentioned.
Anton Etrl's home page also has some useful information:
www.complang.tuwien.ac.at/projects/interpreters.html
(Anton Etrl and Bernd Paysan wrote the GNU forth interpreter)


#1 is probably the simplest
The strategy used here is to make the tree something like this: -

    |---------------------|------------|
    |                     |            |
    |------|----|----|    |            |
 command1 arg1 arg2 arg2) |            |
                          |            |
                          |------|     |---|------------|-------|
                       command2 arg4   if  |           arg5   arg7
                                           |
                                           |--------|
                                          command3  arg6
("if" here is just another command)

then interpret it using something like this:

for (;;) {
   <Get the next node on the tree>
   <Find subroutine corresponding to the command>
   <call this interpreter recursively to evaluate the arguments>
   <call subroutine with arguments>
}

The simplest examples of #1 are interpreters for lisp-like languages
like scheme.  One of the simplest examples is: -
http://ganley.org/software/jslisp.html

See especially the subroutine JslEval

.