shiftreduce

Shift-reduce parsing is a bottom-up parsing technique used by compilers to analyze a stream of tokens according to a formal grammar. It operates with a stack that holds grammar symbols (terminals and nonterminals) and an input buffer containing the remaining input. A separate parsing table guides actions. The primary actions are shift (push the next input token onto the stack and advance the input), reduce (replace a sequence of symbols on the top of the stack that matches the right-hand side of a grammar rule with the rule’s left-hand side symbol), accept (successful parse), and error (parse failure).

The algorithm proceeds by repeatedly consulting the parsing table for the current state (derived from the symbol on top of the stack) and the current input token. If the action is shift, the parser pushes the token and advances. If the action is reduce, the parser pops the number of symbols on the right-hand side of the chosen rule, then pushes the left-hand side nonterminal, and may consult a goto table to determine the next state. If the action is accept, the input is part of a valid sentence in the language; if an error is reported, the input cannot be parsed by the grammar as written.

Variants of shift-reduce parsing include LR, SLR, and LALR parsers, which differ in how their parsing tables are constructed and how conflicts are resolved. Shift-reduce conflicts arise when a grammar permits both shifting and reducing actions in a given situation; these are typically resolved by grammar disambiguation, operator precedence and associativity rules, or grammar refactoring. Applications are common in compiler front-ends for programming languages, where linear-time parsing for unambiguous grammars yields efficient analysis.

Limitations include the need for grammars that are suitable for deterministic table-driven parsing and potential table size growth for larger grammars. Despite these constraints, shift-reduce parsing remains a foundational technique in language processing.