Bottom up Parsing

• 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)

Conflict

• 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.

Handle

• 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 $S^{\prime }\to S$ to $G$
  • 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:

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.

Links

• SLR Parsing
• LALR Parsing