Re: Decidability of Deterministic Context-Free Languages

torbenm@diku.dk (Torben Ęgidius Mogensen)
Wed, 02 Jun 2010 16:28:23 +0200

          From comp.compilers

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)
| List of all articles for this month |

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.