Re: recursive-descent (and LR) error recovery

harvard!ut-sally!utah-cs!sandra (Sandra J Loosemore)
Sat, 15 Aug 87 22:23:20 MDT

          From comp.compilers

Related articles
Re: recursive-descent (and LR) error recovery harvard!ut-sally!utah-cs!sandra (1987-08-15)
| List of all articles for this month |

Posted-Date: Sat, 15 Aug 87 22:23:20 MDT
Date: Sat, 15 Aug 87 22:23:20 MDT
From: harvard!ut-sally!utah-cs!sandra (Sandra J Loosemore)
Newsgroups: comp.compilers
References: <634@ima.ISC.COM> <642@ima.ISC.COM> <651@ima.ISC.COM> <655@ima.ISC.COM>

A couple years ago I implemented a parser for a fairly large language
(900+ states) using a SLR(1) parser generator, which I also wrote. (It
was a cleaned-up version of one I wrote for a formal languages class;
it's written in Common Lisp.) I found that it was necessary
to provide two distinct phases of error handling -- error signalling and
error recovery.

From what I remember of YACC, it provides only a way to do the error
recovery: a way to include special error productions, something like

            <statement> :== <error> <;>

The problem is that once the syntax error is detected, it then has to
skip ahead past a whole bunch of input tokens until it finds the
semicolon, and *then* it will execute the actions associated with the
production. If the action you specified was printing a diagnostic
message, you've just lost all the context for the message.

For my parser generator (called STACC), I took a slightly different
approach. As soon as the parser recognizes it's gotten an invalid
token, it calls a user-supplied error signalling function. For my
application, I had the tokenizer buffer the last line of input, so that
my signalling function could produce a nice message indicating the
context of the error. It's also possible to look at the internal
state of the parser at this time, if you want to include specific
information about what went wrong in your message. The second phase is
error recovery, and it happens much as in YACC: (1) the parse stack is
popped until it finds a state with an error transition; (2) the error
state is pushed; (3) tokens are read and discarded until one is found
that has a valid transition, and (4) parsing continues normally from

Incidentally, I would never have undertaken this project if I had had
to write the parser by hand. Even with the time it took me to write
the parser generator, I estimate it would have taken me two or three
times longer to do it by hand, and the resulting code would have been
much larger and more difficult to maintain. (It's particularly easy to
implement parser generators in Lisp, given its ability to manipulate
code fragments as data objects, and the presence of symbols as a
primitive datatype.)

-Sandra Loosemore, sandra@utah-cs.uucp

Post a followup to this message

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