Re: Non-greedy wildcard possible? (Long)

[Frank Heckenbach]

Hans Aberg 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.

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

> 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".

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

Frank

-- 
Frank Heckenbach, address@hidden
http://fjf.gnu.de/
GnuPG and PGP keys: http://fjf.gnu.de/plan (7977168E)