title: LR(1) parsing table with epsilon productions
body: <p>I'm having trouble building the collection of sets of items for LR(1) parsers with a grammar containing epsilon productions. For example, given the following grammar (where eps stands for epsilon)</p>
  
  <pre><code>S -&gt; a S U
  U -&gt; b
    |  eps
  </code></pre>
  
  <p>State0 would be</p>
  
  <pre><code>S' -&gt; .S, $
  S -&gt; .a S U, $
  </code></pre>
  
  <p>Moving with 'a' from State0 would give the following state, let's call it State2</p>
  
  <pre><code>S -&gt; a .S U, $
  S -&gt; .a S U, $/???
  </code></pre>
  
  <p>In order to have the lookahead for the second item of State2 I need to calculate FIRST(U$). I know that FIRST(U) = {'b', eps}. My first question is: the lookaheads of the second item of State2 are $ and 'b'? Since U can be eps, my brain tells me that I can have $ as a lookahead as well, not just 'b'. It would have been just 'b' if FIRST(U) would have been just {'b'}. Is that correct?</p>
  
  <p>Second question: at some point I will have a state as the following one</p>
  
  <pre><code>S -&gt; a S .U, $
  U -&gt; .b, $
  U -&gt; .eps, $
  </code></pre>
  
  <p>What do I do here? Do I need to move with eps and have a set with the item <code>U -&gt; eps., $</code>? What if I have another terminal as lookahead, i.e. <code>X -&gt; .eps, a/$</code>? And if I move, ending up having a set of the form <code>X -&gt; eps., $</code>, do I reduce?</p>
  
  <p>And more: do I need to insert eps in the parse table as a symbol?</p>
  
  <p>Thanks</p>