Compiler Design
Bottom-Up Parsing & Shift-Reduce
Bottom-Up Parsing Concept
Bottom-Up Parsing is a parsing strategy that begins at the leaf nodes (the input string terminals) and attempts to merge them step-by-step upward until they reach the root node (the start symbol).
Specifically, a bottom-up parser constructs the Rightmost Derivation in Reverse. As the parser scans the input, it identifies a substring that matches the right-hand side of a production rule and reduces it to the left-hand non-terminal.
Parser Actions
A shift-reduce parser maintains an input buffer and a stack. It decides its moves based on four fundamental actions:
1. Shift
Read the next input symbol from the buffer, push it onto the parser stack, and advance the input pointer.
2. Reduce
When the top of the stack matches the right-hand side of a production rule, pop those symbols off and push the corresponding left-hand non-terminal variable.
3. Accept
If the stack contains only the start symbol and the input buffer is exhausted (contains only $), declare successful parse completion.
4. Error
If the parser cannot perform a shift or reduce action, invoke error recovery syntax diagnostics.
Handles and Handle Pruning
Informally, a handle of a right-sentential form γ is a substring β that matches the right side of a production rule A → β, and whose reduction to A represents one step of the rightmost derivation in reverse.
Handle Pruning is the process of locating a handle in a right-sentential form and replacing it with the non-terminal, working backwards to reconstruct the derivation.
An LR parser is driven by a stack containing state symbols, an input buffer, and two parsing tables (ACTION and GOTO).