LR Parser Uses Rightmost Derivation

In contrast, LR parser

  • uses rightmost derivation
  • accumulates right-hand side on stack
  • then decides which production to use

We look at this rightmost derivation backwards, so:

  • left-to-right parsing
  • rightmost derivation (when going from start, replace rightmost non-terminal)
  • we display it backwards (from strings to start symbol)

Consider grammar

E ::= T | E + T
T ::= ID
ID + ID + ID
 T + ID + ID
 E + ID + ID
 E +  T + ID
 E + ID
 E +  T

LR Parser looks at the largest suffix on stack that corresponds to RHS

  • if found, can reduce: replace suffix on stack by non-terminal
  • alternatively, can shift input symbol onto stack