Top-down parsing builds a parse tree by starting with the grammar's start symbol and working its way down toward the actual input tokens, essentially guessing which rule to expand next and hoping it eventually matches what is in front of it. Bottom-up parsing takes the exact opposite approach. Instead of starting with an abstract goal and trying to reach the input, it starts directly with the input tokens themselves and works backward, gradually combining them into larger and larger structures until the entire input has been reduced back to the grammar's start symbol.
This shift in direction might sound like a small technical detail, but it has a significant practical impact. Bottom-up parsing techniques, and in particular the family of algorithms built around shift-reduce parsing, are able to handle a much wider range of grammars than simple top-down techniques, without requiring the same kind of restrictive rewriting like removing left recursion or left factoring. This is a major reason why many real-world compiler generation tools are built around bottom-up parsing rather than top-down parsing.
In this tutorial, you will learn what bottom-up parsing means conceptually, how shift-reduce parsing works using a parsing stack, what a handle is and how handle pruning relates to reduction, how shift-reduce and reduce-reduce conflicts arise, and how bottom-up parsing compares to the top-down techniques covered in the previous tutorial.
Bottom-up parsing works by repeatedly identifying a small piece of the input that matches the right-hand side of some production rule, and replacing that piece with the corresponding non-terminal on the left-hand side of the rule. This replacement step is called a reduction. The parser continues applying reductions, working its way up through larger and larger groupings, until the entire input has been reduced down to a single symbol, the grammar's start symbol, at which point the input is confirmed to be valid.
This process is essentially the reverse of a derivation. Where a derivation starts from the start symbol and expands it step by step to eventually produce a specific string, bottom-up parsing starts from that string and works backward, applying the same production rules in reverse, until it arrives back at the start symbol. Because of this relationship, a successful bottom-up parse effectively constructs what is known as a rightmost derivation, but in reverse order.
Grammar: Expression -> Expression + Term | Term Term -> Identifier Input: a + b Reduction Steps: a + b Term + b (reduce 'a' to Term) Expression + b (reduce Term to Expression) Expression + Term (reduce 'b' to Term) Expression (reduce Expression + Term to Expression)
Notice how each step replaces a small piece of the current string with a non-terminal, gradually shrinking the string until only the start symbol, Expression, remains. This sequence of reductions, read in reverse, is exactly the same as a derivation that a top-down parser might have produced for the same input.
Shift-reduce parsing is the most widely used strategy for implementing bottom-up parsing in practice. It works using two simple operations, a shift and a reduce, applied to a data structure called a parsing stack, along with the remaining unread portion of the input.
| Operation | Description |
|---|---|
| Shift | Move the next input token from the unread input onto the top of the parsing stack. |
| Reduce | Replace a sequence of symbols at the top of the stack with the non-terminal from the left-hand side of a matching production rule. |
At every point during parsing, the parser must decide whether to shift the next token onto the stack or to reduce whatever is currently at the top of the stack. This decision-making process continues until either the entire input has been consumed and reduced down to the start symbol, indicating success, or the parser reaches a state where neither a valid shift nor a valid reduce is possible, indicating a syntax error.
Grammar: Expression -> Expression + Term | Term Term -> Identifier Input: a + b Step-by-Step Parsing: Stack: (empty) Input: a + b Action: Shift 'a' Stack: a Input: + b Action: Reduce a -> Term Stack: Term Input: + b Action: Reduce Term -> Expression Stack: Expression Input: + b Action: Shift '+' Stack: Expression + Input: b Action: Shift 'b' Stack: Expression + b Input: (empty) Action: Reduce b -> Term Stack: Expression + Term Input: (empty) Action: Reduce Expression + Term -> Expression Stack: Expression Input: (empty) Action: Accept
This trace shows the parser gradually building up the stack, shifting tokens on when needed and reducing groups of symbols back into non-terminals whenever a matching production rule is found, until only the start symbol remains on the stack with no input left to process, at which point the parse is accepted as valid.
A central concept in shift-reduce parsing is the idea of a handle. A handle is a substring at the top of the parsing stack that matches the right-hand side of some production rule, and that can be validly reduced at this point in the parse in a way that still leads toward a correct overall derivation. Not every substring that happens to match a production's right-hand side is necessarily a handle; it must be the correct one to reduce given the current context of the parse.
The overall process of bottom-up parsing is sometimes described as handle pruning, since at each step, the parser is essentially searching for the current handle on the stack and "pruning" it away by reducing it to the corresponding non-terminal, gradually working backward through what would have been a rightmost derivation of the input.
Stack Contents: Expression + Term Handle: Expression + Term Reduction: Expression + Term -> Expression
In this case, the entire sequence "Expression + Term" on the stack matches the right-hand side of the production Expression -> Expression + Term, and reducing it at this point correctly continues building toward a valid overall parse, which is exactly what qualifies it as the handle at this step.
A shift-reduce conflict occurs when, at a particular point during parsing, the parser cannot determine whether it should shift the next input token onto the stack or reduce the symbols currently at the top of the stack, because both actions appear to be valid according to the grammar.
Grammar Fragment:
Statement -> if ( Condition ) Statement
| if ( Condition ) Statement else Statement
Situation:
After parsing "if ( Condition ) Statement", the parser must decide whether to reduce immediately, treating the if statement as complete, or shift the token "else" and continue, anticipating the second production rule.
This particular example is a well-known situation often referred to as the dangling-else problem. Compiler designers typically resolve this specific conflict by establishing a rule, usually preferring to shift rather than reduce, which has the effect of associating an else clause with the nearest unmatched if statement, matching how most programmers intuitively expect such code to behave.
A reduce-reduce conflict occurs when the symbols currently at the top of the parsing stack match the right-hand side of more than one production rule, and the parser cannot determine which rule should be used for the reduction.
Grammar Fragment: Parameter -> Identifier Argument -> Identifier Situation: If the grammar allows Identifier to be reduced to either Parameter or Argument in the same context, without any other distinguishing information, the parser cannot determine which non-terminal is correct.
Reduce-reduce conflicts generally indicate a deeper ambiguity or design issue in the grammar itself, and they are usually considered more serious than shift-reduce conflicts. Resolving them typically requires restructuring the grammar so that the two conflicting rules can be distinguished based on the surrounding context, rather than relying on an arbitrary tie-breaking rule.
Having studied both parsing strategies now, it is worth directly comparing them to understand why compiler designers often reach for bottom-up techniques when building parsers for real, full-scale programming languages.
| Aspect | Top-Down Parsing | Bottom-Up Parsing |
|---|---|---|
| Direction of Tree Construction | From the root toward the leaves. | From the leaves toward the root. |
| Relationship to Derivations | Directly constructs a leftmost derivation. | Constructs a reverse of a rightmost derivation. |
| Handling of Left Recursion | Cannot handle left-recursive grammars without rewriting them first. | Can generally handle left-recursive grammars without any special modification. |
| Implementation Complexity | Often simpler to implement by hand, especially using recursive descent. | Typically more complex to implement by hand, usually built using automatically generated parsing tables. |
| Grammar Coverage | Restricted to a more limited class of grammars, such as those suitable for LL(1) parsing. | Capable of handling a broader class of grammars, including those used by LR-based parsing techniques. |
This comparison helps explain why many industrial-strength compilers and parser generation tools rely on bottom-up parsing techniques internally, even though top-down parsing remains popular for smaller projects and for teaching the fundamental concepts of parsing, thanks to its more direct and approachable implementation style.
Bottom-up parsing forms the theoretical basis for some of the most powerful and widely used parsing algorithms in Compiler Design, including SLR, CLR, and LALR parsing, all of which will be explored in detail in the dedicated tutorial on LR parsing later in this series. These algorithms extend the basic shift-reduce approach introduced here with systematically constructed parsing tables that eliminate the need for a human to manually decide when to shift or reduce, instead deriving that information automatically from the grammar itself.
Beyond programming language compilers, the underlying ideas behind shift-reduce parsing appear in a variety of other tools that need to process structured input reliably, including certain configuration file parsers and specialized text-processing utilities that must handle a wide range of possible input structures without relying on restrictive grammar rewriting.
| Mistake | Correct Understanding |
|---|---|
| Assuming a handle is simply any substring that matches a production's right-hand side. | A handle must be the specific substring that is correct to reduce at this exact point in the parse, in a way that leads toward a valid overall derivation. |
| Believing shift-reduce conflicts always indicate a broken or unusable grammar. | Many shift-reduce conflicts, such as the dangling-else problem, can be resolved using a consistent tie-breaking rule without changing the grammar itself. |
| Treating reduce-reduce conflicts with the same casual tie-breaking approach as shift-reduce conflicts. | Reduce-reduce conflicts usually signal a deeper ambiguity in the grammar and often require restructuring the grammar rather than a simple tie-breaking rule. |
| Thinking bottom-up parsing constructs a leftmost derivation, just like top-down parsing. | Bottom-up parsing constructs the reverse of a rightmost derivation, not a leftmost derivation. |
Bottom-up parsing builds a parse tree by starting with the input tokens and working upward, repeatedly identifying and reducing handles until the entire input collapses into the grammar's start symbol. Shift-reduce parsing implements this idea using a parsing stack and two operations, shift and reduce, deciding at each step which action correctly continues the parse. Conflicts between these decisions, whether shift-reduce or reduce-reduce, must be carefully resolved, either through consistent tie-breaking rules or through restructuring the grammar itself. Compared to top-down parsing, bottom-up parsing can handle a significantly wider range of grammars, including those with left recursion, which is a major reason it forms the foundation for many powerful, table-driven parsing algorithms.
In this tutorial, you learned the core idea behind bottom-up parsing, how shift-reduce parsing works using a parsing stack traced through a complete example, what a handle is and how handle pruning drives the parsing process, how shift-reduce and reduce-reduce conflicts arise and are resolved, and how bottom-up parsing compares to the top-down techniques covered earlier. With this foundation in place, you are ready to explore LL(1) parsing, where FIRST and FOLLOW sets are used to build a complete, table-driven predictive parser.