Re: old yacc bug. Fixed?

In article <2737@ima.ima.isc.com>, djones@megatest.uucp (Dave Jones) writes:
> The book [Introduction to Compiler Construction with Unix by Schreiner
> and Friedman] 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?


I can't speak for Sun or Berkeley, but I know that it's fixed on the
version of System V Release 3.0 that I have.


> Some questions"
> 1) How one may determine whether or not a given yacc has the bug?


Try yaccing the following grammar with -v:


%token a
%%
s : oseq
;
oseq : /* empty */
| oseq a
| oseq error
;


and then look at the y.output file. If your yacc has the bug, you will
see a state definition that looks like:


state 2
s : oseq_ (1)
oseq : oseq_a
oseq : oseq_error


error shift 4
a shift 3
. reduce 1


For reference, the correct state definition is:


state 2
s : oseq _ (1)
oseq : oseq _ a
oseq : oseq _ error


$end reduce 1
error shift 4
a shift 3
. error


That is, rule 1 should only be reduced if the next input token is the
end marker. Other input tokens should be considered errors.


> 2) What to do about it if you've got a buggy one?


Complain to your vendor?


> 3) Exactly what are the consequences -- does "go into a loop" mean
> "loop forever"?


I believe it is possible to get into an infinite loop, although I haven't
seen it happen. What I have seen is the same rule get reduced twice
in a row even though the grammar should not allow that to occur.


> 4) What is the correction in 4.1? Is it in the source code?
> 5) What is the typographical error in the correction?


Don't know. I don't have access to any Berkeley stuff.


> 6) What is the "definite correction"? Do you have to have source?


The correction is ridiculously simple if you have the source code - as I
recall it consisted of changing a 2 to a 1 in one place in the code.
Unfortunately, I don't seem to be able to lay my hands on it right now
to give you the details. (I never did understand why S & F didn't just
publish it instead of screwing around like this!)


> 7) How to obtain the correction from the authors?


I wrote a letter to Friedman and asked for it. I'm sure he's on the net,
although I don't have any idea what the address is.


----
Larry Jones UUCP: uunet!sdrc!scjones
SDRC scjones@sdrc.uucp
2000 Eastman Dr. BIX: ltl
Milford, OH 45150 AT&T: (513) 576-2070
"Save the Quayles" - Mark Russell
--

Return to the comp.compilers page.
Search the comp.compilers archives again.