On 1 Apr 2007, at 20:17, Joel E. Denny wrote:
If there is a choice. And which variation of LR(1) would you
prefer, if there
now is a difference: One that compacts the states and still has
the same
problem as LALR(1) that when an error token comes by, some actions
can be
performed before the error is being reported plus it cannot be
used in
interactive scanners to report possible token completions,
I'm focusing on that one.
or one that does
not have those flaws, but takes up perhaps much more space?
I'm thinking there could be an option to modify the definition of
state
compatibility so that Bison can generate either canonical or
compact LR(1)
tables. Assuming the compact LR(1) works out as I hope, canonical
LR(1)
would be interesting to me purely for an efficiency comparison.
Since a problem with LALR(1) is poor error handling, I think one
should be able to turn state merging off. This will also be required
if one wants each state to tell the correct set of possible
completion tokens, as in some interactive parsers. The latter was
discussed on some Bison list (perhaps for GNU readline).
I'm very much still in the planning stages, so don't hold me to any of
this.
There is also a dynamic variation: One sets a maximum of states. If
the number of states does not exceed that, one gets a static
implementation. If they exceed that limit, one instead implements a
parser able to compute new states on the fly.
It is mentioned in the book by Aho, Sethi & Ullman,
"Compilers..." (the "dragon book"), that for a NFA to DFA
translation, such a dynamic translation can avoid the exponentiality
that may happen in a static compilation. Since LR(1) proper can also
generate exponential amounts of states, this might be something
consider as an alternative to state merging. I do not know the theory
of it. I just mention this "just in case".
Hans Aberg
_______________________________________________
[email protected] http://lists.gnu.org/mailman/listinfo/help-bison
