Re: run parse tree efficiently (Michael Tiomkin)
7 Jan 2004 00:58:06 -0500

          From comp.compilers

Related articles
run parse tree efficiently (2004-01-02)
Re: run parse tree efficiently (Joachim Durchholz) (2004-01-07)
Re: run parse tree efficiently (2004-01-07)
Re: run parse tree efficiently (Jeff Kenton) (2004-01-09)
| List of all articles for this month |

From: (Michael Tiomkin)
Newsgroups: comp.compilers
Date: 7 Jan 2004 00:58:06 -0500
References: 04-01-018
Keywords: interpreter
Posted-Date: 07 Jan 2004 00:58:06 EST (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.

Post a followup to this message

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