13 Sep 2004 10:48:09 -0400

Related articles |
---|

Regular grammar from CFG? netsch@ti.com (Lorin Netsch) (2004-09-03) |

Re: Regular grammar from CFG? newsserver_mails@bodden.de (Eric Bodden) (2004-09-07) |

Re: Regular grammar from CFG? vannoord@let.rug.nl (2004-09-07) |

Re: Regular grammar from CFG? brosgol@worldDOTstd.com (Ben Brosgol) (2004-09-08) |

Re: Regular grammar from CFG? vbdis@aol.com (2004-09-08) |

Re: Regular grammar from CFG? friedrich.neurauter@eunet.at (Friedrich Neurauter) (2004-09-08) |

Re: Regular grammar from CFG? cdc@maxnet.co.nz (Carl Cerecke) (2004-09-08) |

Re: Regular grammar from CFG? neal.wang@gmail.com (2004-09-13) |

Re: Regular grammar from CFG? scavadini@ucse.edu.ar (2004-09-13) |

From: | neal.wang@gmail.com (Neal Wang) |

Newsgroups: | comp.compilers |

Date: | 13 Sep 2004 10:48:09 -0400 |

Organization: | http://groups.google.com |

References: | 04-09-035 04-09-060 |

Keywords: | parse, theory |

Posted-Date: | 13 Sep 2004 10:48:09 EDT |

vbdis@aol.com (VBDis) wrote

*> "Lorin Netsch" <netsch@ti.com> schreibt:*

*>*

*> >Can anyone tell me how to determine if a given CFG can be represented*

*> >as a regular grammar?*

*>*

*> You may have a look at the thesis and related work of Cristina Çifuentes. She*

*> describes how interval analysis can be used to determine whether a CFG is*

*> reducible, and IMO this is what you want to determine?*

The original paper of interval analysis is "Frances E. Allen, Control

Flow Analysis". The reducible graphs can be determined by interval

analysis are also called Cocke-Allen reducible by Kennedy in "A survey

of data flow analysis techniques".

Farrow, Kennedy, and Zucconi introduced Semic-structured Flow Graph

(SSFG) grammar, which is a regular grammar, in "Graph Grammars and

Global Program Flow Analysis".

The set of Cocke-Allen reducible graphs is a superset of

SSFG-reducible graphs.

Determing whether a graph is Cocke-Allen reducible is decidable, but

determing whether a graph is SSFG reducible is undecidable.

Neal

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.