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).