LARA

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 $X::=p$ 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