Re: Regular grammar from CFG?

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

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