title: Recursion definitions in BNF
body: <p>I've recentrly started studying programming languages, and I'm trying to get better at understanding recursive definitions in BNF.</p>
  
  <p>For example, if we consider identifier as anything that consists of letters and digits, but always starts with a letter, the definition for such identifier would be</p>
  
  <pre><code>&lt;identifier&gt; ::= &lt;letter&gt; | &lt;identifier&gt; &lt;character&gt;
  &lt;character&gt;  ::= &lt;digit&gt; | &lt;letter&gt;
  </code></pre>
  
  <p>But it gets interesting when we consider a definition of number. Should it be this</p>
  
  <pre><code>&lt;number&gt; ::= &lt;digit&gt; | &lt;number&gt; &lt;digit&gt;
  </code></pre>
  
  <p>or this?</p>
  
  <pre><code>&lt;number&gt; ::= &lt;digit&gt; | &lt;digit&gt; &lt;number&gt;
  </code></pre>
  
  <p>– syntactically they both seem to be correct, but my guts say that their semantics would differ – one number would be 0123456789, and another – 9876543210. Am I wrong and both number definitions are valid?</p>