[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Performance impact of "redundant" rules
From: |
Hans Aberg |
Subject: |
Re: Performance impact of "redundant" rules |
Date: |
Sat, 11 Mar 2006 21:20:29 +0100 |
On 7 Mar 2006, at 18:42, Sylvain Schmitz wrote:
bison uses an excellent LALR(1) implementation based on DeRemer and
Pennello's work.
This reference is mentioned in the Aho et al. "Compilers..." book,
but it does not say if it is what is described in its text.
It relies solely on the LR(0) automaton; the LR(1)
"stuff" is never computed.
OK.
But you seem to say, that parser generation phase might then
become too big.
I think it's big, and the menhir implementors seem to agree.
OK. That is something to look up, would Bison be given an LR(1) option.
LR(1) becomes interesting from unexpected corners: efficient
error generation and parser that need to display token
lookaheads, which LALR(1) deliberately both corrupts in its
optimizations.
I'm not fully convinced of the interest of the "valid prefix +
lookahead" property of LR(1) versus the simple "valid prefix" of LR
(0).
It is just a question of being able to capture all the LALR(1)
grammars at least.
Anyway, this advantage disappears if we start merging states in the
LR(1) automaton ...
Right. One can though think of a LALR(1) that somehow records the
proper LR(1) tokens just for such purposes.
What is the reason performance drops especially in GLR?
Too many states means less chances of merging concurrent stacks. One
could also point out that less inadequate states means less branching,
but the number of inadequate states avoided when using LR(1)
instead of
LALR(1) is not very big, whereas the difference in automaton size is
exponential.
I am not aware of this exponentiality: The Aho [loc.cit.] just gives
a percentage on typical parsers.
Thus LR(1) is much more practicable if you merge states.
The question will be to find compaction methods that does not destroy
the immediate reaction to wrong tokens, and can provide the proper
set of valid lookahead tokens.
Hans Aberg
- Performance impact of "redundant" rules, Frans Englich, 2006/03/06
- Re: Performance impact of "redundant" rules, Sylvain Schmitz, 2006/03/06
- Re: Performance impact of "redundant" rules, Frans Englich, 2006/03/06
- Re: Performance impact of "redundant" rules, Hans Aberg, 2006/03/07
- Re: Performance impact of "redundant" rules, Sylvain Schmitz, 2006/03/07
- Re: Performance impact of "redundant" rules, Hans Aberg, 2006/03/07
- Re: Performance impact of "redundant" rules, Sylvain Schmitz, 2006/03/07
- Re: Performance impact of "redundant" rules,
Hans Aberg <=
- Re: Performance impact of "redundant" rules, Hans Aberg, 2006/03/14
- Re: Performance impact of "redundant" rules, Sylvain Schmitz, 2006/03/14
- Re: Performance impact of "redundant" rules, Hans Aberg, 2006/03/15
- Re: Performance impact of "redundant" rules, Akim Demaille, 2006/03/08