Re: CFGs vs. "declare variable before use"

SM Ryan <wyrmwif@tsoft.org>
28 May 2005 13:58:25 -0400

          From comp.compilers

Related articles
CFGs vs. "declare variable before use" devriese@cs.tcd.ie (Edsko de Vries) (2005-05-26)
Re: CFGs vs. "declare variable before use" wyrmwif@tsoft.org (SM Ryan) (2005-05-28)
Re: CFGs vs. "declare variable before use" mefrill@yandex.ru (mefrill) (2005-05-28)
Re: CFGs vs. "declare variable before use" torbenm@diku.dk (2005-05-28)
Re: CFGs vs. "declare variable before use" cfc@shell01.TheWorld.com (Chris F Clark) (2005-05-28)
Re: CFGs vs. "declare variable before use" torbenm@diku.dk (2005-05-31)
Re: CFGs vs. "declare variable before use" gah@ugcs.caltech.edu (glen herrmannsfeldt) (2005-05-31)
Re: CFGs vs. "declare variable before use" devriese@cs.tcd.ie (Edsko de Vries) (2005-06-02)
[5 later articles]
| List of all articles for this month |

From: SM Ryan <wyrmwif@tsoft.org>
Newsgroups: comp.compilers
Date: 28 May 2005 13:58:25 -0400
Organization: Quick STOP Groceries
References: 05-05-216
Keywords: syntax, semantics
Posted-Date: 28 May 2005 13:58:25 EDT

"Edsko de Vries" <devriese@cs.tcd.ie> wrote:
# 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


In a type 2 grammar, essentially you can't compare a substring of the
generated string to any arbitrary substring elsewhere. You're limitted
to adjacent substrings, P->QR, or substrings left and right of an
embedding core, P->QPR. So if you're limitting the variable to one
declaration and one reference, and all such variable ranges are
disjoint or properly nested, you can use a type 2 grammar for such a
language.


To match the substring(s) corresponding to a declaration to
substring(s) corresponding to a usage that can appear more freely, you
have to have a type 0 or perhaps type 1 grammar to move the
information around the generating string.


--
SM Ryan http://www.rawbw.com/~wyrmwif/
I ASSURE YOU WE'RE OPEN!


Post a followup to this message

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