CLR(1) and LALR(1)

Why it exists

SLR(1) decides a reduction with FOLLOW($A$), the set of every token that can follow $A$ anywhere. In one particular state fewer tokens are actually possible, so SLR sometimes sees a conflict that is not real (the $L = R$ grammar). The remedy is to remember, inside each item, which tokens can follow in this context. That gives the canonical LR(1) parser, the most powerful of the deterministic methods, with a big table. LALR(1) then shrinks the table to the size of the LR(0) one by merging states that differ only in lookaheads, keeping most of the power. Yacc and Bison build LALR(1) parsers.

Prerequisites

You need items, closure and goto from LR(0) and SLR, and FIRST sets (FIRST and FOLLOW).

Precise definitions

LR(1) item. A pair $[A \to \alpha \cdot \beta,\ a]$: an LR(0) item (the core) plus a lookahead terminal $a$ (or $). Meaning: the parser has seen $\alpha$ and hopes to see $\beta$, and when the whole right side has been seen it may reduce only if the next token is $a$. Items with the same core and different lookaheads are written together: $[A \to \alpha \cdot \beta,\ a/b]$.

Closure of a set of LR(1) items. Repeat: for every item $[A \to \alpha \cdot B \beta,\ a]$ in the set, every production $B \to \gamma$ and every terminal $b$ in $\text{FIRST}(\beta a)$, add $[B \to \cdot \gamma,\ b]$. Here $\text{FIRST}(\beta a)$ means FIRST of the string $\beta$ followed by $a$: it is $\text{FIRST}(\beta)$, plus $a$ if $\beta$ can vanish. The reasoning: after $B$ comes $\beta$, and then whatever comes after $A$, namely $a$.

Goto is as before: move the dot over $X$ in every item that has $X$ after the dot, keep the lookahead, then close. The start state is the closure of $[S' \to \cdot S,\ \mathdollar]$.

Canonical LR(1) (CLR(1)) table. From the collection of LR(1) item sets: shifts and GOTO as in SLR; for a complete item $[A \to \alpha \cdot,\ a]$ with $A \ne S'$, ACTION[$i$, $a$] = reduce $A \to \alpha$ — only on the lookahead $a$; $[S' \to S \cdot,\ \mathdollar]$ gives accept. A grammar is LR(1) if there is no conflict. Because lookaheads are exact, CLR(1) detects errors without any extra reductions.

Size. States with the same core but different lookaheads are different states, so the canonical LR(1) automaton can have many more states than the LR(0) automaton (22 against 12 for the standard expression grammar; hundreds or thousands for a programming language).

LALR(1). Take the canonical LR(1) states and merge those that have the same core (the same LR(0) items), taking the union of the lookaheads item by item. The merged automaton has exactly the states of the LR(0) automaton (so the same number as SLR(1)); the transitions are those of the merged states. The table is filled as for CLR(1) but with the merged lookaheads. (In practice the lookaheads are computed directly from the LR(0) states by propagation, without building the whole LR(1) automaton.)

What merging does:

• It can never create a shift-reduce conflict. Shift actions depend only on the core (the symbols after the dot), which is identical in the merged states; a new conflict would need a reduce lookahead equal to a shift symbol in the merged state, and that already existed in one of the merged states (where the same core and shift were present, with the lookahead of the other). So if the canonical LR(1) table has no shift-reduce conflict, neither has the LALR(1) table.
• It can create reduce-reduce conflicts. Two complete items in one core may have disjoint lookaheads in each separate state but overlapping lookaheads after the union.
• It can delay error detection: the parser may perform some reductions on an erroneous token (because merged lookaheads are larger), but it still never shifts the bad token.

So: $\text{LR(0)} \subset \text{SLR(1)} \subset \text{LALR(1)} \subset \text{LR(1)}$ (as classes of grammars), where $\subset$ means "properly contained", and the table sizes are the same for LR(0), SLR(1), LALR(1) and larger for LR(1).

How it works

Canonical LR(1) item sets for the standard small grammar $S \to C C$, $C \to c C \mid d$. State 0 is the closure of $[S' \to \cdot S, \mathdollar]$: closing $S \to \cdot C C$ with lookahead $ adds $C \to \cdot c C$ and $C \to \cdot d$ with lookahead FIRST($C \mathdollar$) = {c, d}. Following the gotos you get 10 states, while the LR(0) automaton has 7: for example the items $C \to c \cdot C$ appear in states 3 (lookahead c/d) and 6 (lookahead $), which have the same core.

LALR(1) merges the pairs with equal cores: (3, 6), (4, 7) and (8, 9). The result has 7 states, with unions of lookaheads such as $[C \to d \cdot,\ c/d/\mathdollar]$ in the merged state 4-7.

What can go wrong is shown by the grammar $S \to a A d \mid b B d \mid a B e \mid b A e$, $A \to c$, $B \to c$. After a c the lookahead tells $A$ from $B$ (d means $A$, e means $B$); after b c the other way round. In canonical LR(1) those are two different states, so there is no conflict. LALR merges them (the same core: $A \to c \cdot$, $B \to c \cdot$) and the lookahead sets overlap: a reduce-reduce conflict. The grammar is LR(1) but not LALR(1).

Finally the $L = R$ grammar from the previous page. LALR(1) keeps just one state for $S \to L \cdot = R$, $R \to L \cdot$, and the lookahead of the reduction $R \to L$ there is only $, so no conflict: it is LALR(1) (and LR(1)) but not SLR(1).

Worked examples

Cheat box

Traps and GATE patterns

Connections

LALR(1) builds on the item sets of LR(0) and SLR and uses the table-driven LR driver. FIRST sets are needed for the lookaheads (FIRST and FOLLOW). All four classes and LL(1) are compared with examples in the parser hierarchy.

PYQs

Which one of the following statements is TRUE?

Consider the following grammar G.

S → F | H

F → p | c

H →d | c

Where S, F and H are non-terminal symbols, p, d
and c are terminal symbols. Which of the following
statement(s) is/are correct?

S1: LL(1) can parse all strings that are generated
using grammar G.

S2: LR(1) can parse all strings that are generated
using grammar.

A canonical set of items is given below:

S → L.  > R

Q → R.

On input symbol < the set has:-

Consider the following two sets of LR(1) items of
an LR(1) grammar.

X→c. X, c/d                 X→ c. X, $
X-> .cX, c/d
X→ .cX, $
X→ .d, c/d
X→ .d, $

Which of the following statements related to
merging of the two sets in the corresponding LALR
parser is/are FALSE?

1. Cannot be merged since look ahead is different.

2. Can be merged but will result in S-R conflict.

3. Can be merged but will result in RR conflict.

4. Cannot be merged since goto on c will lead to
two different sets.

An LALR(1) parser for a grammar G can have
shift-reduce (S-R) conflicts if and only if

Consider the following expression grammar. The
seman-tic rules for expression calculation are stated
next to each grammar production.

E → number
 E.val = number. val

        | E '+' E
 E(1).val = E(2).val + E(3).val

        | E '×' E
 E(1).val = E(2).val × E(3).val

The above grammar and the semantic rules are fed to
a Yacc tool (which is an LALR (1) parser generator)
for parsing and evaluating arithmetic expressions.
Which one of the following is true about the action of
Yacc for the given grammar?

Self-check

Revision card

References