Elision, or: Nick rides again in jbonai

[Guy Steele <cbmvax!uunet!Think.COM!gls>]

   From: dmb@bigd.cray.com
   Date: Tue, 16 Apr 91 09:19:20 -0500

      I've considered the use of the <error> production to be a kludge ever
   since Jim Brown started it almost ten years ago.  It does allow the parser
   to recover from an elided terminator, if you are using YACC.  Of course,
   other errors in that position may get mistaken for elided terminators, though
   I'm not sure I could throw together an example that would get an error only
   at the place of an elided terminator.  It might be fun to try.

      My real question is for Guy.  If one wished to explore the question of
   including elidible terminators in the grammar, how would one go about it?
   My approach has been to include a rule allowing the terminator to go to an
   empty production and then examine the places where conflicts arise.  Those
   places are where ambiguities may arise if a terminator is elided.  Beyond
   that things seem to get messy.  

That's the first thing I would do, too.  And things can indeed get messy.

				   We don't have tools for hacking on grammars
   that make sure the language being defined doesn't change.

I'd have to check to be sure, but determining whether two context-free
grammars generate the same language is probably undecidable in the general
case.  That's not to say that you couldn't have a useful tool that prevents
you from making mistakes as you transform a grammar (but might not let
you make all possible transformations).
							      Grammar writing
   seems to be an art rather than a science.  My compiler theory classes were
   almost twenty years ago, but I do read some of the relevant journals.  The
   emphasis seems to be on developing better error recovery techniques and on
   modifications to the basic LR(k) algorithms which will produce smaller
   parsers.  I haven't seen any work on developing tools for grammar writers.