|Re: CFGs vs. "declare variable before use" cfc@shell01.TheWorld.com (Chris F Clark) (2005-05-28)|
|RE: CFGs vs. "declare variable before use" email@example.com (Quinn Tyler Jackson) (2005-05-28)|
|From:||Quinn Tyler Jackson <firstname.lastname@example.org>|
|Date:||28 May 2005 23:00:03 -0400|
|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.
Return to the
Search the comp.compilers archives again.