Editing LALR parser (section)

=== LR parsers ===
The LALR(1) parser is less powerful than the LR(1) parser, and more powerful than the SLR(1) parser, though they all use the same [[Formal grammar#The syntax of grammars|production rules]]. The simplification that the LALR parser introduces consists in merging rules that have identical '''kernel item sets''', because during the LR(0) state-construction process the lookaheads are not known. This reduces the power of the parser because not knowing the lookahead symbols can confuse the parser as to which grammar rule to pick next, resulting in '''reduce/reduce conflicts'''. All conflicts that arise in applying a LALR(1) parser to an unambiguous LR(1) grammar are reduce/reduce conflicts. The SLR(1) parser performs further merging, which introduces additional conflicts.

The standard example of an LR(1) grammar that cannot be parsed with the LALR(1) parser, exhibiting such a reduce/reduce conflict, is:<ref>"[http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756su56.xht 7.9 LR(1) but not LALR(1)] {{webarchive|url=https://web.archive.org/web/20100804231352/http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756su56.xht |date=4 August 2010 }}", ''[http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756.xht CSE 756: Compiler Design and Implementation] {{webarchive|url=https://web.archive.org/web/20100723153301/http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756.xht |date=23 July 2010 }},'' Eitan Gurari, Spring 2008</ref><ref>"[https://stackoverflow.com/questions/8496065/why-is-this-lr1-grammar-not-lalr1 Why is this LR(1) grammar not LALR(1)?]"</ref>
   S → a E c
     → a F d
     → b F c
     → b E d
   E → e
   F → e

In the LALR table construction, two states will be merged into one state and later the lookaheads will be found to be ambiguous. The one state with lookaheads is:

   E → e. {c,d}
   F → e. {c,d}

An LR(1) parser will create two different states (with non-conflicting lookaheads), neither of which is ambiguous. In an LALR parser this one state has conflicting actions (given lookahead c or d, reduce to E or F), a "reduce/reduce conflict"; the above grammar will be declared ambiguous by a [[LALR parser generator]] and conflicts will be reported.

To recover, this ambiguity is resolved by choosing E, because it occurs before F in the grammar. However, the resultant parser will not be able to recognize the valid input sequence <code>b e c</code>, since the ambiguous sequence <code>e c</code> is reduced to <code>(E → e) c</code>, rather than the correct <code>(F → e) c</code>, but <code>b E c</code> is not in the grammar.