Re: How detect cycle in grammar ?

Hans Aberg <haberg-news@telia.com>
Mon, 21 Nov 2011 18:14:05 +0100

          From comp.compilers
Related articles
How detect cycle in grammar ? a.moderacja@gmail.com (Borneq) (2011-11-20)
Re: How detect cycle in grammar ? haberg-news@telia.com (Hans Aberg) (2011-11-21)
Re: How detect cycle in grammar ? gene.ressler@gmail.com (Gene) (2011-11-21)
Re: How detect cycle in grammar ? anton@mips.complang.tuwien.ac.at (2011-11-22)
Re: How detect cycle in grammar ? a.moderacja@gmail.com (Borneq) (2011-11-23)
Re: How detect cycle in grammar ? a.moderacja@gmail.com (Borneq) (2011-11-24)
Re: How detect cycle in grammar ? quinn_jackson2004@yahoo.ca (Quinn Tyler Jackson) (2011-11-25)
Re: How detect cycle in grammar ? gene.ressler@gmail.com (Gene) (2011-11-27)
[6 later articles]
| List of all articles for this month |
From: Hans Aberg <haberg-news@telia.com>
Newsgroups: comp.compilers
Date: Mon, 21 Nov 2011 18:14:05 +0100
Organization: A noiseless patient Spider
References: 11-11-041
Keywords: parse
Posted-Date: 21 Nov 2011 23:04:00 EST

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


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.