title: Why can't a LL grammar be left-recursive?
body: <p>In the <em><a href="http://en.wikipedia.org/wiki/Compilers%3a_Principles,_Techniques,_and_Tools">dragon book</a></em>, LL grammar is defined as follows:</p>
  
  <p>A grammar is LL if and only if for any production <code>A -&gt; a|b</code>, the following two conditions apply.</p>
  
  <ol>
  <li><p><code>FIRST(a)</code> and <code>FIRST(b)</code> are disjoint. This implies that they cannot both derive <code>EMPTY</code></p></li>
  <li><p>If <code>b</code> can derive <code>EMPTY</code>, then <code>a</code> cannot derive any string that begins with <code>FOLLOW(A)</code>, that is <code>FIRST(a)</code> and <code>FOLLOW(A)</code> must be disjoint.</p></li>
  </ol>
  
  <p>And I know that LL grammar can't be left recursive, but what is the formal reason? I guess left-recursive grammar will contradict rule 2, right? e.g., I've written following grammar:</p>
  
  <pre><code>S-&gt;SA|empty
  A-&gt;a
  </code></pre>
  
  <p>Because <code>FIRST(SA) = {a, empty}</code> and <code>FOLLOW(S) ={$, a}</code>, then <code>FIRST(SA)</code> and <code>FOLLOW(S)</code> are not disjoint, so this grammar is not LL. But I don't know if it is the left-recursion make <code>FIRST(SA)</code> and <code>FOLLOW(S)</code> not disjoint, or there is some other reason? Put it in another way, is it true that every left-recursive grammar will have a production that will violate condition 2 of LL grammar?</p>