[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: Sun, 12 May 2002 16:46:48 -0700

 > Note however, that the default reduction is not internally to Bison,
 > because under POSIX, it should be the first listed action in the input if
 > LALR(1) cannot tell which one it should be. Thus, under POSIX, the input is
 > not a mathematical grammar where the rules are a set, but a well ordered
 > list.

Yeesh; you are demonstrating to me how many different uses of the word
"default" there are in this system!  This is in fact another example 
of what I was NOT talking about.  The default reduction in Bison's
table is the *most common* reduction among all the actions in a
particular state---that is, the reduction that applies to the most
lookahead symbols in that state.  So, for example, in the grammar

           a : b ';' | c '.' | c ',' ;
           b : 'x' ;
           c : 'x' ;

The default reduction (in the sense I was using the term) for the
state containing

            b : 'x' .
            c : 'x' .

is the SECOND one (reducing to c), not the FIRST, because one takes
the second reduction on two symbols ('.' and ',') and the first on
only one (';').

So again, this use of "default reduction" is not easily discernible
from the grammar and is unrelated to the Posix sense.  

 > Perhaps a better error recovery procedure requires the "error" token to be
 > better integrated into the grammar, and then passed through the LALR(1)
 > algorithm: Right now, I suspect that the LALR algorithm tells what should
 > constitute an error, and then the written parser hooks a simplistic error
 > recovery scheme onto that. This then sets some severe limitations on how
 > the error recovery might act.

Well, actually, I think you'll find that the machine generated by
Bison treats 'error' as a perfectly ordinary token.  I only see one
slight adjustment---states that shift the error token don't use a
default reduction (in my sense).  I believe this is to allow parse
errors to be caught a little earlier than they might otherwise be, but
I am not sure how effective it is at that.

The whole algorithm is really rather elegant (at least the official one, as
described in the documentation); it is a pity that it has various
undesirable properties (including a tendency to throw away more text
than necessary).  But I suppose that is simply an example of TANSTAAFL
("There ain't no such thing as a free lunch").

Paul Hilfinger

reply via email to

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