LR Parsing

LR parsing is a table-driven bottom-up method for deterministic context-free grammars. L means tokens are read left to right; R means the parser constructs a rightmost derivation in reverse.

Shift-Reduce Machine #

The parser maintains a stack of states and grammar symbols. For each state and lookahead token, an action table chooses one of:

1. Shift: consume the token and push the destination state.
2. Reduce: replace the right-hand side of a production with its left-hand-side nonterminal, then use the goto table to select the next state.
3. Accept: recognize the augmented start production at end of input.
4. Error: report that no valid continuation exists.

push state 0
repeat
  action = ACTION[top_state, lookahead]
  if action is shift s: consume lookahead; push s
  if action is reduce A → β: pop |β| grammar symbols and states; push GOTO[top_state, A]
  if action is accept: return syntax tree
  otherwise: report a syntax error

Semantic actions commonly run on reduction. A parallel value stack stores AST nodes or other values for the symbols being reduced.

Items and Lookahead #

An LR item records a production and a dot showing recognized input, for example E → E + · T. Item sets form parser states. closure adds productions required by a nonterminal after the dot, and goto advances the dot over a grammar symbol.

LR(0) reductions have no lookahead and therefore accept a small grammar class. SLR uses FOLLOW sets to restrict reductions. Canonical LR(1) attaches a lookahead set to each item and recognizes more grammars. LALR(1) merges compatible LR(1) states to reduce table size; merging can introduce conflicts that canonical LR(1) does not have.

A shift/reduce conflict means the table cannot determine whether to consume a token or reduce. A reduce/reduce conflict means two reductions are possible. Precedence declarations can resolve intended expression conflicts, but a conflict caused by an ambiguous language construct should be repaired in the grammar or made explicit in the language specification.