[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: Mon, 13 May 2002 14:25:34 -0700

HA > We only crossed over the following concepts:

HA > 1. Default reduction.
HA >   a. The reduction marked $default in the .output file.
HA >   b. In a reduce/reduce conflict, which rule to use as default.
HA > 
HA > 2. Default action (when the action is left out at a rule in the .y file).

And 1a should NOT be documented, since it is purely a matter of
implementation and ought to be open to change.

HA > I am not sure why 1a must always be a reduction (why cannot there be a
HA > default shift?). But anyway, it depends on the LALR(1) algorithm it seems
HA > me, and on not error recovery as a part of the grammar only.

Default shifts wouldn't work too well---shifts are deterministic and
each state has a single accessing symbol, and therefore there can be
only one shift or goto entry in a state that leads to any other given
state.  A default that applies only to one entry isn't too useful!

HA > If one should be specific, then perhaps 1b should be called the
HA > reduce/reduce conflict default reduction, and 1a the LALR(1) algorithm
HA > default reduction. (The reduce/reduce conflicts one gets depend on the
HA > parsing algorithm, too, but this is not something specified by the
HA > algorithm directly; so 1b is a way to cover up where the algorithm fails,
HA > and is thus not an "LALR(1) algorithm default reduction".)

As I said, 1a should not be documented in a user manual.  

BTW, I think I should comment on this LALR/LR thing.  I don't believe
this issue has anything to do with the distinction between LR and LALR
parsers.  Both use identical parsing algorithms and identically
formatted tables.  LR(1) grammars that are not LALR(1) are rather rare
in practice (indeed, I've never seen a spontaneous example, just
contrived textbook examples, but of course I'm not a parser
specialist, so my experience is limited).  Item 1a has only to do with
an optimization device applicable to either type of grammar that
(unfortunately) happens to become obscurely visible (now THERE'S a
true oxymoron for you) in the presence of erroneous input.

Paul Hilfinger

reply via email to

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