Path: utzoo!utgpu!water!watmath!clyde!ima!compilers-sender
From: sdrc!scjones@uunet.uu.net (Larry Jones)
Newsgroups: comp.compilers
Subject: Re: old yacc bug. Fixed?
Summary: Maybe
Keywords: yacc
Message-ID: <2767@ima.ima.isc.com>
Date: 10 Oct 88 22:02:15 GMT
References: <2737@ima.ima.isc.com>
Sender: compilers-sender@ima.ima.isc.com
Reply-To: sdrc!scjones@uunet.uu.net (Larry Jones)
Organization: Structural Dynamics Research Corp., Cincinnati
Lines: 90
Approved: compilers@ima.UUCP

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
--
Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.EDU
Plausible paths are { decvax | harvard | yale | bbn}!ima
Please send responses to the originator of the message -- I cannot forward
mail accidentally sent back to compilers.  Meta-mail to ima!compilers-request