title: Building parse trees with shift-reduce parsing
body: <p>I'm experimenting with parsing on my free time, and I wanted to implement a shift-reduce parser for a very very simple grammar. I've read many online articles but I'm still confused on how to create parse trees. Here's an example of what I want to do:</p>
  
  <hr>
  
  <p>Grammar:</p>
  
  <pre><code>Expr -&gt; Expr TKN_Op Expr 
  Expr -&gt; TKN_Num
  </code></pre>
  
  <p>Here's an example input:</p>
  
  <pre><code>1 + 1 + 1 + 1
  </code></pre>
  
  <p>That, after tokenization, becomes:</p>
  
  <pre><code>TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
  </code></pre>
  
  <hr>
  
  <p>I understand that:</p>
  
  <ol>
  <li><strong>Shifting</strong> means pushing the first input token on the stack and removing it from the input</li>
  <li><strong>Reducing</strong> means substituting one or more elements on the stack with a grammar element</li>
  </ol>
  
  <p>So, basically, this should happen:</p>
  
  <pre><code>Step 1:
      Stack:
      Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
      What: Stack is empty. Shift.
  
  Step 2:
      Stack: TKN_Num
      Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
      What: TKN_Num can be reduced to Expr. Reduce.
  
  Step 3:
      Stack: Expr
      Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
      What: Cannot reduce. Shift.
  
  Step 4:
      Stack: Expr TKN_Op 
      Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
      What: Cannot reduce. Shift.
  
  Step 5:
      Stack: Expr TKN_Op TKN_Num
      Input: TKN_Op TKN_Num TKN_Op TKN_Num
      What: TKN_Num can be reduced to Expr. Reduce.
      // What should I check for reduction? 
      // Should I try to reduce incrementally using 
      // only the top of the stack first, 
      // then adding more stack elements if I couldn't
      // reduce the top alone?
  
  Step 6:
      Stack: Expr TKN_Op Expr
      Input: TKN_Op TKN_Num TKN_Op TKN_Num
      What: Expr TKN_Op Expr can be reduced to Expr. Reduce.
  
  Step 7:
      Stack: Expr
      Input: TKN_Op TKN_Num TKN_Op TKN_Num
      What: ...
      // And so on...
  </code></pre>
  
  <p>Apart from the <em>"what to reduce?"</em> doubt, I have no clue how to correctly build a parse tree. The tree should probably look like this:</p>
  
  <pre><code>1    +    o
            |
       1    +    o
                 |
            1    +    1
  </code></pre>
  
  <p>Should I create a new node on reduction? </p>
  
  <p>And when should I add children to the newly create node / when should I create a new root node?</p>