[ACCEPTED]-Is every LL(1) grammar also an LR(1)?-lr
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
We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.