Shift-Reduce Parsing Actions
What you'll learn: You'll understand the four fundamental operations that a shift-reduce parser uses to build a parse tree from the bottom up.
The Core Idea
A shift-reduce parser is like a worker assembling a product from parts, making decisions at each step about whether to grab more pieces or combine what's already on the workbench. At every moment, the parser must choose one of four actions to process the input tokens and build a parse tree.
The Four Basic Actions
1. Shift
Move the next input token onto the parser's stack (the "workbench"). This is like saying "I need this piece for later assembly."
2. Reduce
Recognize that the top symbols on the stack match the right-hand side of a production rule, and replace them with the rule's left-hand side non-terminal. This is the actual "assembly" step—combining parts into a larger component according to grammar rules (using handles, as you learned previously).
3. Accept
Declare success! The entire input has been consumed, and the stack contains just the start symbol. The parse is complete and valid.
4. Error
Detect that the input doesn't conform to the grammar. Neither shifting nor reducing leads to a valid parse state. The parser must report a syntax error.
How They Work Together
The parser examines its current stack and the next input token, then consults its parsing strategy to decide which action to take. Shift brings in raw material, reduce builds structures using viable prefixes and handles, accept confirms a successful parse, and error catches invalid input.
Key Takeaway: Shift-reduce parsing operates through exactly four actions—shift (add token to stack), reduce (apply grammar rule), accept (parsing succeeds), and error (syntax violation detected)—forming the complete operational foundation of bottom-up parsers.