Minimise LR(1) table

[tjvr]

There appear to be techniques to reduce the number of states in the automaton.

• The Lane Table algorithm shows how to augment an LR(0) automaton to use an LR(1) lookahead only where necessary

• Practical LR(k) Parser Construction shows how to reduce the number of states in an LR(1) automaton where possible (calls this the "Honalee algorithm")

[tjvr]

Consider the following two item sets:

i6. goto('+') from i2
  1 [Expr  -> Factor '+' . num,  $end]*
  2 [Expr  -> Factor '+' . num,  '+' ]*
  3 [Parms -> .,                 ',' ] 

i11. goto('+') from i4
  1 [Expr  -> Factor '+' . num,  '+']*
  2 [Expr  -> Factor '+' . num,  ')']*
  3 [Parms -> .,                 ','] 

If we ignore lookahead items, they have the same item cores:

i6. cores:
  [Expr  -> Factor '+' . num]*
  [Parms -> .               ]

i11. cores:
  [Expr  -> Factor '+' . num]*
  [Parms -> .               ]

(We only need to compare the cores of the kernel items, since the closure items are determined by the kernel items, and so should be the same.)

Also, the reduction item sets are identical, so merging them would not produce a reduce/reduce conflict. ("This occurs in grammars that are LR(k) but which are not simpler, i.e., grammars that are not SLR(0), LALR(k), or LR(0).") That is to say, if the reduction is different depending on the lookahead symbol.