LARA

LR(1) Parser Actions

This is a natural generalization of SLR 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.,t) \in$ K then
    • pop p from stack
    • push X onto stack
  • if none possible, report syntax error
  • if both possible, shift-reduce conflict: grammar not LR(1)

More Information

Theory of parsing, from page 372

Note, among other properties that if a language can be parsed by a deterministic pushdown automaton, then there is a grammar for this language that can be parsed by an LR(1) automaton. (Such grammar may be much bigger than the alternative non-deterministic grammar.)