Re: CFGs vs. "declare variable before use"

"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!

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