4 Jun 2005 15:07:34 -0400

Related articles |
---|

[4 earlier 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" 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) |

Re: CFGs vs. "declare variable before use" gah@ugcs.caltech.edu (glen herrmannsfeldt) (2005-06-04) |

Re: CFGs vs. "declare variable before use" mefrill@yandex.ru (mefrill) (2005-06-04) |

Re: CFGs vs. "declare variable before use" mittra@juno.com (Swapnajit Mittra) (2005-06-08) |

Re: CFGs vs. "declare variable before use" sharp@cadence.com (2005-06-08) |

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

Newsgroups: | comp.compilers |

Date: | 4 Jun 2005 15:07:34 -0400 |

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

References: | 05-05-21605-06-020 |

Keywords: | syntax, theory |

Posted-Date: | 04 Jun 2005 15:07:34 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.