title: How to write a recursive descent parser?
body: <p><strong>C++</strong>
  I can't figure out how to write a recursive descent parser for the following grammar:</p>
  
  <pre><code>&lt;Datalog Program&gt;     -&gt;  Schemes : &lt;Scheme List&gt;     
                           Facts   : &lt;Fact List&gt;
                           Rules   : &lt;Rule List&gt;
                           Queries : &lt;Query List&gt;
                           &lt;EOF&gt;
  &lt;Scheme List&gt;         -&gt;  &lt;Scheme&gt; &lt;Scheme List Tail&gt;
  &lt;Scheme List Tail&gt;    -&gt;  &lt;Scheme List&gt; | ε
  &lt;Scheme&gt;              -&gt;  &lt;Identifier&gt; ( &lt;Identifier List&gt; )
  &lt;Identifier List&gt;     -&gt;  &lt;Identifier&gt; &lt;Identifier List Tail&gt;
  &lt;Identifier List Tail&gt;-&gt;  , &lt;Identifier List&gt; | ε
  &lt;Fact List&gt;           -&gt;  &lt;Fact&gt; &lt;Fact List&gt; | ε
  &lt;Fact&gt;                -&gt;  &lt;Identifier&gt; ( &lt;Constant List&gt; ) .
  &lt;Constant List&gt;       -&gt;  &lt;String&gt; &lt;Constant List Tail&gt;
  &lt;Constant List Tail&gt;  -&gt;  , &lt;Constant List&gt; | ε
  &lt;Rule List&gt;           -&gt;  &lt;Rule&gt; &lt;Rule List&gt; | ε
  &lt;Rule&gt;                -&gt;  &lt;Head Predicate&gt; :- &lt;Predicate List&gt; .
  &lt;Head Predicate&gt;      -&gt;  &lt;Identifier&gt; ( &lt;Identifier List&gt; )
  &lt;Predicate List&gt;      -&gt;  &lt;Predicate&gt; &lt;Predicate List Tail&gt;
  &lt;Predicate List Tail&gt; -&gt;  , &lt;Predicate List&gt; | ε
  &lt;Predicate&gt;           -&gt;  &lt;Identifier&gt; ( &lt;Parameter List&gt; )
  &lt;Parameter List&gt;      -&gt;  &lt;Parameter&gt; &lt;Parameter List Tail&gt;
  &lt;Parameter List Tail&gt; -&gt;  , &lt;Parameter List&gt; | ε
  &lt;Parameter&gt;           -&gt;  &lt;String&gt; | &lt;Identifier&gt; | &lt;Expression&gt;
  &lt;Expression&gt;          -&gt; ( &lt;Parameter&gt; &lt;Operator&gt; &lt;Parameter&gt; )
  &lt;Operator&gt;            -&gt; + | *
  &lt;Query List&gt;          -&gt;  &lt;Query&gt; &lt;Query List Tail&gt;
  &lt;Query List Tail&gt;     -&gt;  &lt;Query List&gt; | ε
  &lt;Query&gt;               -&gt;  &lt;Predicate&gt; ?
  </code></pre>
  
  <p>This is a simple datalog-like grammar. I'm absolutely lost in trying to write the parser. I've already written a Lexical Analyzer that outputs a vector with all the tokens. I know that I need to write methods for each production, but I can't figure out how to connect the tokens into a parse tree (so I can run a toString() function after the tree is complete). I need to be pointed into the right direction. Thanks.</p>