Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!news.glorb.com!postnews.google.com!news1.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!news.iecc.com!nerds-end From: Gene Newsgroups: comp.compilers Subject: Re: How detect cycle in grammar ? Date: Wed, 7 Dec 2011 06:29:33 -0800 (PST) Organization: Compilers Central Lines: 23 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <11-12-014@comp.compilers> References: <11-11-041@comp.compilers> <11-11-045@comp.compilers> <11-11-050@comp.compilers> <11-11-057@comp.compilers> <11-11-066@comp.compilers> NNTP-Posting-Host: news.iecc.com X-Trace: leila.iecc.com 1323609025 76560 64.57.183.58 (11 Dec 2011 13:10:25 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Sun, 11 Dec 2011 13:10:25 +0000 (UTC) Keywords: parse, theory Posted-Date: 11 Dec 2011 08:10:25 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:386 On Nov 28, 11:46 am, an...@mips.complang.tuwien.ac.at (Anton Ertl) wrote: > Gene writes: > >It's also worth noting that any grammar with A->A in it is ambiguous > >in a way that should cause LR table generation to fail. How would a > >parser know how many times to reduce A->A? > > S -> A|B > A -> A > B -> t > > This grammar can derive only the word "t", and only in one way. I see > no ambiguity; no word can be derived in two ways in this grammar. > > As for warning about these useless cycles, sure, they may indicate a > programming mistake, so better warn about them. I still don't see > that they are a problem as far as their meaning is concerned, nor > wrt. implementability in general. Apparently the Bison implementors > thought so, too, or Bison would produce an error, not a warning. We are really down in the weeds. I should have said any reduced grammar (with useless non-terminals already removed).