title: How to transform this grammar to LR(1)?
body: <p>I have a grammar with an LR(1) conflict which I cannot resolve; yet, the grammar should be unambiguous. I'll first demonstrate the problem on a simplified grammar with five tokens: <code>(</code>, <code>)</code>, <code>{}</code>, <code>,</code> and <code>id</code>.</p>
  
  <p>The EBNF would look like this:</p>
  
  <pre><code>      args = ( id ',' )*
  
  expression = id
             | '(' expression ')'
             | '(' args ')' '{}'
  </code></pre>
  
  <p>The grammar is unambiguous and requires at most two tokens of lookahead. When <code>(</code> is shifted, there are only five possibilities:</p>
  
  <ol>
  <li><code>(</code> → Recur.</li>
  <li><code>)</code> → Reduce as <code>'(' args ')'</code>.</li>
  <li><code>id</code> <code>)</code> not <code>{}</code> → Reduce as <code>'(' expression ')'</code>.</li>
  <li><code>id</code> <code>)</code> <code>{}</code> → Reduce as <code>'(' args ')' '{}'</code></li>
  <li><code>id</code> <code>,</code> → Reduce as <code>'(' args ')' '{}'</code> (eventually).</li>
  </ol>
  
  <p>A naive translation yields the following result (and <a href="https://gist.github.com/whitequark/1d530b7da1a8324ba6a3#file-test-conflicts" rel="nofollow">conflicts</a>):</p>
  
  <pre><code>   formal_arg: Ident
                 {}
  
    formal_args: formal_arg Comma formal_args
               | formal_arg
               | /* nothing */
                 {}
  
        primary: Ident
               | LParen formal_args Curly
               | LParen primary RParen
                 {}
  </code></pre>
  
  <p>So, the grammar requires at most three tokens of lookahead to decide. I know that an LR(3) grammar <a href="http://en.wikipedia.org/wiki/Canonical_LR_parser" rel="nofollow">can be transformed</a> to LR(1) grammar.</p>
  
  <p>However, I don't quite understand how to do the transformation in this particular case. Note that the simplified grammar above is an extraction from a <a href="https://gist.github.com/whitequark/8f9b337e506664796f83" rel="nofollow">larger body of code</a>; in particular, is it possible to transform  <code>primary</code> without touching <code>expr</code> and everything above?</p>