Re: Non-greedy wildcard possible? (Long)

[Hans Aberg]

At 00:43 +0200 2004/05/27, Frank Heckenbach wrote:
>> The problem with GLR is that when an LALR(1) ambiguity appears, it merely
>> splits up the parser to handle all the possibilities. The one writing the
>> parser then has to add code to treat these ambiguities.
>
>Only for real ambiguities. Grammars that just require further
>look-ahead than LALR(1) (or in fact than LALR(k) for any k) can be
>parsed with GLR without any explicit user code.

I should have said that if all but one parse dies, the surviving one will
be selected.

>> Also, when an ambiguity appears in the input, then the GLR parser does not
>> resolve it by asking for more tokens, but merely splits the parser,
>> processing each possibility.
>
>True. What I was saying is that from the lexer's (say) point of view
>it's the same as asking for more look-ahead tokens: While the parser
>is split, it doesn't perform any actions, so in particular it can't
>influence the lexer (whether by direct tie-ins or by putting things
>in a symbol table or whatever). So, even though the parallel parsing
>is proceeding, the lexer (and any part of the program outside of the
>parser) just sees the parser consuming more and more tokens.

This is though an important point: That no parser actions are performed
during the split, and in particular that the lexer cannot be fed back from
the parser, then. This is then also true about non-ambiguous parsing.

>> Each possibility is still though all the same
>> old LALR(1). So you do not automatically climb LR(k) by this method, but
>> one still has to indicate how to merge the different possibilities. There
>> is an example in the Bison manual when this might be useful, resolving a
>> certain C++ ambiguity.
>
>GLR can indeed parse any non-ambiguous CFG without any extra code.
>(At the cost of possibly degraded performance, only in cases that
>LALR(1) can't handle, worst-case exponential, but in practice
>usually benign.)
>
>Explicit merging and dprec are *additional* features that help
>parsing even somewhat ambiguous grammars.
>
>So perhaps the C++ example in the manual is not the best one
>possible for a start since it's "step 2".

The C++ example is important, because it shows how GLR can be used to
resolve run-time parsing ambiguities.

>Perhaps these explanations might help alleviate your averseness to
>GLR (as it sometimes appears).

I merely want folks to investigate the standard methods with tweaks in full
first, and most of all, not hoping that any more advanced parsing method
should save them from doing the grammar writing job themselves. We have had
cases in this list in the past where the problem was in reality due to
sloppy grammar analysis; then GLR won't save you.

  Hans Aberg