LR Parser Runs Automaton over Stack

Key question in LR parsing

  • when to shift
  • when to reduce, and using which rule

Key property:

Stack contains a prefix of rightmost derivation consistent with the input so far

Next action should preserve this property if possible

Earley Parser would maintain items to check if any such derivation exists

LR parsers runs a finite state automaton over stack

  • also uses notion of items (but without starting position)
  • not as powerful, approximates the answer
  • more efficient

Different automaton –> different types of LR algorithms

  • LR(0), SLR, LALR(1), LR(1), … (each more general than previous)