[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
- Reductions during Bison error handling, Paul Hilfinger, 2002/05/09
- Re: Reductions during Bison error handling, Hans Aberg, 2002/05/10
- Re: Reductions during Bison error handling, Paul Hilfinger, 2002/05/10
- Re: Reductions during Bison error handling, Hans Aberg, 2002/05/11
- Re: Reductions during Bison error handling,
Paul Hilfinger <=
- Re: Reductions during Bison error handling, Hans Aberg, 2002/05/13
- Re: Reductions during Bison error handling, Richard Stallman, 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/13
- 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