|run parse tree efficiently email@example.com (2004-01-02)|
|Re: run parse tree efficiently firstname.lastname@example.org (Joachim Durchholz) (2004-01-07)|
|Re: run parse tree efficiently email@example.com (2004-01-07)|
|Re: run parse tree efficiently Jeffrey.Kenton@comcast.net (Jeff Kenton) (2004-01-09)|
|From:||firstname.lastname@example.org (Michael Tiomkin)|
|Date:||7 Jan 2004 00:58:06 -0500|
|Posted-Date:||07 Jan 2004 00:58:06 EST|
email@example.com (Chris) wrote in message news:04-01-018...
> 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
Search the comp.compilers archives again.