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!216.196.98.146.MISMATCH!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!news.iecc.com!nerds-end From: glen herrmannsfeldt Newsgroups: comp.compilers Subject: Re: How detect cycle in grammar ? Date: Tue, 29 Nov 2011 07:31:17 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 37 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <11-11-068@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 1322708083 24728 64.57.183.58 (1 Dec 2011 02:54:43 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Thu, 1 Dec 2011 02:54:43 +0000 (UTC) Keywords: parse, errors Posted-Date: 30 Nov 2011 21:54:43 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:370 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. For this case, it would seem easy for any program to figure out that it was a useless recursion. If you make a longer cycle of useless recursion, then it might be harder to detect, but it still shouldn't be so hard. Now, you could also have: D -> D t or E -> t E which are also useless, in that they require an infinite number of t's to match, so again I would hope that they could be detected. For complicated grammars, it isn't easy for people to track all these down, but it is easy for programs to do it. -- glen h