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

Problem Detail: 

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?

Asked By : templatetypedef

Answered By : templatetypedef

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!

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2791

3.2K people like this

 Download Related Notes/Documents