Building a parse tree bottom-up requires an algorithm to decide when a group of tokens forms a complete grammatical unit (a handle) and should be replaced by a non-terminal. The parser needs a systematic way to stack input and identify production right-hand sides.
A shift-reduce parser is the basic framework for bottom-up parsing. It uses a stack to hold grammar symbols and an input buffer. The parser repeatedly shifts input tokens onto the stack until it recognizes a handle (a production right-hand side) at the top of the stack, then reduces by popping the handle and pushing the corresponding non-terminal.
The parser has four possible actions: shift (push next input token onto stack), reduce (pop handle, push non-terminal), accept (parsing successful), or error (syntax error). The parser continues shifting and reducing until it reduces the entire input to the start symbol. Conflicts arise when the parser can both shift and reduce (shift/reduce conflict) or reduce by two different productions (reduce/reduce conflict).
- Stack-based: Grammar symbols are pushed/popped from a stack
- Four actions: Shift, Reduce, Accept, Error
- Handle identification: The parser must identify handles correctly
- Conflicts: Shift/reduce and reduce/reduce conflicts require resolution rules
- Foundation: LR parsers (SLR, CLR, LALR) are shift-reduce parsers with decision tables
- Built from: Bottom-Up Parsing — shift-reduce is the mechanism for bottom-up parsing
- Builds into: LR Parsers — SLR, CLR, and LALR extend shift-reduce with state-based decision tables
- Related: Operator Precedence Parser — a simpler shift-reduce variant using operator precedence relations
- Related: Syntax Analysis — shift-reduce is a key parsing approach
- Related: Ambiguous Grammar — ambiguity causes shift/reduce and reduce/reduce conflicts
- Handle identification: The handle is always at the top of the stack — never buried — in viable prefix parsing
- Conflict resolution in Yacc: Yacc resolves shift/reduce conflicts in favor of shift, reduce/reduce in favor of the first production listed
- Default reductions: In ambiguous situations, the parser may make a default choice that doesn’t match the language designer’s intent