# When did $LR(k)$ acquire the meaning "left-to-right scan, rightmost derivation?"

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?

• 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. Mar 10 '15 at 15:08
• @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. Mar 10 '15 at 15:18
• 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...) Mar 10 '15 at 16:06

## 1 Answer

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!