Bottom-Up Parsing

• A bottom-up parser builds a derivation from the terminal symbols, working toward the start symbol.
• It consists of a stack and an input .
• Four actions:
  • shift , which pushes the next token onto the stack
  • reduce , removes Y1, ...,Yk, which are the right-hand side of some production X = Y1 ... Yk. From the top of the stack and replaces them by X.
  • accept , ends the parser with success.
  • error , ends the parser with an error message.
• Question: How does the parser know, which action to invoke.