Re: cycle free grammar ?

Max Hailperin <max@gustavus.edu>
08 Aug 2007 11:41:00 -0500

          From comp.compilers

Related articles
cycle free grammar ? ctx2002@gmail.com (2007-08-04)
Re: cycle free grammar ? wyrmwif@tsoft.org (SM Ryan) (2007-08-07)
Re: cycle free grammar ? max@gustavus.edu (Max Hailperin) (2007-08-08)
| List of all articles for this month |

From: Max Hailperin <max@gustavus.edu>
Newsgroups: comp.compilers
Date: 08 Aug 2007 11:41:00 -0500
Organization: Compilers Central
References: 07-08-014
Keywords: parse, theory

ctx2002@gmail.com writes:
> I am currently learning how to write a compiler , i am using a book
> called Compilers Principles , techniques, and tools.
>
> in this book , there is an exercise asking write a algorithm to
> convert a grammar into a equivalent cycle - free grammar.
>
> for example:
>
> convert grammar s->ss|(s)|e to a cycle free grammar.
>
> any one know how to do that?


If you first make the grammar epsilon-free (which is the prior
exercise, if memory serves me), then the only kinds of cycles that can
remain are those based on productions of the form A -> B. That may be
enough of a hint to let you figure out the algorithm on your own. If
not, a second hint would be to look at algorithms for finding the
strongly connected components of directed graphs. -max



Post a followup to this message

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