[ACCEPTED]-Is every LL(1) grammar also an LR(1)?-lr

Accepted answer
Score: 11

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

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

Lets say we 3 have productions as follows:

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

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

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

Where as the LR(1) will 1 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

More Related questions