[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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]