Formally constructing control flow

[svrist]

Hi Kiama-list

I read your wikipage on dataflow, and loved the nice syntax and way of
specifying the algorithm. I need to do something similar, and
eventhough, with Kiama in hand, I'm able to do a CFG very easily I
need to explain how to do the CFG in a more formal way (for a report).

I've asked this question on Stack Overflow:
http://stackoverflow.com/questions/3616950/formally-constructing-control-flow-graph
stating my problem and outlining the problem a bit more rigoursly.

Im posting here just in case you might be able to point me to an
article or other material the actually do define a CFG in some formal
way.

Kind Regards
Søren B. Vrist

[Tony Sloane]

Hi Søren,

I'm very glad that you found it nice to express CFGs in Kiama. I would be interested to see your specification at some point, if you don't mind sharing. Also, any suggestions you have that could make things even easier would be useful to us.

Regarding formal descriptions of CFG building, I'm not aware of a great description. Some possibilities that I have here are:

- Engineering a Compiler by Cooper and Torczon has a short algorithm for CFG construction (p 439)
- Muchnick's, Advanced Compiler Design and Implementation has a more detailed algorithm

I hope these help.

cheers,
Tony

> --
> You received this message because you are subscribed to the Google Groups "kiama" group.
> To post to this group, send email to ki...@googlegroups.com.
> To unsubscribe from this group, send email to kiama+un...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/kiama?hl=en.
>

[Søren Bjerregaard Vrist]

Thank you :)

When I get a bit further along I can share some code with you guys.

Thanks for the book references. It looks like they might point me in a useful direction.

Muchnicks book had the much dreaded (to me) formulation:

"Throughout the remainder of the book, we assume that we are given a flowgraph

G = (N, E) with node set N and edge set E \subset N x N, where entry \in N and 

exit \in N. We generally write edges in the form a-> b, rather than (a, b)."

but much of the text concerning basic blocks and extended basic blocks overlap nicely with  "Engineering a Compiler"s description of how to two-pass the ast and characterize basic blocks by their leader and last operations.

(and Appels "Modern compiler implementation", even tough CFG isn't mentioned along with CFG explicitly)

This might take me a bit further, thank you very much!

As far as I can tell though, there is no very simple and clean way to do this formally - if the details should be done right. Which is ok, as long as I'm reasonably convinced that it is not just me that "haven't seen the light yet".

Thanks again!

/Søren

[Meredith Gregory]

Dear Soren,

i'm not quite sure what you're looking for. A context-free grammar (CFG) was first investigated and developed by Chomsky as a part of a hierarchy of formalizations of a theory of language. The idea itself, while originally presented in the context of the intersection of linguistics and the theory of computation, is quite a bit more general. For example, on the one hand, CFG's have a directly correlation with certain classes of solvable domain equations; and on the other are (mostly) succinctly captured by BNF-expressible grammars.

Best wishes,

--greg

--
You received this message because you are subscribed to the Google Groups "kiama" group.
To post to this group, send email to ki...@googlegroups.com.
To unsubscribe from this group, send email to kiama+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/kiama?hl=en.

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com

[Meredith Gregory]

Dear Soren,

Nevermind -- i misread your question!

Best wishes,

--greg

[Søren Bjerregaard Vrist]

Thanks for your time anyway, Im sorry I keep forgetting that CFG isnt just an acronym for Control Flow Graph but also Context Free Grammars :)

/Søren

mvh/Kind regards
Søren B. Vrist - http://blog.vrist.dk
Twitter: http://twitter.com/svrist   |  ------   |    ClaimID: http://claimid.com/svrist