# What's wrong with this LL grammar? (very short)

S --> Ta | b | Sc
T --> Tc | λ


This isn't an LL grammar but I need it to be so I can do a parse table. The problem is that no matter how much I try I never manage to do make it an LL grammar. Can someone please help by making it a LL grammar? It isn't that big and I'm very confused.

• Have you tried using an example and seeing where you go wrong? AT which stage of the tree construction that you find the problem? – Camel Uno Aug 14 '12 at 5:32
• I'm using JFLAP to create the parse table but I can't manage to make it LL, I always get "unrestricted at left side". – Pablo Miranda Aug 14 '12 at 5:37
• S --> TaS' | bS' ///// S'--> cS'|λ ////// T--> cT | λ ///// but seems like I just can't do it and I bet that's wrong ^ – Pablo Miranda Aug 14 '12 at 5:40
• What is the grammar for? What are you trying to parse? What kind of string or expression? – Camel Uno Aug 14 '12 at 5:50
• If you search the webs and even cs.SE for "remove left recursion", you will find algorithms that do so. Please try to apply them and refocus your question if necessary. – Raphael Aug 14 '12 at 15:40

First note that $T = c^*$ (using regular expression syntax). We can therefore rewrite your grammar to:

S --> c*a | b | Sc


Rewriting even further, we can say that $S = (c^*a | b)c^*$, so $S$ is regular. It is not hard to come up with a grammar for this language:

S --> T a T | b T
T --> c T | λ


More generally, when trying to rewrite grammars to $LL$ form, one first removes left recursion using standard techniques (for instance here). Then one tries to remove any conflicts that are left, for which no general techniques are known - just try to figure out what the conflict means, and try to solve it accordingly.

• You could just have given a right-regular grammar. – Raphael Oct 7 '12 at 22:30