On 15 Mar 2006, at 01:24, Sylvain Schmitz wrote:
So, as for LR(1), I guess for typical grammars there will be a
blow- up a couple of times of the number of states. If there is a
problem with exponential blowups, one might perhaps try the same
approach, make a grammar to non-deterministic automata
translation, with a runtime component computing the final
deterministic push-down automaton states at need, caching them.
I have never seen this kind of implementations either. I can see
one reason for that: when we construct the deterministic handle
finding automaton, we also get information on whether the LR parser
is deterministic or not, and on where the conflicts are.
One could perhaps use a LR(1) testing algorithm, which is
supposed to be much less costly than the complete parser
generation, to check whether the determinization will work or not---
I don't know enough about these tests to tell whether they also
give you where the conflicts occur---
This would anyhow be a later stage, after a traditional LR(1)
implementation has been put into Bison as an option for awhile. I
just mention the possibility, as it opens up for interesting hybrids,
perhaps in connection with GLR, which uses a different method for
handling non-deterministic parsing.
and do the NFA to DFA translation on parsing time like you suggest.
It is dangerous to use the wording "NFA" and DFA" here, as it is push-
down automatons using a stack.
A second reason is simply that, for purely parsing purposes---
that is, ignoring the advantages you already mentioned, like
correct prefix + lookahead---, we do not need the full-blown LR(1)
automaton; its compressed form works just fine; even the weaker LALR
(1) parser is good enough in most cases. The space constrains
experienced in the days where LR parsing was invented did not leave
much choice on the matter.
As for Bison, I think it should at some point in the future have a
LR(1)
feature, so that one at least can experiment with it.
Indeed, you now have the choice.
This is the one major reason for putting it in: these days even
personal computers do not have space problems having it. So starting
to use it, will give inputs of its usability.
Hans Aberg
_______________________________________________
[email protected] http://lists.gnu.org/mailman/listinfo/help-bison
