Bottom Up Parsing

Bottom-Up Parsing (Shift-Reduce)

Bottom-Up parsers start at the leaves of the tree (the input tokens) and work their way up to the Start Symbol by iteratively matching the Right-Hand Side (RHS) of a production rule and Reducing it back to its Left-Hand Side (LHS) non-terminal.

AutomataLab supports four deterministic bottom-up algorithms, from simplest to most powerful: LR(0), SLR(1), LALR(1), and CLR(1).

---

1. The Parser Automaton (Item Sets)

All LR parsers work by building a massive Deterministic Finite Automaton (DFA) behind the scenes.

• The states of this DFA are called Item Sets.
• An Item is a production rule with a dot • indicating how far the parser has progressed in matching that rule (e.g., $E \rightarrow E \bullet + T$).
• When the dot reaches the end of the rule (e.g., $E \rightarrow E + T \bullet$), it's a signal that the parser can perform a Reduce action.

Pro-Tip: Click the View Automaton button in the Parser Studio to visually explore this generated DFA and all of its Item Sets!

---

2. Shift and Reduce Actions

As the parser reads the input stream, it looks at the Parse Table to decide between two primary actions:

• Shift: Push the current input token onto the stack and transition to a new Item Set state. The dot moves forward •.
• Reduce: Pop the symbols matching the RHS of a production rule off the stack, and replace them with the LHS non-terminal. Then, follow the GOTO table.

---

3. The Four LR Parsers Explained

If multiple rules apply, conflicts occur. The four algorithms differ purely in how strictly they decide when to place a Reduce action in the Parse Table.

LR(0)

The simplest parser. If an Item Set contains a completed rule (the dot is at the end), LR(0) simply places a Reduce action across the entire row for all possible lookahead tokens.

• Conflicts: Extremely high. It almost always results in Shift/Reduce conflicts because it blindly reduces without checking if the next token actually makes grammatical sense.

SLR(1) - Simple LR

A massive upgrade. Before placing a Reduce action for rule $A$, SLR(1) checks the mathematical FOLLOW($A$) set (calculated in the Grammar Lab). It will only place the Reduce action in the columns of the lookahead tokens that are actually allowed to follow $A$.

• Conflicts: Much lower. This resolves the vast majority of simple Shift/Reduce conflicts.

CLR(1) - Canonical LR

The most powerful (but memory-heavy) parser. Instead of relying on the global FOLLOW set, CLR(1) tracks the exact, specific lookahead tokens during the Item Set generation. This prevents rare corner-case conflicts that SLR(1) misses.

• Conflicts: Minimal. If CLR(1) has conflicts, your grammar is fundamentally ambiguous and must be rewritten.
• Trade-off: The DFA size explodes exponentially, generating massive Parse Tables.

LALR(1) - Look-Ahead LR

The industry standard (used by YACC and Bison). LALR(1) is a genius compromise. It generates the massive CLR(1) state machine, but then aggressively merges any Item Sets that have the identical core items, combining their lookahead tokens.

• Result: You get the precise lookahead power of CLR(1) but the compressed, smaller Parse Table size of SLR(1)!

---

4. Conflict Visualization

If you build an LR parser and the table has red cells, you have a conflict.

• Shift/Reduce Conflict: The parser sees a token and doesn't know whether to Shift it onto the stack or Reduce the current stack. E.g., the infamous "Dangling Else" problem in programming languages.
• Reduce/Reduce Conflict: The parser knows it needs to Reduce, but it has two completed production rules that both match the stack, and it can't definitively pick one.

Clicking a red cell in AutomataLab will explicitly show you which two actions are colliding.

See Also

• Top-Down Parsing
• General Parsing