RE: run parse tree efficiently

Chris asked:


> [I traverse a tree of objects derived from an abstract base "node" class.]
> I want to know if this is the right/common technique to run a parse
> tree. Is there any other more efficient solution?


It certainly is one of the ways it's done. If the language being
interpreted allows for function calls into dynamically defined
functions that are also part of the tree, you have two choices:
resolve the graph at compile time, and store pointers into the first
executable node of the functions to be executed, or resolve them at
call-time (or some combination of the two methods that resolves them
on first-call and saves the result for later).


The virtual function on objects approach you've taken has the benefit
of encoding the node type at compile time, rather than execution time,
but might make optimization techniques a bit tricky (not impossible,
just tricky).


As for efficiency ... I would only be guessing, but my guess is that
it is one of the most efficient ways to interpret a tree, but not one
of the most efficient ways to use memory. It has as one of its main
benefits an automatic use of the stack, thereby freeing you from
explicit stack management. Ask yourself how you will unwind the stack
if something akin to a "quit" imperative is reached X (for some deep
value of X) levels deep, however. Do you just return successively from
each call, right to the top node, or do you throw an exception and let
the compiler do the object destruction? Both methods have their
pros/cons.


--
Quinn Tyler Jackson


http://members.shaw.ca/qjackson/

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