Re: Parser Error Detection and Recovery

>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.
--

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