Re: CFGs vs. "declare variable before use"

> I am presuming that you mean to pick an element z from L; then show
> (as you did) that we cannot apply the pumping lemma to the element z
> (as you defined it); therefore we can conclude that L is not context
> free. (I am a bit confused by your statement "it is not hard to prove
> z cannot belong to L", because clearly, z is in L).


I meant "z cannot belong to L if L is defined by KF-grammar". My
thinking was folowing: if L is defined by KF-grammar then pumping lemma
should be applied to L. And I am showing that it is not true by
selecting string z, which is (we know) in L, but cannot belong to L as
it is proven from pumping lemma. It is stndard method of proving named
as "the rule of contraries". To prove A-->B you prove !B-->!A. A here
is "L satisfies declare before using rule" and B is "L is not
KF-language". We suppose !B = "L IS KF-language" and prove !A="L DOES
NOT satisfy declare before using rule". To do this we get the simplest
model of the language with "declare before use" rule. Each language
within such the rule has structure like "declaration w statemens using
w", where w is identifier. We drop all unnecessary and get "ww"
language. What model may be simpler? To prove I used the property that
language L1={0^n1^n0^n1^n: n belongs to N} is contained in L={ww}. It
is the simplest method to prove. But, it is clear that it is only
simple way to prove and does not reflect WHY "declare before use" rule
does not allow a language to be KF. To understand this I suggest you
think about simple fact: if we want ID to be in garammar we must drop
abstract ID (coming from lex) and include in our KF-grammar fro the
language the set of rules generate ID. This set always must generate ID
by this way: generate pair "declare ID" number of "using ID" and then
move "using ID" further in the program text. So, the problem really
concerns ww language. And the problem really is generation of the
second w, which is context dependent from the first w. The simplest way
to prove this "context depending" is using pumping lemma. Try think and
find something else. But, is seems to be harder.


Vladimir.

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