Wed, 02 Jun 2010 16:28:23 +0200

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: | torbenm@diku.dk (Torben Ęgidius Mogensen) |

Newsgroups: | comp.compilers |

Date: | Wed, 02 Jun 2010 16:28:23 +0200 |

Organization: | UNI-C |

References: | 10-06-003 |

Keywords: | parse, theory |

Posted-Date: | 03 Jun 2010 15:08:02 EDT |

Matthias-Christian Ott <ott@mirix.org> writes:

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

*>*

*> However, a LR(k) parser can indicate conflicts in the parsing table*

*> and detect if a grammar is not a LR(k) grammar.*

*>*

*> This seems to be a contradiction.*

Not at all. A grammar is deterministic if there exists a k such that

the grammar is LR(k). Making a LR(k) parser answers the question only

for a specific k.

Once you add the existential quantifier, you imply an unbounded search,

so the question is only semi-decidable: If the answer is "yes", you will

eventually get it, but if the answer is "no", you will never know.

You can look at it this way: If the grammar is not deterministic, how

will you prove it?

Torben

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.