Re: Non-greedy wildcard possible? (Long)

[Frank Heckenbach]

Hans Aberg wrote:

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

Yes, as long as the parser is split. As I said, to the "outside
world" it appears as if the parser uses more lookahead. The amount
of lookahead is generally unbounded, but of course, if you know your
grammar, you can make some statements. (E.g., if splitting can only
occur within expressions, as you can see by looking at the conflicts
in the bison output, things outside of expressions are parsed
normally, so e.g. lexing based on symbol tables would not be
affected.)

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

Sure. I just meant there should perhaps be an example without dprec
as a first step. -- Yes, I know, when I say this, I should rather
write and post such an example. I think I could write a short
example based on Pascal syntax, if wanted ...

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

Of course. OTOH, when we're talking about lexer tricks vs. GLR
parsing, I'm not sure which one is generally preferable. (FTR, I'm
using both, in different cases.)

Frank

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