title: Eliminating Left Recursion
body: <p>So I have some grammar that doesn't work for a top-down parser due to it having left recursion:</p>
  
  <pre><code>L::= A a | B b
  A::= L b | a a
  B::= b B b | b a
  </code></pre>
  
  <p>So in order to fix this, I have to remove the left recursion.  To do this, I do a little substitute-like-thing:</p>
  
  <pre><code>L::= A a | B b
  A::= A a b | B b b | a a (I plugged in the possible values of "L")
  </code></pre>
  
  <p>A then turns to (I believe):</p>
  
  <pre><code>A::= a a A' | B b b
  A'::= a b A' | ε
  </code></pre>
  
  <p>I'm fairly certain that I'm correct up to there (wouldn't be surprised if I'm not, though).  Where I'm struggling is now removing the left recursion out of "B b b".  I've tried going about this so many ways, and I don't think any of them work.  Here's one that seems most logical, but ugly as well (thus saying it's probably wrong).  Starting by manipulating B::= b B b | b a</p>
  
  <pre><code>B::= b B b | b a
  B::= b B' (they both start with b, so maybe i can pull it out?)
  B'::= B b | a
  B'::= b B' b | a (substituted B's value in)
  B'::= b B" | a
  B"::= b B" |a B" | ε
  </code></pre>
  
  <p>So I guess to show what the finalized B's would be:</p>
  
  <pre><code>B::= b B'
  B'::= b B" | a
  B"::= b B" | a B" | ε
  </code></pre>
  
  <p>This seems way too ugly to be correct.  Especially since I'd have to plug that into the new "A" terminals that I created.</p>
  
  <p>Can someone help me out?  No idea if I'm going about this the right way. I'm supposed to be able to create an LL(1) parse table afterward (should be able to do that part on my own).</p>
  
  <p>Thanks.</p>