Shift-reduce parsing and handles

Why it exists

A top-down parser must choose a production before it has seen the input that production will derive. A bottom-up parser waits: it reads tokens, keeps them on a stack, and only when the symbols on top of the stack form the right side of a production does it replace them by the left side. It decides later, with more information, so it handles a larger class of grammars (left recursion included) than LL(1) does. Every practical parser generator (Yacc, Bison) builds a bottom-up parser.

Prerequisites

You need grammars, derivations and parse trees (ambiguity and grammar transformations) and the stack (stack ADT). Recall that in a rightmost derivation the rightmost nonterminal is replaced at every step, and that a sentential form produced by one is a right-sentential form.

Precise definitions

Reduction. The opposite of a derivation step: replace a substring that matches the right side of a production $A \to \beta$ by $A$. Parsing a sentence bottom-up means reducing it step by step to the start symbol.

Bottom-up parsing = rightmost derivation in reverse. If $S \Rightarrow_{rm} \gamma_1 \Rightarrow_{rm} \dots \Rightarrow_{rm} w$, the bottom-up parser finds the steps in the opposite order: $w$, then $\gamma_{n-1}$, then ..., then $S$. The parse tree is built from the leaves up.

Handle. In a right-sentential form $\gamma$, a handle is a substring $\beta$ together with a production $A \to \beta$ such that replacing $\beta$ by $A$ gives the previous right-sentential form in some rightmost derivation. In other words, the handle is the right side that has to be reduced next, at its particular position (the same substring can occur twice and only one occurrence is the handle). For an unambiguous grammar every right-sentential form has exactly one handle. The handle of a form is its leftmost complete subtree of height one (a node whose children are all leaves of the current form).

Handle pruning. Reducing the handle, then the handle of the new form, and so on until the start symbol is reached, is called handle pruning; it gives the rightmost derivation backwards. The whole difficulty of bottom-up parsing is finding the handle.

The shift-reduce parser. It has a stack (symbols; the top is at the right) and the input buffer, which ends in $. Initially the stack is empty. The stack together with the unread input always spells a right-sentential form. The moves are:

1. Shift: move the next input token on to the stack.
2. Reduce: the top of the stack is the right side $\beta$ of a production $A \to \beta$ (the handle): pop it and push $A$.
3. Accept: the stack holds only the start symbol and the input is $.
4. Error: no valid move.

The key fact that makes a stack sufficient: the handle is always at the top of the stack, never inside it. So the parser never needs to search the stack: after a reduce, the new handle (if any) again ends at the top; otherwise it shifts.

Viable prefix. A prefix of a right-sentential form that does not extend past the right end of the rightmost handle. The stack contents of a correct shift-reduce parser are always viable prefixes, and an error is detected as soon as the stack plus the next token is no longer a viable prefix. The set of viable prefixes of a grammar is a regular language, recognised by the DFA of LR(0) items that is built on the next pages.

Conflicts. Given only the stack and the next token the parser may have more than one choice.

• Shift-reduce conflict: both a shift and a reduce are possible. Typical cause: ambiguity of operators or the dangling else.
• Reduce-reduce conflict: two different reductions are possible (two different handles end at the top). Typical cause: two nonterminals with the same right side.

A grammar for which a deterministic shift-reduce parser (with a given amount of lookahead and a given table-building method) makes no such choice is an LR grammar of the corresponding class (LR parsing). Parser generators resolve a shift-reduce conflict in favour of shift and a reduce-reduce conflict in favour of the production listed first, unless the grammar author gives precedence declarations. Every ambiguous grammar has at least one conflict in every LR table; this is why ambiguity must be removed or declared.

How it works

Step through the parse of $\text{id} + \text{id} * \text{id}$ with the layered expression grammar. The stack is on the left (top at the right), the unread input on the right, and the tree is built as a forest that merges into one tree. Watch two things. First, after each shift, either a reduce follows or another shift does. Second, the stack plus the input is always a right-sentential form, so the sequence of reductions, read from the end to the start, is a rightmost derivation: $E \Rightarrow E + T \Rightarrow E + T * F \Rightarrow E + T * \text{id} \Rightarrow E + F * \text{id} \Rightarrow E + \text{id} * \text{id} \Rightarrow T + \text{id} * \text{id} \Rightarrow F + \text{id} * \text{id} \Rightarrow \text{id} + \text{id} * \text{id}$.

(The parser in the animation decides between shift and reduce with the table explained on the next pages; here only the moves matter.) Notice that with the stack $E + T$ and the next token *, the parser must shift, not reduce $E \to E + T$. That is the multiplication binding tighter: reducing too early would produce $(E + T) * \text{id}$. The choice looks at the next token, which is why one token of lookahead is part of the method.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Shift-reduce parsers are made deterministic by LR parsing, whose tables decide between shift and reduce. The finite automaton of viable prefixes is built from items in LR(0) and SLR. The top-down alternative is LL(1) parsing; the two are compared in the parser hierarchy. Ambiguity and its removal are in grammar transformations.

PYQs

Which of the following is/are Bottom-Up Parser(s)

Consider the following grammar.

S →aSB| d

B →b

The number of reduction steps taken by a bottom-
up parser while accepting the string aaadbbb is
_______.

Which one of the following is True at any valid
state in shift-reduce parsing?

What is the maximum number of reduce moves that
can be taken by a bottom-up parser for a grammar
with no epsilon-and unit-production (i.e. of type

A → ε and A → a) to parse a string with n tokens?

Which of the following describes a handle (as
applicable to LR-parsing) appropriately?

Consider the grammar
                                          E → E + n | E × n | n

For a sentence n + n × n, the handles in the right-
sentential form of the reduction are

Self-check

Revision card

References