Re: Conversion to LR grammar (Hans Aberg)
13 May 2005 18:02:18 -0400

          From comp.compilers

Related articles
Conversion to LR grammar (2005-04-28)
Re: Conversion to LR grammar (2005-05-13)
| List of all articles for this month |

From: (Hans Aberg)
Newsgroups: comp.compilers
Date: 13 May 2005 18:02:18 -0400
Organization: Mathematics
References: 05-04-087
Keywords: parse, LR(1), theory
Posted-Date: 13 May 2005 18:02:18 EDT (Alpana) wrote:

> I want to write an LR grammar whose corresponding non-LR version is
> with me. Does any algorithm exists for do this? I know some of the
> tricks for conversion but had not encountered with any algorithm.

If you just have a general grammar, and want to decide whether it is
LR(k) for some k, I think that such problem might not be decidable,
even though I do not remember for sure.

There are grammar rewritings from LR(k) to LR(1), but those are not
usable for in practical implementations. In addition, many computer
languages are context sensitive, but by clever programming, one can
put that into the semantics, and reduce to a context free
grammar. Sometimes special tweaks are needed, in the lexer or the
parser, so that one can implement a language using LL(1) or LALR(1).

So it depends really what you want to do with you language: Is it
theoretical or a practical implementation?

    Hans Aberg

Post a followup to this message

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