title: What's wrong with my LR(0) grammar?
body: <p>I'm trying to make my own LR(0) parser, and I'm running into trouble with some grammars.</p>
  
  <p>Basically, for the grammar</p>
  
  <pre><code>exp:  mexp
  mexp: '1'
  mexp: mexp '*' '1'
  </code></pre>
  
  <p>my parser is outputting</p>
  
  <pre><code>State 0: • 1
         | • mexp
         | • exp
         | • mexp * 1
  State 1: 1 •
  State 2: exp •
  State 3: mexp • * 1
         | mexp •
  State 4: mexp * • 1
  State 5: mexp * 1 •
  </code></pre>
  
  <p>with the warning</p>
  
  <pre><code>(state 3, *) already has reduction:  exp: mexp
  </code></pre>
  
  <p>The LR(0) table my program derived for this grammar is:</p>
  
  <pre><code>         '1' exp mexp '*'    $
  State 0:  s1  s2   s3         
  State 1:  r3           r3   r3
  State 2:                   acc
  State 3:  r2           s4   r2
  State 4:  s5                 
  State 5:  r4           r4   r4
  </code></pre>
  
  <p>where $ denotes the end of file.</p>
  
  <p>The warning stems from the fact that state 3 -- which corresponds to <code>mexp • * 1 | mexp •</code> -- has <em>both</em> a reduction <code>r2</code> <em>and</em> a state transition <code>s4</code> for the input <code>*</code>.</p>
  
  <p>But it seems like <a href="http://en.wikipedia.org/wiki/LR_parser#Constructing_the_action_and_goto_tables" rel="nofollow">according to Wikipedia</a>, this should not be happening -- I should only have reductions:</p>
  
  <blockquote>
    <p>If an item set <em>i</em> contains an item of the form A → w • and A → w is rule <em>m</em> with <em>m</em> > 0 then the row for state <em>i</em> in the action table is completely filled with the reduce action r<sub><em>m</em></sub>.</p>
  </blockquote>
  
  <p>The funny thing is, when I remove the rule <code>exp: mexp</code>, I don't get any such conflicts.</p>
  
  <p>So what I'm having trouble figuring out is, is this indeed a genuine problem in the grammar?<br>
  (In other words, is this grammar not, in fact, LR(0)?)<br>
  I don't believe this to be the case but I'm not sure.</p>
  
  <p>If so, why? And if not, then what's wrong? (Is my table wrong, or am I doing something else incorrectly?)</p>