Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!nx01.iad01.newshosting.com!newshosting.com!novia!border4.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!news.iecc.com!nerds-end From: anton@mips.complang.tuwien.ac.at (Anton Ertl) Newsgroups: comp.compilers Subject: Re: How detect cycle in grammar ? Date: Mon, 28 Nov 2011 16:46:51 GMT Organization: Institut fuer Computersprachen, Technische Universitaet Wien Lines: 23 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <11-11-066@comp.compilers> References: <11-11-041@comp.compilers> <11-11-045@comp.compilers> <11-11-050@comp.compilers> <11-11-057@comp.compilers> NNTP-Posting-Host: news.iecc.com X-Trace: leila.iecc.com 1322549622 65715 64.57.183.58 (29 Nov 2011 06:53:42 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Tue, 29 Nov 2011 06:53:42 +0000 (UTC) Keywords: parse, theory Posted-Date: 29 Nov 2011 01:53:42 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:368 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. - anton -- M. Anton Ertl anton@mips.complang.tuwien.ac.at http://www.complang.tuwien.ac.at/anton/