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)