Re: yacc parse tree (Axel Belinfante)
18 Dec 1998 12:13:00 -0500

          From comp.compilers

Related articles
yacc parse tree (Josh Adams) (1998-12-10)
Re: yacc parse tree (Simon Cozens) (1998-12-13)
Re: yacc parse tree (1998-12-13)
Re: yacc parse tree (1998-12-18)
Re: yacc parse tree (1998-12-18)
Re: yacc parse tree (Josh Adams) (1998-12-19)
Re: yacc parse tree (Joachim Durchholz) (1998-12-19)
Re: yacc parse tree (Sukru Cinar) (1998-12-21)
Re: yacc parse tree (Sukru Cinar) (1998-12-22)
Re: yacc parse tree (Alan H. Martin) (1999-01-02)
Re: yacc parse tree (Sukru Cinar) (1999-01-02)
[1 later articles]
| List of all articles for this month |

From: (Axel Belinfante)
Newsgroups: comp.compilers
Date: 18 Dec 1998 12:13:00 -0500
Organization: Univ. of Twente, Dept. of Computer Science, Tele Informatics group
References: 98-12-018 98-12-022
Keywords: parse, yacc

|> > 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:>. 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).

  <> <URL:>
    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

Post a followup to this message

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