Re: CFGs vs. "declare variable before use"

"Edsko de Vries" <devriese@cs.tcd.ie> writes:


> A common statement I read about the limitations of CFGs is that they
> cannot be used to express the requirement that "variables must be
> declared before they are used". However, I have been unable to find
> any formal justifications for this statement (e.g., in the style of
> the proof using the pumping lemma that a^n b^n c^n is not a context
> free language). Could anyone point me to some relevant literature?
> Also, are people aware of any other limitations of CFGs, esp. in the
> context of (the semantics of) programming languages, such as the one I
> mentioned, preferably with proofs?


CFG's can be used to guarantee that declarations precede use: If the
declaration dominates every use, then a variable is bound to be
declared before use. And you can also find cases where a use is
guaranteed to come before the declaration (if no path from the start
node to the use passes through the declaration). But there might be
cases where a control-flow analysis can't decide if there might be
uses preceeding the declaration.


Basically, the problem is that control-flow analysis (in most cases)
assumes that conditions are independent and that all branches are
valid. In a few cases, you can find conditions that are trivially
always true (or false) and you can find conditions that imply each
other (such as x<0 implies x<1), so you can see that some paths in the
CFG aren't valid. But (due to undecidability), no static analysis can
find all cases of dependent or constant conditions.


Hence, all static analyses are approximations, no matter if they are
based on CFG's, dataflow analysis, pre/post conditions or whatever.


                Torben

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