28 May 2005 13:59:31 -0400

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) |

Re: CFGs vs. "declare variable before use" cfc@shell01.TheWorld.com (Chris F Clark) (2005-06-02) |

[4 later articles] |

From: | "mefrill" <mefrill@yandex.ru> |

Newsgroups: | comp.compilers |

Date: | 28 May 2005 13:59:31 -0400 |

Organization: | http://groups.google.com |

References: | 05-05-216 |

Keywords: | syntax, semantics, theory |

Hi,

It is not too hard. Just use pumping lemma for KF-languages.

Pumping Lemma for KF-language:

Let L - KF-language. Then, there is such constant n, that if z - string

belongs L with |z| <= n, then z can be written in z = uvwxy and:

1. |vwx| <= n.

2. vx != epsilon (empty string).

3. uv^iwx^iy belongs L, if i >= 0.

So, we pump v and x.

Lets look in simplest language with "declare before use": L={ww: w

belongs to {0,1}*}. L consists of two same 0,1 simbols sequenses. For

example, 0101 (w=01) or 10111011 (w=1011). It is clear the language is

the simplest model of our problem. And let z=0^n1^n0^n1^n. So, z's

example is 0101, 00110011 and etc. It is not hard prove z cannot belong

to L. To do this, look on vwx string from pumping lemma and try to

understand where in z=0^n1^n0^n1^n it may be. There are 5 cases and no

one from them is true. For example, let vwx is in first zeros, so that

vwx belongs to first 0^n. Then vw=0^k, where k>0. What is uwy? uwy

begins with 0^(n-k)1^n. As |uwy|=4n-k and uvy=tt, then |t|=2n-k/2. So,

t is not in first block of ones and is completed by 0. But, last simbol

of uwy is 1, so uwy cannot be tt.

Edsko de Vries,

*> 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?*

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.