Re: Better error recovery

Chris F Clark wrote:
> Karsten Nyblad when addressing another topic wrote:
>> At last, I would avoid parser generators that use the error recovery of
>> yacc.
> ...
>> Today you should expect an error recovery to be better at guessing
>> the intentions of the programmer and/or be easier to work with for
>> the compiler writer.
>
> Do you have a specific error recovery method that you could recoomend
> to a parser generator writer? I'm familiar wth yacc error recovery
> and also the insert/delete/replace cost algorithms that came out of
> Charles Fisher's work. However, I've never seen how to customize the
> cost based algorithms other than a table of tokens and costs--or would
> you reccommend such a table?


I would recommend the so called forward move error recovery
mechanisms. They leave the stack unchanged and fix any syntax error
by inserting, replacing, and/or deleting tokens from the list of
tokens not yet parsed. The big advantage of these mechanisms are that
they are easy to work with for the compiler writer.


Recoveries that are not of the class of forward move recoveries may
delete and insert non terminals on the parse stack. When non terminals
are deleted from the stack, the compiler may have to undo work done by
the semantics routines. When non terminals are inserted, the compiler
will have to invent values for attributes attached to the invented non
terminal. Later parts of the compiler will have to deal with non
terminals invented by the error recovery. Thus the code of the compiler
gets more complicated and larger.


The forward move algorithms cannot delete non terminals, and most of
them do not invent non terminals. Thus the compiler gets simpler.


I intend to implement: J. Roehrich: "Methods for the automatic
construction of error correcting parsers," Acta Informatica 13, 115-139
(1980) myself. That recovery is of course forward move. The recovery
has the advantage that it will always recover an error, but it has the
disadvantage that if implemented in an LALR(K) parser generator, the
generator will accept some grammars that are LR(K) but not LALR(K).
Yes, it is old, but it is easy to implement in the parser generator, and
I know it and like it.


I further intend to implement a cost based forward move recovery, but I
have not selected it, and I have not had the time for reading articles
about error recovery for years. Most articles that I have seen, use
Pascal programs written by students a long time ago for making
statistics on how good the new algorithm is compared to older
algorithms. I doubt these statistics can be used today were editors
color keywords, comments, etc. differently, and where programmers do not
write code on punch cards any more. Thus, I intend to implement my
parser generator in such a way that it is possible to experiment with
different error recoveries.


Karsten Nyblad

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