RE: CFGs vs. "declare variable before use"

Quinn Tyler Jackson <quinn-j@shaw.ca>
28 May 2005 23:00:03 -0400

          From comp.compilers
Related articles
Re: CFGs vs. "declare variable before use" cfc@shell01.TheWorld.com (Chris F Clark) (2005-05-28)
RE: CFGs vs. "declare variable before use" quinn-j@shaw.ca (Quinn Tyler Jackson) (2005-05-28)
| List of all articles for this month |
From: Quinn Tyler Jackson <quinn-j@shaw.ca>
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
[Floyd].


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


http://members.shaw.ca/qtj/


[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.