LR Parsing Tables
So far we assumed that the state (set of items) is given by
- always starting in initial state
- re-running automaton on entire stack
Instead, LR parsers
- keep state corresponding to last run
- update the state on 'shift'
- pop the state on 'reduce'
Stack does not actually contain grammar symbols
- instead it contains corresponding states of the automaton
- current state is the top of the stack
Table Entries and Their Meaning
Three types of entries in table, for a given state I
- table(I)(t) = shift(J): on given token t, shift by pushing J onto stack
- table(I)(t) = reduce(k): let be rule number k, then
- pop |p| symbols from stack
- in resulting state execute goto(I,t) (to re-execute automaton on non-terminal X)
- table(I)(X) = goto(I,X): on non-terminal X, push state J on top of stack
Further References
See Tiger Book, Chapter 3 for many examples