Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| 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: | Gene <gene.ressler@gmail.com> |
| Newsgroups: | comp.compilers |
| Date: | Tue, 1 Jun 2010 19:29:57 -0700 (PDT) |
| Organization: | Compilers Central |
| References: | 10-06-003 |
| Keywords: | parse, theory |
| Posted-Date: | 02 Jun 2010 09:01:33 EDT |
On Jun 1, 5:47 pm, Matthias-Christian Ott <o...@mirix.org> wrote:
> 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.
The last sentence here is problematic. This actually means that if you
have a non-LR(k) grammar for a language (which after all is just a set
of strings), the question of whether a LR(k) grammar exists for the
same language is undecidable. As you imply later in your note, if you
already have a LR(k) grammar, then you have a trivially decidable
instance, but the general problem remains unsolvable.
Return to the
comp.compilers page.
Search the
comp.compilers archives again.