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.190.251.MISMATCH!transit4.readnews.com!news-out.readnews.com!news-xxxfer.readnews.com!news.misty.com!news.iecc.com!nerds-end
From: Hans Aberg <haberg-news@telia.com>
Newsgroups: comp.compilers
Subject: Re: How detect cycle in grammar ?
Date: Mon, 21 Nov 2011 18:14:05 +0100
Organization: A noiseless patient Spider
Lines: 19
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <11-11-043@comp.compilers>
References: <11-11-041@comp.compilers>
NNTP-Posting-Host: news.iecc.com
X-Trace: leila.iecc.com 1321934640 50452 64.57.183.58 (22 Nov 2011 04:04:00 GMT)
X-Complaints-To: abuse@iecc.com
NNTP-Posting-Date: Tue, 22 Nov 2011 04:04:00 +0000 (UTC)
Keywords: parse
Posted-Date: 21 Nov 2011 23:04:00 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:345

On 2011/11/20 17:48, Borneq wrote:
> A->B
> B->B
> This grammar is not correct, B is looped.
>
> A->B
> B->C
> C->A
> This another grammar, cycle can be arbitrarily long.
> Is cycle when First(Nonterminal) not contain any terminal, even not
> epsilon?

If it is only cycles in the graph you are out for, perhaps some
algorithm mentioned here might help:
   https://en.wikipedia.org/wiki/Strongly_connected_component
   https://en.wikipedia.org/wiki/Cycle_detection

Hans