Re: yacc parse tree

|> > pretty simple. Each rule takes the subtrees from its subrules and
|> > tokens and builds a tree for that rule and returns it as $$. When you
|> > get to the top, you have a parse tree. The most annoying part is
|> > allocating and deallocating the tree nodes, particularly if you want
|> > to recover from parse errors.
|>
|> I imagine Knuth would have a clever data-structure based solution to this
|> one - is anyone aware of any work done on the idea of the parser
|> constructing a *tree of trees*?
|> --
|> [Any tree is a tree of trees, it's a recursive data structure. No
|> cleverness required here. -John]


Hmm. Even though no cleverness is needed, writing the data-structures
and (de)allocation routines (in C) can be tedious work, work that can
be automated... :-)


Maybe our 'term-processor' Kimwitu can be of some help here. The idea
is that you can give it a grammar description of your tree structure,
from which it generates data-structures to hold the nodes, and
functions to allocate and deallocate the nodes. It can nicely be used
to create a tree representation of something that you parse with yacc
(kimwitu generates the YYSTYPE needed).


To access the tree you can write C functions in which you can use
patterns over the tree, you can specify unparse rules, and you can
specify rewrite rules for the (simple) rewriter. (and of course it
can do even more than this :-) (one of the more clever things that it
has is an option that
  can be turned on for each non-terminal of the tree grammar,
  that tells it to share common subtrees - together with their
  attributes)(something that it misses is an attribute evaluator)


For more information see <URL:http://fmt.cs.utwente.nl/kimwitu/>. If
you have questions or remarks about it, please feel free to contact me
(or follow-up in this group for things of general interest).


Axel.
--
  <Axel.Belinfante@cs.utwente.nl> <URL:http://www.cs.utwente.nl/~belinfan/>
    University of Twente, Dept. of C.S., Formal Methods & Tools Group
  P.O. Box 217; NL-7500 AE Enschede. Phone: +31 53 4893774; Fax: +31 53 4893247

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