Re: Decidability of Deterministic Context-Free Languages

On Tue, 1 Jun 2010 23:47:04 +0200, Matthias-Christian Ott
<ott@mirix.org> wrote:


>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. So it can decide
>whether a grammar is deterministic context-free.
>
>This seems to be a contradiction.


It isn't. What you're missing is that a grammar serves two purposes -
it is both a generator of a language and a recognizer of strings
contained in that language. Recognition of any particular subset
requires determining the necessary lookahead value (k), but it does
not require knowing whether the full generated language is also (k)
(unless, of course, the recognized subset is the entire language ...
which is VERY rare in practice).


George

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