Is every LL(1) grammar also an LR(1)?

Question

Is every LL(1) grammar also an LR(1)?

Answer 1

Yes, since both LL and LR parse the data from Left to Right; and since LL(1) looks ahead only one token it must necessarily be an LR(1). This is also true for LR(k), where k > 1, since an LR(k) grammar can be transformed into a LR(1) grammar.

The difference between LR and LL grammars comes in that LR produces the rightmost derivation, where as LL produces the leftmost derivation. So this means that an LR parser can in fact parse a greater set than an LL grammar as it builds up from the leaves.

Lets say we have productions as follows:

A -> "(" A ")" | "(" ")"

Then LL(1) will parse the string (()):

(()) -> A
     -> "(" A ")"
     -> "(" "(" ")" ")"

Where as the LR(1) will parse as follows:

Input  Stack          Action
(())   0       
())    0 '('
))     0 '(' '(' 
)      0 '(' '(' ')'  Reduce using A -> "(" ")"
)      0 '(' A
-      0 '(' A ')'    Reduce using A -> "(" A ")"
-      0  A           Accept

For more info see: http://en.wikipedia.org/wiki/LL_parsing