|Regular grammar from CFG? email@example.com (Lorin Netsch) (2004-09-03)|
|Re: Regular grammar from CFG? firstname.lastname@example.org (Eric Bodden) (2004-09-07)|
|Re: Regular grammar from CFG? email@example.com (2004-09-07)|
|Re: Regular grammar from CFG? brosgol@worldDOTstd.com (Ben Brosgol) (2004-09-08)|
|Re: Regular grammar from CFG? firstname.lastname@example.org (2004-09-08)|
|Re: Regular grammar from CFG? email@example.com (Friedrich Neurauter) (2004-09-08)|
|Re: Regular grammar from CFG? firstname.lastname@example.org (Carl Cerecke) (2004-09-08)|
|Re: Regular grammar from CFG? email@example.com (2004-09-13)|
|Re: Regular grammar from CFG? firstname.lastname@example.org (2004-09-13)|
|From:||email@example.com (Neal Wang)|
|Date:||13 Sep 2004 10:48:09 -0400|
|Posted-Date:||13 Sep 2004 10:48:09 EDT|
firstname.lastname@example.org (VBDis) wrote
> "Lorin Netsch" <email@example.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
Determing whether a graph is Cocke-Allen reducible is decidable, but
determing whether a graph is SSFG reducible is undecidable.
Return to the
Search the comp.compilers archives again.