|old yacc bug. Fixed? firstname.lastname@example.org (1988-10-04)|
|Re: old yacc bug. Fixed? email@example.com (1988-10-06)|
|Re: old yacc bug. Fixed? firstname.lastname@example.org (1988-10-10)|
|From:||email@example.com (Dave Jones)|
|Date:||4 Oct 88 22:00:51 GMT|
|Organization:||Megatest Corporation, San Jose, Ca|
I'm in the process of writing a compiler using yacc. A fellow worker
loaned me "Introduction to Compiler Construction with Unix"
by Axel T., Schreiner and H. George Friedman, Jr., Prentice Hall, 1985,
so I've been trying to read it.
The book alludes to a bug in yacc. The main thing I want to know is
whether the Sun Unix 4.2 release 3.4 has the bug, and if so what do
I do about it?
They give some examples of using the "error" token, with the following
footnote, which I quote verbatim:
This way of extending repetative constructs has a drawback due to
a bug in yacc ( as distributed with Bell version 7, Berkeley
4.2bsd [sic], and various derivatives): if in a state the default
action is to reduce, and if the next terminal symbol cannot be
shifted but _error_ could be (e.g., on a trailing _error_ rule),
yacc's tables dictate that the reduction take place, event if the next
terminal symbol cannot be shifted subsequently. In this case error
recovery takes place "too late", and the parser can, in fact, go
into a loop, mistakenly reduce rules several times, etc. The
4.1bsd [sic] distribution actually contains a correction for this
bug, based on ["Practical LR error recovery", Sigplan Notices,
Aug. 79]. Essentially, in these cases all possible inputs must be
enumerated, so that the error can be detected; this results in
slightly larger parser tables. The correction in 4.1bsd [sic]
contains a typographical error, however. A definite correction
is available from the authors (S. Johnson, personal
Notice that it says the bug is fixed in 4.1 but not 4.2, except
that the fix is wrong! At least that's the interpretation I put on it.
Can anyone make heads or tails of this gobblety-gook? (I love that
"in fact" part.)
1) How one may determine whether or not a given yacc has the bug?
2) What to do about it if you've got a buggy one?
3) Exactly what are the consequences -- does "go into a loop" mean
4) What is the correction in 4.1? Is it in the source code?
5) What is the typographical error in the correction?
6) What is the "definite correction"? Do you have to have source?
7) How to obtain the correction from the authors?
The best try I can make is that maybe one could expect to see
entries of this form:
X : Y _ error (6)
Z : A _ (5)
error shift 4
. reduce 5
And in this case the parser would reduce by rule 5, when shifting
_error_ is in order. But I can't find any such states in any
output I can generate. Besides, this would just cause some extra
input to be thrown away. The parser would not get into a loop
or make extra reductions.
[From firstname.lastname@example.org (Dave Jones)]
Return to the
Search the comp.compilers archives again.