RE: CFGs vs. "declare variable before use"

Quinn Tyler Jackson <>
28 May 2005 23:00:03 -0400

          From comp.compilers

Related articles
Re: CFGs vs. "declare variable before use" (Chris F Clark) (2005-05-28)
RE: CFGs vs. "declare variable before use" (Quinn Tyler Jackson) (2005-05-28)
| List of all articles for this month |

From: Quinn Tyler Jackson <>
Newsgroups: comp.compilers
Date: 28 May 2005 23:00:03 -0400
Organization: Compilers Central
References: 05-05-224
Keywords: parse, theory
Posted-Date: 28 May 2005 23:00:03 EDT

> Esko asked:
> > 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?
> I probably should let Quinn Tyler Jackson answer this as he's been
> working fairly extensively in this area, that is defining grammars for
> solving these kinds of problems.

The most cited proof of this general concept that I can think of is due to

It's the the ACM Digital Library -- and is a very short read.

[Floyd] R. W. Floyd, "On the Non-Existence of a Phrase Structure Grammar for
ALGOL 60," Communications of the ACM, Vol. 5, pp. 483-484, 1962.

Post a followup to this message

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