Return-Path: Return-Path: From: Guy Steele Date: Wed, 17 Apr 91 12:51:27 EDT Message-Id: <9104171651.AA14154@ukko.think.com> To: dmb@bigd.cray.com Cc: lojban-list@snark.thyrsus.com In-Reply-To: dmb@bigd.cray.com's message of Tue, 16 Apr 91 09:19:20 -0500 <9104161419.AA09068@bigd.cray.com> Subject: Elision, or: Nick rides again in jbonai Status: RO X-From-Space-Date: Wed Apr 17 17:00:52 1991 X-From-Space-Address: 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 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.