Re: Interpreter. What is the best way ?

>From article 91-11-048,
by nick@nsis.cl.nec.co.jp (Gavin Thomas Nicol):
> This language will be interpreted, and herein lies the question. For
> this kind of system, is it better to compile the program into bytecode,
> into a parse tree (like gawk), or into tokenised input ? Obviously,
> interpreting the sources directly is NOT the quickest way of doing things.


Bytecodes and parse-trees are good intermediate codes for fast
interpretation. Merely tokenizing the source text is inferior.


Tokenizing the input offers very little compile-time error checking.
Tokenizing the input is very fast, but it means that the interpreter is
    responsible for all syntactic issues (finding the ends of loops, balancing
    parentheses, etc). This means that run-time checks must be included for
    these issues in the interpreter, and this slows things down.


Using a parse tree for the intermediate text avoids the need for any
    syntax checking at run-time. The interpreter can be very fast, but
    if your interpreter is written recursively (the natural approach), then
    you pay the cost of a procedure call and return for just about every
    link in the tree you follow at run-time.
Using a parse tree for the intermediate text makes it awkward to save the
    intermediate text as some kind of object code. It works best in
    environments where the user thinks the source is being directly
    interpreted, while it is actually being compiled and then run by
    a single program that pretends to be a straight interpreter.


Using a bytecode for the intermediate text is the fastest way to make
    an interpreter. You can use indirect chaining for command dispatching,
    eliminating most of the overhead of a centralized fetch-decode routine.
Using a bytecode makes it easy to save the object code between runs.


I've written interpreted systems using both bytecodes and parse trees. My
current impression is that parse trees involve less design work, since the
syntax of the language drives the process, and I don't have to spend the
time designing an abstract machine architecture that I would have to spend
if I used a bytecode. I'd use a parse tree for the prototype, then, if
performance problems dictate a change, go over to the bytecode.


Doug Jones
jones@cs.uiowa.edu
--

Return to the comp.compilers page.
Search the comp.compilers archives again.