08 Aug 2007 11:41:00 -0500

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) |

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 |

Posted-Date: | 08 Aug 2007 23:21:27 EDT |

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.