Tue, 1 Jun 2010 23:47:04 +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: | Matthias-Christian Ott <ott@mirix.org> |

Newsgroups: | comp.compilers |

Date: | Tue, 1 Jun 2010 23:47:04 +0200 |

Organization: | Compilers Central |

Keywords: | parse, theory, question |

Posted-Date: | 01 Jun 2010 18:47:21 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.