Conversion to LR grammar

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.

alpanad@gmail.com (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