13 May 2005 18:02:18 -0400

Related articles |
---|

Conversion to LR grammar alpanad@gmail.com (2005-04-28) |

Re: Conversion to LR grammar haberg@math.su.se (2005-05-13) |

From: | haberg@math.su.se (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 |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.