Converting LR(k) grammars to LR(1)

ralphpboland@yahoo.com (Ralph Boland)
28 Jul 2004 12:23:02 -0400

          From comp.compilers
Related articles
Converting LR(k) grammars to LR(1) ralphpboland@yahoo.com (2004-07-28)
| List of all articles for this month |
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.