10

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

Michael Petrotta
  • 59,888
  • 27
  • 145
  • 179
siddharth
  • 579
  • 1
  • 8
  • 18

1 Answers1

11

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

Mike
  • 1,060
  • 2
  • 11
  • 14
  • but the sequence(of productions) used by LL(1) to parse is not always in the opposite sequence(of productions)used by LR(1) to parse. Even though former being the top down and latter being bottom up parser so your reason for all LL(1) to be LR(1) does not seem enough. – siddharth Nov 14 '10 at 01:43
  • 1
    Something being LR does not mean that the parse tree with be identical to the inverse LL parse tree, and the thus parser will not necessarily use the productions in the opposite order. What it does mean is that an LR parser can correctly parse the same set of strings given the same grammar. – Mike Nov 14 '10 at 03:31
  • Does this fact contradicts? http://cs.stackexchange.com/questions/60763/does-my-grammar-contradict-ll-⊆-lr1/60764#60764 – Pranav Jul 24 '16 at 11:51