• Preferred method
  • A bottom-up parser traces a rightmost derivation in reverse. Reduces a string to the start symbol by inverting productions
  • Do not require Left refactor.
  • For any grammar, the set of viable prefixes is a regular language

Shift Reduce Parsing

  • Split the string into 2 substring.
    • Left: Non-Terminals and Terminals
    • Right: Terminals
  • Shift:
    • move a terminal to the left string
    • Apply an inverse production at the right end of the left string
    • Push a terminal to the stack, top of the stack is the |
  • Reduce
    • pops symbols off of the stack (production rhs)
    • pushes a non-terminal on the stack (production Ihs)


  • If it is legal to both shift or reduce, there is a shift-reduce conflict
    • Recoverable
  • If it is legal to reduce by two different productions, there is a reduce-reduce conflict
    • Grammar error.


  • We only want a reduction at handles
    • A handle is a reduction that also allows further reductions back to the start symbol
    • handles appear only at the top of the stack, never inside
    • Bottom-up parsing algorithms are based on recognising handles

Viable Prefix

Used to recognise handle, guide the right direction of reduce

  • Recognising VP
    • Add a dummy production to
    • The NFA States are the items of G
      • We either extend (follow) or epsilon transaction (with production)
      • Every state is an accepting state
    • The states of the DFA are “canonical collections of LR(0) items”

Valid Item

definition: image.png

LR Parser

  • action table Action[s, a]
    • shift: push to stack
    • reduce: pop the rhs off the stacks, Goto table gives a new state to push on the stack. The input is unchanged
    • accept
    • error
  • goto table Goto[s, X] the action table specifying entries for terminals, and the goto table specifying entries for nonterminals.