Re: Usefulness of automatic parse tree generation

"Carl Cerecke" <cdc@maxnet.co.nz> wrote in message


> > I'm in the process of writing a generic SLR parser. It takes as input
> > SLR parsing tables and a string to be parsed.
>
> If its input is parse tables, then there is very little work to make it
> LALR or full LR(1) as well. The big difference between SLR, LR, and LALR
> is in the table generation, not the actual parsing machinery.
>
> > So, my question is: How useful would my idea be? In what contexts
> > would it be useful to have a tree that mimicked the grammar and a
> > particular derivation with that grammar?
>
> Useful for educational purposes. And, perhaps, small simple grammars.
>
> > In what contexts would it not be useful?
>
> Anywhere were a sensible syntax-tree is preferred (e.g.
> compiler/translator). Because, I am assuming, the parse tables that
> are your parser's input don't have abstract syntax tree (AST)
> directions, you'd be stuck with massive trees.
>
> I wrote a parser-generator once that automatically created ASTs, and
> struck this very problem. I had to add AST directions to the
> parser-generator input file to get a sensible sized-tree that I could
> walk over in a reasonable time. It was a huge language though -
> produced a parsing automata 4 times the size of Java.
>
> > Is it worth implementing?
>
> Sure. Go for it.
>
> Cheers,
> Carl.


I've thought about the LALR thing you mentioned. I'm also generating
the parse tables (separate library from the parser), so that's where
the change would need to be. How difficult is it to upgrade an SLR
table generator to an LALR table generator?


I've also been thinking more about the parse tree vs. syntax tree
thing. I would like to automate the transformation of a parse tree
into a syntax tree. But it's not clear to me if this can be done by
simply collapsing long chains of unit productions or not. There might
be more to it to generate a minimal and completely natural syntax
tree. It may be that the user of the library needs to provide rules
for the transformation. If so, what would these rules look like? I'd
love to hear from anybody that has experience in doing this and can
offer sound guidance!


Thanks,
Dave
[I think you need explicit hints in the grammar to produce an AST, so
you can tell the difference between, say, (exp) which is just grouping
and [exp] which is a unary operator. -John]

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