LR(0) and SLR(1) construction

Why it exists

An LR parser needs a table. The table is built from a finite automaton that recognises exactly the viable prefixes of the grammar, the strings that can appear on the stack. The automaton's states are sets of items that record how much of each production has been seen. From the automaton you read off shifts (transitions on terminals), GOTO entries (transitions on nonterminals) and, where an item is complete, the reductions. LR(0) and SLR(1) are the two simplest ways to choose when to reduce.

Prerequisites

You need the LR driver and the shape of the ACTION and GOTO tables (LR parsing) and FOLLOW sets (FIRST and FOLLOW).

Precise definitions

LR(0) item. A production with a dot somewhere in its right side: $A \to \alpha \cdot \beta$. The dot marks how much of the right side the parser has already seen on the stack. The production $A \to X_1 X_2 X_3$ gives four items: $A \to \cdot X_1 X_2 X_3$, $A \to X_1 \cdot X_2 X_3$, $A \to X_1 X_2 \cdot X_3$, $A \to X_1 X_2 X_3 \cdot$. The production $A \to \varepsilon$ has a single item, $A \to \cdot$. A production with $n$ symbols on the right gives $n + 1$ items.

Augmented grammar. Add a new start symbol $S'$ and the production $S' \to S$. When the parser is about to reduce by this production (item $S' \to S \cdot$ with the input at $) it accepts. The augmentation guarantees a single accepting point.

Closure. For a set of items $I$, $\text{closure}(I)$ is built by: put every item of $I$ in it; repeat: if $A \to \alpha \cdot B \beta$ is in the set and $B \to \gamma$ is a production, add $B \to \cdot \gamma$; until nothing is added. Meaning: if the parser expects to see a $B$ next, it might be at the start of any production of $B$.

Kernel and non-kernel items. The kernel of a state consists of its starting item $S' \to \cdot S$ (in state 0) and every item whose dot is not at the left end; the other items (dot at the left end) come from the closure.

Goto. $\text{goto}(I, X)$ is the closure of the set of all items $A \to \alpha X \cdot \beta$ such that $A \to \alpha \cdot X \beta$ is in $I$: move the dot over $X$ and close.

Canonical collection of LR(0) item sets. Start with $I_0 = \text{closure}(\{S' \to \cdot S\})$ and repeatedly add $\text{goto}(I, X)$ for every state $I$ and every symbol $X$ that follows a dot in $I$, until nothing new appears. The sets are the states; the gotos are the transitions. This is a DFA that recognises the viable prefixes. (State numbers depend on the order of construction; questions give or ask for the number of states, which does not.)

LR(0) parsing table. For each state $I_i$:

• if $A \to \alpha \cdot a \beta$ is in $I_i$ ($a$ a terminal) and $\text{goto}(I_i, a) = I_j$: ACTION[$i$, $a$] = shift $j$;
• if $A \to \alpha \cdot$ is in $I_i$ and $A \ne S'$: ACTION[$i$, $a$] = reduce $A \to \alpha$ for every terminal $a$ (and $);
• if $S' \to S \cdot$ is in $I_i$: ACTION[$i$, $] = accept;
• if $\text{goto}(I_i, A) = I_j$ for a nonterminal $A$: GOTO[$i$, $A$] = $j$.

If a cell receives two entries the grammar is not LR(0): a shift-reduce conflict (a state with a complete item and a shift item) or a reduce-reduce conflict (two complete items). A grammar is LR(0) if the construction has no conflict. A state that contains a complete item $A \to \alpha \cdot$ ($A \ne S'$) must contain no other complete item and no shift item, so LR(0) grammars are rare; $S \to a S b \mid a b$ is one.

SLR(1) table. The same item sets, but a complete item $A \to \alpha \cdot$ gives a reduce only for the terminals $a$ in $\text{FOLLOW}(A)$. Rows and shifts are as for LR(0). A grammar is SLR(1) if the resulting table has no conflict. Equivalently, for every state: for a complete item $A \to \alpha \cdot$ and any shift item $B \to \beta \cdot a \gamma$, $a \notin \text{FOLLOW}(A)$; and two complete items $A \to \alpha \cdot$, $B \to \beta \cdot$ have disjoint FOLLOW sets.

The weakness of SLR: FOLLOW($A$) takes the follow set of $A$ over the whole grammar, but in a particular state fewer tokens can really follow. The next page fixes this with lookaheads attached to items.

Counting. The number of LR(0) items of a grammar (augmented) is the sum over all productions of (length of the right side + 1). The number of states of the automaton is what is asked more often; it needs the construction.

How it works

The first animation builds the LR(0) collection for the expression grammar, one goto at a time. Each row is a state with its items (complete closure) and its outgoing transitions. Step through it: whenever a goto creates an existing set, no new state appears (for example state 4 on ( leads back to state 4).

Now the SLR(1) table for this grammar, filled state by state. In state 2 the items are $E \to T \cdot$ and $T \to T \cdot * F$: the shift on * and the reduce for $E \to T$ would collide in LR(0) (a reduce on every terminal), but in SLR(1) the reduce is only on FOLLOW($E$) = {+, ), $}, which does not contain *: no conflict.

The standard grammar that is not SLR(1): $S \to L = R \mid R$, $L \to * R \mid \text{id}$, $R \to L$ (assignments with dereference). State 2 contains $S \to L \cdot = R$ and $R \to L \cdot$. The shift on = conflicts with the reduction $R \to L$, because = is in FOLLOW($R$) (since $R$ can be followed by whatever follows $L$, and $L$ is followed by = in $S \to L = R$). In the real context, though, an $R$ at the start of a statement is followed only by $, so the reduction would never be right on =: the conflict is spurious, caused by the coarse FOLLOW set.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The driver is the one of LR parsing; the sets come from FIRST and FOLLOW. The weakness of SLR is repaired by the lookahead items of CLR(1) and LALR(1). All four methods are compared with LL(1) in the parser hierarchy. The viable-prefix automaton is a DFA in the sense of DFA, built here from items instead of from regular expressions.

PYQs

Consider the canonical LR(0) parsing of the
grammar below using terminals {a, b, c} and non-
terminals {A, B, C, S} with S as the start symbol.
                    S → ACB
                   A → aA | ε
                   C → cC | ε
                  B → bB | b

Which one of the following options gives the
number of shift-reduce conflicts that will occur in
the LR(0) ACTION table?

Consider the augmented grammar with { +, *, (, ), id
} as the set of terminals.
S' →S
S→S+ R|R
R→R*P|P
P→(S) |id

If
I0
is
the
set
of
two
LR(0)
items
{[S'→S.],[S→S.+R]} then goto(closure (I0 ),+)
contains exactly _____ items.

Consider the following statements.

S1: Every SLR(1) grammar is unambiguous but
there are certain unambiguous grammars that are
not SLR(1).

S2 : For any context-free grammar, there is a parser
that takes at most O(n3 ) time to parse a string of
length n.

Which one of the following options is correct?

Consider the augmented grammar given below:

    S' → S

    S → 〈L〉 | id

    L → L, S | S

Let I0 = CLOSURE ({[S' → ·S]}). The number of
items in the set GOTO (I0 , 〈 ) is: _____.

A canonical set of items is given below:

S → L.  > R

Q → R.

On input symbol < the set has:-

Consider the grammar
                  S → (S) | a

Let the number of states in SLR(1), LR(1) and
LALR(1) parsers for the grammar be n1, n2 and n3
respectively. The following relationship holds good

Self-check

Revision card

References