28 Jul 2004 12:23:02 -0400

Related articles |
---|

Converting LR(k) grammars to LR(1) ralphpboland@yahoo.com (2004-07-28) |

From: | ralphpboland@yahoo.com (Ralph Boland) |

Newsgroups: | comp.compilers |

Date: | 28 Jul 2004 12:23:02 -0400 |

Organization: | http://groups.google.com |

Keywords: | LR(1), parse, question |

Posted-Date: | 28 Jul 2004 12:23:02 EDT |

I am aware that LR(k) grammars can be converted to LR(1) grammars and

am interested in algorithms the do this conversion automatically. I

am not actually interested in doing this conversion but in

understanding it as I believe this information will be useful for a

parser generator tool I am designing. (I am hoping to prove that with

my parser generator algorithm such conversions are not necessary,

admittedly a lofty goal.)

I checked the original paper by Knuth in which it is proved that this

conversion is always possible but the proof does not translate

easily into a constructive algorithm.

Can anyone point me to algorithms for converting LR(k) grammars into

LR(k-1) grammars for k>1 or to algorithms for converting a LR(k)

grammars directing into LR(1) grammars?

Alternative proofs of Knuth's result that are more constructive in nature

would also be appreciated.

Thanks

Ralph Boland

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.