1
$\begingroup$ 
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.

Improve this question
$\endgroup$
5
  • $\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
    Commented Aug 14, 2012 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
    Commented Aug 14, 2012 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
    Commented Aug 14, 2012 at 5:40
  • $\begingroup$ What is the grammar for? What are you trying to parse? What kind of string or expression? $\endgroup$
    – Camel Uno
    Commented Aug 14, 2012 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
    Commented Aug 14, 2012 at 15:40

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You could just have given a right-regular grammar. $\endgroup$
    – Raphael
    Commented Oct 7, 2012 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.