Sun, 6 Jun 2010 11:15:57 -0700 (PDT)

Related articles |
---|

Decidability of Deterministic Context-Free Languages ott@mirix.org (Matthias-Christian Ott) (2010-06-01) |

Re: Decidability of Deterministic Context-Free Languages gneuner2@comcast.net (George Neuner) (2010-06-01) |

Re: Decidability of Deterministic Context-Free Languages gene.ressler@gmail.com (Gene) (2010-06-01) |

Re: Decidability of Deterministic Context-Free Languages torbenm@diku.dk (2010-06-02) |

Re: Decidability of Deterministic Context-Free Languages ott@mirix.org (Matthias-Christian Ott) (2010-06-02) |

Re: Decidability of Deterministic Context-Free Languages gene.ressler@gmail.com (Gene) (2010-06-06) |

Re: Decidability of Deterministic Context-Free Languages gneuner2@comcast.net (George Neuner) (2010-06-07) |

From: | Gene <gene.ressler@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Sun, 6 Jun 2010 11:15:57 -0700 (PDT) |

Organization: | Compilers Central |

References: | 10-06-003 10-06-005 10-06-007 |

Keywords: | parse, theory |

Posted-Date: | 06 Jun 2010 17:03:19 EDT |

On Jun 2, 5:55 pm, Matthias-Christian Ott <o...@mirix.org> wrote:

*> On Tue, Jun 01, 2010 at 07:29:57PM -0700, Gene wrote:*

*> > On Jun 1, 5:47 pm, Matthias-Christian Ott <o...@mirix.org> wrote:*

*> > > Hi,*

*>*

*> > > it is generally not decidable whether a context-free language is*

*> > > deterministic. That means it is not decidable whether a grammar is an*

*> > > LR(k) grammar.*

*>*

*> > The last sentence here is problematic. This actually means that if you*

*> > have a non-LR(k) grammar for a language (which after all is just a set*

*> > of strings), the question of whether a LR(k) grammar exists for the*

*> > same language is undecidable. As you imply later in your note, if you*

*> > already have a LR(k) grammar, then you have a trivially decidable*

*> > instance, but the general problem remains unsolvable.*

*>*

*> No, I meant it is undecidable whether an abitrary context-free grammar*

*> is deterministic. Several sources claim that LR(k) parsers and DPDA*

*> both (only) recognize deterministic context-free languages.*

*>*

*> However, I might have been a bit to careless about distinguishing*

*> grammars from languages.*

*>*

*> If you have context-free grammar you can contstruct a PDA from it and*

*> determine whether it is detmerministic or not. So you can decide with*

*> a context-free grammar either with a LR(k) parser or PDA whether it*

*> is deterministic or not.*

Okay. Then another way of stating my original point is that it

depends when you "fix" the value of k. For any given k, the

deterministic nature of a grammar is trivially decidable. As you

said, just try to construct a LR(k) parse table.

However, if you let the value of k "free," you have a harder problem:

deciding whether a LR(k) parser exists for _any_ k. This is only semi-

decidable. I.e you can always be sure of a "yes" if that's the

answer. Just try to build a parser for k = 0,1,2, ... until you are

successful. On the other hand if the answer is "no," you can never be

sure. E.g. trying k=0,1,2,... you'll never be certain the next value

isn't the one that's successful. (Hence the old saw that's it's hard

to prove a negative.)

Semi-decidable is also undecidable, so there is no contradiction.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.