[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Reductions during Bison error handling

From: Hans Aberg
Subject: Re: Reductions during Bison error handling
Date: Wed, 15 May 2002 11:24:34 +0200

At 15:09 -0700 2002/05/14, Paul Hilfinger wrote:
>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.

Perhaps people differ about what LALR(1) really is -- this might have some
importance for POSIX, which requires LALR(1). At least, one can from POSIX
not expect a certain specified behavior when an error occurs, at least with
respect to eny eventual reductions before the error is detected.

>  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.

There was a case in the Help Bison group, in the thread "Not getting parse
error", where a guy put in several "return 0" into the actions, and then
the Bison parser would not report errors. Now, in the Bison parser, the
action "return 0" is in effect equivalent to "abort, returning 0". So what
happens is that when an error happens, the parser first performs some
reductions, doing a "return 0" before the actual parse error is detected.
This a freak thing though, because one should not use "return 0" in the

  Hans Aberg

reply via email to

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