If I am given a CFG by looking at it can I decide whether it is a LL class of grammar or LR class of grammar? When I searched for this question on Google what I got was how the parsers for these grammars work, but, that is not what I want. Any assistance would be greatly appreciated.
Asked
Active
Viewed 182 times
0
-
1read this also: [How to determine whether a language is LL(1) LR(0) SLR(1)](http://stackoverflow.com/questions/475949/how-to-determine-whether-a-language-is-ll1-lr0-slr1) and [How to identify whether a grammar is LL(1), LR(0) or SLR(1)?](http://stackoverflow.com/questions/8496642/how-to-identify-whether-a-grammar-is-ll1-lr0-or-slr1) – Grijesh Chauhan May 20 '13 at 14:01
1 Answers
1
You can recognize if a grammar is not LL if it has left recursion.
Example:
S -> A | y
A -> Az
Samy Dindane
- 17,900
- 3
- 40
- 50
-
-
1
-
The absense of left recursion is **not** condition enough for a grammar to be LL. Lookup the definition of LL in Wikipedia. This grammar is not LL: ``S -> aSa | ε`` – Apalala May 20 '13 at 19:00
-
@Apalala Read **well** what I wrote. I didn't say *any grammar without left recursion is LL*, but I said *if it's left recursive, it is not LL*. – Samy Dindane May 20 '13 at 22:23
-
@Samy You're right. Please make any minor edit to your answer so I can remove the downvote. – Apalala May 21 '13 at 02:59
-
@Samy You didn't, edit your answer so I can remove the downvote. Yet remember that removing left recursion is a mechanical process, and that makes left-recursion not a primary criteria for LL-ness. – Apalala May 21 '13 at 03:03
-
@Apalala Answer edited. — What would be another criteria for LL-ness? – Samy Dindane May 21 '13 at 07:22