Re: run parse tree efficiently

weltraum@astrocat.de (Chris) wrote in message news:04-01-018...
> hi!
>
> I wrote a little interpreter by hand in c++ (without any tools) and
> use the following technique to run the parse tree: I have an abstract
> class "node" with a method "solve". The real tree nodes overload this
> method, in which the solve methods of the child nodes are called
> "recursively". To run the program the solve method of the main program
> node is called and the rest happens automatically.
>
> I want to know if this is the right/common technique to run a parse
> tree. Is there any other more efficient solution?


    Yes, this is the common technique to run a program defined by an
AST. The method is usually called "compute" or "eval", instead of
"solve". I think it's also the most efficient solution if you have to
use the AST.
    If you are looking for a more efficient solution, you can try
compilation, or compilation to an intermediate language/virtual
machine code, like in Prolog, Java, Python, or a front end of any
compiler, and running the compiled code. BTW, you could save some
effort using parser generator tools, e.g. yacc and lex. I know that
you had a lot of fun making a hand-made parser;-)


> ps. do you know free resources about interpreter design/programming in
> the web, or good books?


    Besides the rarely used feature of evaluating a character string as
a part of your program, there is no difference between interpreted and
compiled languages. For most interpreted languages you can write a
compiler and vice versa (C interpreter is only one example). The
processor in your computer is an interpreter of its command language,
and you can think of compiling a program and running it as running an
interpreter of the language in two steps.
    Any advice on a book on interpreter design would start
a religious war what design/language is better for programming!-)


    You can start from a compiler book and free sources for some
interpreted languages, like awk, Python, or Unix shells.
    For a simple language, too much information can only make writing
an interpreter more complicated.

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