Bottom-up parsing and LR

Why it exists

A shift-reduce parser must decide, at every moment, whether to shift or to reduce, and by which production. Looking through the stack for a handle would be slow and ambiguous. The LR parser solves it with a finite automaton: the stack stores, together with every grammar symbol, the state of an automaton that has already read the whole stack. The state and the next input token then determine the move, by a table look-up. LR parsing is fast (linear time), handles the largest class of grammars of any deterministic bottom-up method, detects errors at the earliest token, and can be generated automatically from the grammar.

Prerequisites

You need shift-reduce parsing, handles and viable prefixes (shift-reduce parsing). The tables are built from FIRST and FOLLOW or from lookahead sets on the next pages.

Precise definitions

LR($k$). Left-to-right scan of the input, Rightmost derivation in reverse, $k$ tokens of lookahead. The parser makes every decision from the stack contents and the next $k$ tokens. In GATE, $k$ is 0 or 1. A grammar is LR($k$) if such a parser exists for it. LR(1) grammars generate exactly the deterministic context-free languages, so nothing is gained by using $k > 1$ for the languages (some grammars become simpler).

The LR parser. An input buffer ending in $, a stack that alternates states and grammar symbols $s_0 X_1 s_1 X_2 s_2 \cdots X_m s_m$ (the top is $s_m$), and a parsing table with two parts:

• ACTION[$s$, $a$] for a state $s$ and a terminal (or $) $a$: one of
  • shift $j$: push $a$ and the state $j$;
  • reduce $A \to \beta$ (written $r_k$ for production number $k$): pop $2|\beta|$ entries ($|\beta|$ symbols and their states), let $t$ be the new top state, push $A$ and GOTO[$t$, $A$];
  • accept;
  • error (an empty cell).
• GOTO[$s$, $A$] for a state $s$ and a nonterminal $A$: the state to push after a reduction to $A$.

Algorithm. Let $s$ be the state on top and $a$ the next token. Look up ACTION[$s$, $a$] and do what it says; repeat until accept or error. The sequence of reductions is a rightmost derivation in reverse. The cost is linear in the input length: every token is shifted once and the number of reductions is bounded by the size of the tree.

Configuration. A pair (stack, remaining input). The stack contents $X_1 \cdots X_m$ plus the input is a right-sentential form.

Error detection. The parser reports an error as soon as it looks at an empty ACTION cell. LR parsers (like LL(1) parsers) have the viable-prefix property: they never shift a token that cannot extend a valid prefix of some sentence, so the error is detected at the earliest possible token (canonical LR(1); SLR and LALR may perform some extra reductions before noticing the error, but never shift the offending token).

The four table-building methods (details on the next two pages):

All four use the same driver; only the way the table is filled differs. The size of the table (the number of states) is the number of LR(0) states for LR(0), SLR and LALR, and larger for canonical LR(1).

Why LR is more powerful than LL. An LL parser must pick a production after seeing only the first token that the production derives. An LR parser waits until the whole right side has been seen (and one more token). Left recursion is natural for LR (and keeps the stack shallow); it is fatal for LL.

How it works

The animation parses $\text{id} + \text{id} * \text{id}$ with the SLR(1) table of the expression grammar. The stack alternates states and symbols (the top is at the right). The cell consulted in the table is outlined at each step. For a reduce you also see in the explanation which GOTO entry gives the next state. Follow one reduce slowly: in the step "reduce $T \to F$" the parser pops two stack entries (the symbol $F$ and its state 3), looks at the state that is now on top (0), reads GOTO[0, $T$] = 2, and pushes $T$ and 2.

The next animation shows an error. After id + the state is 6 and the parser sees another +: the cell ACTION[6, +] is empty, because after a plus an operand must come. The error is reported at that token, without shifting it.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The method is the table-driven form of shift-reduce parsing. The finite automaton and the first two table methods are in LR(0) and SLR(1); the lookahead-based methods are in CLR(1) and LALR(1); all are compared with LL(1) in the parser hierarchy. The semantic actions attached to reductions compute attributes in syntax-directed definitions.

PYQs

Which one of the following kinds of derivation is
used by LR parsers?

Self-check

Revision card

References