Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!olivea!mintaka!spdcc!iecc!compilers-sender
From: megatest!djones@decwrl.dec.com (Dave Jones)
Newsgroups: comp.compilers
Subject: Re: Parser Error Detection and Recovery
Keywords: yacc, errors, debug, code
Message-ID: <16499@prometheus.megatest.UUCP>
Date: 1 Apr 91 23:29:25 GMT
References: <1796@bbxsda.UUCP> <16273@prometheus.megatest.UUCP>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: megatest!djones@decwrl.dec.com (Dave Jones)
Organization: Megatest Corporation, San Jose, Ca
Lines: 81
Approved: compilers@iecc.cambridge.ma.us

>From article <1796@bbxsda.UUCP>, by scott@bbxsda.UUCP (Scott Amspoker):
> In article <16273@prometheus.megatest.UUCP> djones@megatest.com (Dave Jones) writes:
>>However, the original yacc has a bug related to default-reductions which
>>makes proper error-recovery impossible: It creates states with default
>>reductions and a shift-action on "error". The bug is a typo. ...
> 
> That might explain some problems I've been having.  Can somebody post (or
> mail) a short yacc file that demonstrates the problem?  I need to determine
> if the yacc I am using has this bug.

You bet.

Before I get into that, I would like to thank Sun Microsystems. I reported
the bug to them a year or two ago, and in the letter explained how to
change the "1" into a "2" to make it work. Knowing as I do about priorities
at computer companies and "hot" projects, I expected that to be the
end of it; I never expected to see it fixed, even though it was a one-
character change to the source file. We have a source licence from BSD,
so I fixed it myself. But just now I checked out the Sun version, and
by golly, they fixed it. Amazing.

It is also a little amazing that in the years from 1983 and 1989,
the bug went unfixed and probably unnoticed. I guess the grammar-writers just
shook their heads and figured there was something about it they did not
understand.

Luckily, when I researched this before I made up and saved a test case.
Here 'tis.

botch.y
^^^^ snip ^^^^ snip ^^^^ snip ^^^^ snip ^^^^ snip ^^^^ snip ^^^^ snip ^^^^

	%token SYM
	%%
	start  : list
	       ;

	list : /* empty */
	     | list SYM
	     | list error
	     ;

^^^^ snip ^^^^ snip ^^^^ snip ^^^^ snip ^^^^ snip ^^^^ snip ^^^^ snip ^^^^


To test a yacc as to whether it has the bug, do a "yacc -vd botch.y",
and look at the y.output file. If you see a state which can shift "error",
but has a default reduction, you have a buggy yacc.

   Example of BUGGY y.output:

    state 2
        start :  list_    (1)
        list :  list_SYM
        list :  list_error 

        error  shift 4
        SYM  shift 3
        .  reduce 1

It would appear that it can shift to state 4 on a (synthesized) error token,
but in fact it will do the default reduction (reduction 1) before
the error-token can be synthesized by the parser.

A properly working yacc would produce the following:

    state 2
        start :  list_    (1)
        list :  list_SYM
        list :  list_error 

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

Notice that the default action is "error", not a reduction. The
error-action synthesizes the error-token, which can then be shifted.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.