title: How to find FIRST and FOLLOW sets of a recursive grammar?
body: <p>Suppose I have the following CFG.</p>
  
  <pre><code>A -&gt; B | Cx | EPSILON
  B -&gt; C | yA
  C -&gt; B | w | z
  </code></pre>
  
  <p>Now if I try to find</p>
  
  <pre><code>FIRST(C) = FIRST(B) U FIRST(w) U FIRST(z)
           = FIRST(C) U FIRST(yA) U {w, z}
  </code></pre>
  
  <p>That is, I'm going in a loop.
  Thus I assume I have to convert it into a form which has immediate left recursion, which I can do as follows.</p>
  
  <pre><code>A -&gt; B | Cx | EPSILON
  B -&gt; C | yA
  C -&gt; C | yA | w | z
  </code></pre>
  
  <p>Now if I try to calculate FIRST sets, I think I can get it done as follows.</p>
  
  <pre><code>FIRST(C) = FIRST(C) U FIRST(yA) U FIRST(w) U FIRST(z)
           = { y, w, z } // I ignore FIRST(C)
  FIRST(B) = FIRST(C) U FIRST(yA)
           = { y, w, z }
  FIRST(A) = FIRST(B) U FIRST(Cx) U FIRST(EPSILON)
           = { y, w, z, EPSILON }
  </code></pre>
  
  <p>Am I correct there?</p>
  
  <p>But even if I'm right there, I still run into a problem when I try to calculate FOLLOW sets from this grammar.</p>
  
  <pre><code>FOLLOW(A) = { $ } U FOLLOW(B) U FOLLOW(C)
  </code></pre>
  
  <p>I get FOLLOW(B) from 2nd rule and FOLLOW(C) from 3rd rule. But now to calculate FOLLOW(B), I need FOLLOW(A) (from 1st grammar rule) so again I'm stuck in a loop.</p>
  
  <p>Any help?
  Thanks in advance!</p>