14
$\begingroup$

According to the Wikipedia article, the L in $LR(k)$ means "left-to-right scan", and the "R" means "rightmost derivation." However, in Knuth's original paper on $LR(k)$ grammars, he defines $LR(k)$ (on page 610) as a language that is "translatable from left to right with bound $k$."

I am guessing that this new terminology was chosen to complement $LL(k)$ parsing's "left-to-right scan, leftmost derivation." That said, I don't know when the terminology changed meaning.

Does anyone know where the newer acronym for $LR(k)$ comes from?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Have you achieved any progress in this question? I am just at the same spot right now, not knowing which meaning to rely on. Teaching an introductory course, I don't want to go into so much detail to explain LL grammars as well (so, the "left-to-right"-meaning would be nice and simple), but on the other hand, teaching the wrong meaning is not acceptable. $\endgroup$ – lukas.coenig Mar 10 '15 at 15:08
  • $\begingroup$ @lukas.coenig I don't think it's "wrong" to use the more modern terminology. I haven't heard anything since I posted this question a while back, unfortunately. $\endgroup$ – templatetypedef Mar 10 '15 at 15:18
  • $\begingroup$ Sorry to here that - very nice question btw. (My concern is not about the modern terminology - I would rather like to use the old one which is more simple. However, I found an accurate way by just citing the original paper next to the definition. This can't be wrong either...) $\endgroup$ – lukas.coenig Mar 10 '15 at 16:06
5
$\begingroup$

I went and asked Don Knuth about this. He mentioned that he first used the new terminology in his 1972 paper Top-Down Syntax Analysis (link here) to provide a consistency between the terminology in $LL(k)$ and $LR(k)$ parsing.

Hope this helps!

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.