Decidability of Deterministic Context-Free Languages

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.


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. I see the following possibilities
that would resolve it:


a) It is decidable whether a context-free language is deterministic.


b) Not all deterministic context-free languages can be described by an
      LR(k) grammar, in other words LR(k) languages are a subset of
      deterministic context-free languages.


c) Not all context-free grammars which aren't deterministic produce a
      conflict.


a) seems unlikely to be true. I know too little to decide whether b)
and c) are true.


Can someone help me with this?


Regards,
Matthias-Christian

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