LR Parser Runs Automaton over Stack

Key property:

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

  • this property depends also on the initial symbol

Next action of the parser should preserve this property

Key question in LR parsing

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

Earley Parser would maintain all possibilities

LR parsers instead runs a finite state automaton over the current stack: the final state of the automaton encodes the decision

  • it incorporates some top-down information

About the automaton:

  • uses notion of items as in Earley Parser (but without starting position)
  • not as powerful, as Earley Parser because it approximates one answer
  • runs in time linear in input size

Different automaton –> different type of LR algorithm:

  • LR(0), SLR, LALR(1), LR(1)

each more general than previous one

All these classes of parsers can accept only some of the context-free languages, but are often sufficient for programming languages in practice (partly because languages are designed in a way to be easy to parse).