Re: old yacc bug. Fixed?

sdrc! (Larry Jones)
10 Oct 88 22:02:15 GMT

          From comp.compilers

Related articles
old yacc bug. Fixed? djones@megatest.uucp (1988-10-04)
Re: old yacc bug. Fixed? (1988-10-06)
Re: old yacc bug. Fixed? sdrc! (1988-10-10)
| List of all articles for this month |

From: sdrc! (Larry Jones)
Newsgroups: comp.compilers
Summary: Maybe
Keywords: yacc
Date: 10 Oct 88 22:02:15 GMT
References: <>
Organization: Structural Dynamics Research Corp., Cincinnati

In article <>, 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

Post a followup to this message

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