Re: Decidability of Deterministic Context-Free Languages

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

Return to the comp.compilers page.
Search the comp.compilers archives again.