[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Reductions during Bison error handling
From: |
Paul Hilfinger |
Subject: |
Re: Reductions during Bison error handling |
Date: |
Tue, 14 May 2002 15:09:45 -0700 |
HA> Yes, but I was under the impression that that was a part of the LALR
HA> algorithm, see Aho et al, p. 240: "However, when presented with an
HA> erroneous input, the LALR parser may proceed to do some reduction after the
HA> LR parser has declared an error..."
Ah. "Extra reductions" is not part of LALR per se, but rather a SIDE
EFFECT of its lossy table compression scheme---specifically its
merging of lookahead states. The more prominent side effect is that
there are cases where LALR cannot resolve a reduction, but LR can
(granted, these latter are cases that do not seem to materialize in
practice, hence the popularity of LALR). Extra reductions are ALSO a
side-effect of Bison's conflation of error cases with most-frequent
reductions. Alas, I really have no idea how many fewer cases of extra
reductions would occur if we used LR(1) with Bison's table compression
vs. LALR(1) with Bison's table compression.
Paul Hilfinger
- Re: Reductions during Bison error handling, (continued)
- Re: Reductions during Bison error handling, Richard Stallman, 2002/05/14
- Re: Reductions during Bison error handling, Hans Aberg, 2002/05/14
- Re: Reductions during Bison error handling, Paul Hilfinger, 2002/05/13
- Re: Reductions during Bison error handling, Hans Aberg, 2002/05/13
- Re: Reductions during Bison error handling, Paul Hilfinger, 2002/05/13
- Re: Reductions during Bison error handling, Hans Aberg, 2002/05/14
- Re: Reductions during Bison error handling, Paul Hilfinger, 2002/05/14
- Re: Reductions during Bison error handling, Hans Aberg, 2002/05/14
- Re: Reductions during Bison error handling,
Paul Hilfinger <=
- Re: Reductions during Bison error handling, Hans Aberg, 2002/05/15
- Re: Reductions during Bison error handling, Akim Demaille, 2002/05/20
- Re: Reductions during Bison error handling, Paul Hilfinger, 2002/05/21
- Re: Reductions during Bison error handling, Akim Demaille, 2002/05/20
Re: Reductions during Bison error handling, Paul Hilfinger, 2002/05/10
Re: Reductions during Bison error handling, Paul Hilfinger, 2002/05/10
Re: Reductions during Bison error handling, Akim Demaille, 2002/05/20