LR(0) Parser Actions

Let K be parser state at the end of stack and t current token:

  • if there is a transition $(K,t,I)$ for $I$ non-empty
    • shift: push t onto stack
    • if t is EOF, then accept
  • reduce: if item $(X::=p.) \in$ K then
    • pop p from stack (it will be there)
    • push X onto stack (automaton will not be stuck)
  • if none possible, report syntax error
  • if both possible, shift-reduce conflict: grammar not LR(0)

More powerful are SLR Parser Actions