error recovery

[Dave Jones]

>From article <1279 at lzfme.att.com>, by jro at lzfme.att.com (J.OWENS):
> FROM:  James R. Owens, 38-C Elm Street, Summit, New Jersey 07901
> PHONE: 201-273-7360
> 
> I am looking for an algorithm for error-recovery to be used in
> a syntax analyzer.  The input stream is Pascal, and the parser
> is written in C under Unix 3.2.  My professor will not allow the use
> of Lex and Yacc.

Hmmmm...   Will he allow the use of some other parser-generator?
If not, your most practical solution would seem to be to re-implement
a subset of yacc.  But if that's not the solution your professor has in
mind, it's not likely to get you a very good grade.  He probably wants
you to write an ad hoc recursive descent parser. 

In any case, error-recovery is a little tricky. I use a commercial C compiler,
which I happen to know is written using yacc. It sometimes prints pages of
gibberish if you make a mistake.

I am currently writing a commercial Pascal compiler, using a BSD4.2 yacc
supplied by the same computer vender as the C compiler.  I had
to fix a bug in yacc in order to get error-recovery to work the way
it's supposed to.  We have a Unix source licence, and I happened to have
the sources to yacc laying around. But if I had not been able to fix the bug,
I would have used another parser-generator, or written one from scratch,
rather than doing a recursive descent parser.

Why? For one thing, error-recovery in a recursive descent parser is even
trickier than in an LR parser! The C activation stack gets to a point
where procedure activations are stacked up which must be discarded. A stack
of longjmp buffers is probably the best mechanism to use, but beware: there
are people who have strong religious objections to longjmp. Your prof might
be one of them.

Not to second guess your professor, but you seem to be new at this, and
it doesn't seem right to ask a student to implement error-recovery on the
first try without benefit of parser-building tools such as yacc. It could
take quite a bit of inspiration. Why not ask your instructor whether he
intends for you to write a recursive descent parser, and if so, whether he
wants you to attempt error-recovery.

If the answer to both is "yes," cancel all of your social engagements for
a couple of quarters.

> 
> Your comments, suggestions or CODE will be greatly appreciated.
> 

Let me get this right.  He won't let you use yacc, but he'll let you
use other people's suggestions and code?  Very curious.  I strongly 
suggest that you ask your professor for _his_ comments and suggestions.

> Thanks,
> James R. Owens

Hope this helped a little.