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.

| cite | improve this question | | | | |
  • $\begingroup$ Have you tried using an example and seeing where you go wrong? AT which stage of the tree construction that you find the problem? $\endgroup$ – Camel Uno Aug 14 '12 at 5:32
  • $\begingroup$ 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". $\endgroup$ – Pablo Miranda Aug 14 '12 at 5:37
  • $\begingroup$ S --> TaS' | bS' ///// S'--> cS'|λ ////// T--> cT | λ ///// but seems like I just can't do it and I bet that's wrong ^ $\endgroup$ – Pablo Miranda Aug 14 '12 at 5:40
  • $\begingroup$ What is the grammar for? What are you trying to parse? What kind of string or expression? $\endgroup$ – Camel Uno Aug 14 '12 at 5:50
  • 2
    $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | | | | |
  • $\begingroup$ You could just have given a right-regular grammar. $\endgroup$ – Raphael Oct 7 '12 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy