Bottom-Up Parsing and Shift-Reduce

A bottom-up parser builds the parse tree from the leaves up to the root. It starts from the input string and repeatedly replaces a substring that matches the body of a production by the production's head, a step called a reduction, until only the start symbol remains. Read backwards, the sequence of reductions is a rightmost derivation of the input.

The general mechanism is shift-reduce parsing: a stack holds grammar symbols, the parser either shifts the next input token onto the stack or reduces a group of symbols on top of the stack, and the whole difficulty is knowing when to reduce and by which production. The LR family of parsers (LR(0), SLR, LALR, canonical LR) answers that question with automata; operator-precedence parsing answers it, for a restricted class of grammars, with precedence relations between terminals. This note gives the mechanism, the vocabulary (handles, viable prefixes, conflicts) and operator precedence; the LR tables follow in the next notes.

The running grammar is the layered expression grammar

which is left-recursive and therefore unsuitable for LL(1) parsing, but is handled directly by bottom-up parsers. The parser's working storage is a stack, and a shift-reduce parser is a deterministic pushdown automaton whose stack holds grammar symbols (or states).

The handle is always on top of the stack. In a shift-reduce parser the handle never appears buried inside the stack: once the right end of a handle has been shifted, the parser reduces before shifting again. That is why a stack suffices.

Unambiguous grammars have unique handles. Every right-sentential form of an unambiguous grammar has exactly one handle. An ambiguous grammar can have two, which is why it always causes conflicts in any deterministic shift-reduce parser.

A handle is not just any matching body. In the right-sentential form E + T * id, the substring E + T matches the body of $E \to E + T$, but reducing it gives E * id, which is not a right-sentential form of this grammar. The handle is id (by $F \to \textbf{id}$).

Parsing id * id + id (stack bottom is $\text{\textdollar}$, top at the right):

There are 5 shifts (one per token) and 8 reductions (one per interior node of the parse tree, that is, one per step of the rightmost derivation). Two decisions show why a parser needs more than the stack contents:

The decision depends on the next token, which is exactly what LR parsing tables encode.

Reading a rightmost derivation backwards, each right-sentential form has one handle:

Measured in input tokens covered, the right end of each handle never moves left: 1, 1, 1, 3, 3, 5, 5, 5. That is why the handle is always on top of the stack. In E + T * id, T is not reduced to $E$ although $E \to T$ matches: reducing it would give E + E * id, which is not a right-sentential form.

Every stack in the trace is a viable prefix: T *, T * F, E + T, and so on. Some strings are not: E + T + is never a stack content, because before + is shifted after E + T the handle E + T must be reduced. The set of viable prefixes of any grammar is a regular language; the LR(0) automaton of the next note is a DFA that recognises it, and that fact is what makes LR parsing possible.

An operator grammar has no $\varepsilon$-productions and no production body with two adjacent nonterminals. For such grammars a shift-reduce parser can decide using three relations between terminals:

Relations are read between the topmost terminal on the stack (ignoring nonterminals) and the next input token. From precedence and associativity: if $\theta_1$ has higher precedence than $\theta_2$, then $\theta_1 \gtrdot \theta_2$ and $\theta_2 \lessdot \theta_1$; for equal precedence, left-associative operators give $\theta_1 \gtrdot \theta_2$ and $\theta_2 \gtrdot \theta_1$, right-associative ones give $\lessdot$ both ways; every operator $\lessdot$ id and id $\gtrdot$ every operator; $\text{\textdollar} \lessdot$ everything and everything $\gtrdot \text{\textdollar}$.

For + and * (both left-associative, * higher), with rows the stack terminal and columns the input token:

The parse of id + id * id with this table (each reduced handle becomes an unnamed nonterminal N):

There are 5 shifts and 5 reductions, against 8 reductions in the LR parse of the layered grammar: an operator-precedence parser never performs the unit reductions $T \to F$ and $E \to T$, because it does not track which nonterminal is on the stack.

An operator-grammar trap. E -> E A E | id, A -> + | * is not an operator grammar: the body E A E has two adjacent nonterminals. Substituting for $A$ gives E -> E + E | E * E | id, which is an operator grammar (and ambiguous, which operator precedence tolerates, because the relations choose the grouping).

Precedence functions. The table can be compressed into two integer functions $f$ (stack side) and $g$ (input side) with $a \lessdot b \implies f(a) < g(b)$ and $a \gtrdot b \implies f(a) > g(b)$. For the table above one solution is $f(\textbf{id}) = 4, g(\textbf{id}) = 5$, $f(+) = 2, g(+) = 1$, $f(*) = 4, g(*) = 3$, $f(\text{\textdollar}) = g(\text{\textdollar}) = 0$. Each defined equal-precedence relation similarly requires $f(a)=g(b)$; these implications apply to defined relations, not blank/error entries. The price is that blank (error) entries disappear: every pair now compares, so some errors are detected later.

Operator-precedence parsing handles only a small class of grammars and has trouble with operators such as unary minus that share a symbol with a binary one; it is mainly used for expressions.

The same rules decide how an expression is grouped. Take 2 + 3 * 4 - 5: