title: How do I generate sentences from a formal grammar?
body: <p><strong>What's a common way of generating sentences from a grammar?</strong></p>
  
  <p>I want an algorithm that's sort of the opposite of a parser. That is, given a formal context-free grammar (say LL), I want to generate an arbitrary sentence that conforms to that grammar. I use <em>sentence</em> here to mean any valid body of text, so it can actually be a whole program (even if it doesn't make any sense—as long as it's syntactially correct). </p>
  
  <p>Example grammar:</p>
  
  <pre><code>program   : &lt;imports&gt; NEWLINE? &lt;namespace&gt;
  imports   : ("import" &lt;identifier&gt; NEWLINE)* 
  namespace : "namespace " &lt;identifier&gt; NEWLINE "{" &lt;classes&gt; "}" 
  identifier: (A-Za-z_) (A-Za-z0-9_)*
  ...
  </code></pre>
  
  <p>Example generated <em>program</em>:</p>
  
  <pre><code>import jkhbhhuob
  import aaaaa888_
  
  namespace u8nFGubgykb
  { class ui0op_np { ... }
  }
  </code></pre>