drt@notecnirp.Princeton.EDU (David Tarditi) (07/31/89)
I've been working on a Yacc-like parser generator for the language ML
for a while now. Here is my suggestion on improving Yacc's error-recovery
based on what we've actually implemented.
The idea of adding a 'yyexpected' function might sound good at
first, but there are a number of problems with it. As was pointed out
before, the number of expected terminals will probably be quite large,
as this will include terminals on which a shift is possible and
terminals on which a reduction is possble. For a grammar for Pascal,
for example, this could be 30 or more terminals in some spots. Also,
you would probably have to modify the Yacc source code to do this
because Yacc inserts default reduction actions. These default
reduction actions eliminate the lookahead information associated with
reductions.
Anybody interested in improving Yacc's error recovery should read
'A practical method for LR and LL syntactic error diagnosis and recovery',
M. Burke and G. Fisher, ACM Transactions on Programming Languages and
Systems, Vol. 9, No. 2, April 1987, pp. 164-197.
This article describes how to write a parser which recovers
automatically in a table-independent manner from parsing errors.
I've implemented some portions of the algorithm described there, and
it seems to work well.
I don't know if this helps the original poster much. It certainly
would take more work to implement this algorithm than the poster intended to
put into error recovery. For those who *really* want to improve
Yacc's error recovery, I would suggest taking a serious look at this
paper.
----------------
- David Tarditi (drt@notecnirp.princeton.edu)
--
--
Send compilers articles to compilers@ima.isc.com or, perhaps, Levine@YALE.EDU
{ decvax | harvard | yale | bbn }!ima. Meta-mail to ima!compilers-request.
Please send responses to the author of the message, not the poster.