[DGD] Re: Parsing grammar problem

[Felix A. Croes]

Reimer Behrends <behrends at student.uni-kl.de> wrote:

> On Sat, May 30, 1998 at 11:20:36PM -0500, Jason Cone wrote:
> > As sure as I am that the grammar's more or less correct, it's entirely
> > possible that something's not quite right with it.  That's why I'd like
> > feedback on it.
> [...]
> >   element_list: element_list ',' element_list
> [...]
> >   assoc_element_list: assoc_element_list ',' assoc_element_list
>
> I haven't yet looked at the parsing algorithm in some depth, but the two
> rules above produce a lot of ambiguous parsings (for instance, A, B, C
> can be parsed as both (A, B), C and A, (B, C) -- with the number of
> possible parses being of order O(exp(n)), where n is the list length. At
> the very least that's not desirable, and probably the cause of your
> troubles, too.

The parsing algorithm will attempt to handle all possible alternative
parse trees in parallel.  For the rules above, the amount of
alternatives increases exponentially with the number of elements in
each list.

See dgd/doc/parser, near the end, for an example of how to write the
grammar in a non-ambiguous way.  The same document also describes
how you can detect ambiguity in a grammar.

Dworkin