Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!nx02.iad01.newshosting.com!newshosting.com!198.186.194.249.MISMATCH!transit3.readnews.com!news-out.readnews.com!news-xxxfer.readnews.com!news.misty.com!news.iecc.com!nerds-end From: Quinn Tyler Jackson Newsgroups: comp.compilers Subject: Re: How detect cycle in grammar ? Date: Fri, 25 Nov 2011 22:28:58 -0800 Organization: Compilers Central Lines: 37 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <11-11-052@comp.compilers> References: <11-11-041@comp.compilers> <11-11-045@comp.compilers> <11-11-046@comp.compilers> NNTP-Posting-Host: news.iecc.com X-Trace: leila.iecc.com 1322342329 57248 64.57.183.58 (26 Nov 2011 21:18:49 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Sat, 26 Nov 2011 21:18:49 +0000 (UTC) Keywords: parse, theory Posted-Date: 26 Nov 2011 16:18:49 EST X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: x330-a1.tempe.blueboxinc.net comp.compilers:354 On Tue, Nov 22, 2011 at 7:20 AM, Anton Ertl wrote: > > Gene writes: > >Nonterminals that can never derive a terminal string are the > >problem. > > Is it really? Since they cannot derive a terminal, they have no > influence on the language described by the grammar. They might just > as well not be there. Are they really a problem (except for certain > implementation techniques)? Imagine a world of parsing where the common wisdom (nonterminals that do not derive a terminal have no influence on the grammar) does not apply, and then try to imagine writing a parser generator for such a language. Welcome to adaptive grammars. In an adaptive grammar, a rule that (eventually or directly) derives a terminal one instant may or may not derive one the next, and if it does, it may not derive the same terminal(s) it used to, and this may vary over time (global state) or space (local state). S ::= b ":" y; b ::= <> #super; // match the longest of z or x a ::= '[a-z]+'; x ::= $n|=(a); y ::= x.n; z ::= "orange"; The above grammar (which varies over space, not time -- and is therefore declarative rather than imperative) generates the language L = {w:w | w=a string of 1 or more letters in length, and w != the string orange}. That is, in one very special case y does not derive a terminal, and is "useless" but in every other case, it does derive a terminal. Quinn