Re: Usefulness of automatic parse tree generation

"Dave" <better_cs_now@yahoo.com> wrote in message


> I'd like to solicit opinions on a particular idea from people with
> experience in the compilers field.
>
> I'm in the process of writing a generic SLR parser. ...
>
> The question I have is with regard to the output. I'm considering
> also having it output a parse tree. Of course, as a generic library,
> the only thing it could do would be to output a parse tree that
> exactly mimicked the grammar and the particular derivation arrived at.


The DMS Software Reengineering Toolkit does exactly this. It also has
options to build more compressed trees by removing unary productions
and eliminating non-value-bearing terminals. We use the compressed
versions to help us efficiently process very big sets of source files.


At the physical tree level, using the procedural tree interface, these
differences are visible, and it can be problematic to write code to
handle the various representations. For many tasks (especially
information extraction tasks) this really isn't an issue; having a
"GetNthChild" call is useful simply to walk the tree when you are
looking for something, and unary productions and terminals aren't
generally very interesting.


The attribute evaluator and source-to-source rewrite aspects of DMS,
however, offer a compression-independent view of the trees. This is
really nice; you can have compact trees and
  easily derived representation which is useful.


DMS has been used for a variety of software analysis, mass change, and
transformation tasks. So I think it is reasonable to say this is a
useful idea :-)
--
Ira D. Baxter, Ph.D., CTO 512-250-1018
Semantic Designs, Inc. www.semdesigns.com

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