Self-checkedTier 1 10 min readcd.parser-comparison

Parser power hierarchy and conflicts

How LL(1), LR(0), SLR(1), LALR(1) and LR(1) compare: the containments between grammar classes, what each method needs from the grammar, table sizes, error detection, how conflicts arise and are resolved, and a procedure for deciding which class a grammar belongs to, with a computed table of eight grammars.

Why it exists

GATE asks the same few questions again and again: is this grammar LL(1), SLR(1), LALR(1) or LR(1)? Which is more powerful? How many states? Which conflict appears? The answers all come from one picture of how the classes sit inside each other and what each method looks at. This page is that picture, with a computed example for every region.

Prerequisites

CLR(1) and LALR(1)Top-down parsing and LL(1)

You need the top-down parser (LL(1)) and the bottom-up family (LR(0) and SLR, CLR(1) and LALR(1)).

Precise definitions

The containments (classes of grammars).

$\text{LR(0)} \subset \text{SLR(1)} \subset \text{LALR(1)} \subset \text{LR(1)}, \qquad \text{LL(1)} \subset \text{LR(1)}.$

Every inclusion is proper. LL(1) is not contained in SLR(1) or LR(0) (LL(1) grammars can fail SLR(1): example G6 below), and LR(0), SLR(1) are not contained in LL(1) (left recursion: $S \to S a \mid b$ is LR(0) but not LL(1)). In general, LL( $k$ ) $\subset$ LR( $k$ ): an LR parser sees the whole right side before deciding; an LL parser must decide after seeing only the first $k$ tokens of it.

Languages. The languages generated by LR(1) grammars are exactly the deterministic context-free languages (those recognised by a deterministic pushdown automaton); LR( $k$ ) for $k > 1$ gives no new languages. LL( $k$ ) languages are a proper subset of them: for example $\{a^n b^n\} \cup \{a^n c^n\}$ is deterministic but has no LL( $k$ ) grammar.

What each method needs from the grammar.

	LL(1)	LR(0)	SLR(1)	LALR(1)	LR(1)
direction and derivation	top-down, leftmost	bottom-up, rightmost reversed	same	same	same
lookahead used	1 token to choose a production	none	1 token, but FOLLOW	1 token, merged exact	1 token, exact
left recursion	not allowed	fine	fine	fine	fine
common prefixes	not allowed (left factor)	fine	fine	fine	fine
ambiguous grammars	never	never	never	never	never (without precedence rules)
table states	rows = nonterminals	LR(0) states	LR(0) states	LR(0) states	most
detects errors	at once	at once	after some reductions	after some reductions	at once
typical tools	recursive descent, ANTLR-like	teaching	teaching	Yacc, Bison	rare (large tables)

How conflicts arise (the four causes).

Ambiguity: always conflicts in every method (precedence declarations resolve them in practice).
LR(0): any state with a complete item and anything else; the method ignores the lookahead.
SLR(1): FOLLOW( $A$ ) is larger than what can follow in this state: a spurious shift-reduce or reduce-reduce conflict.
LALR(1): merging states with the same core unites lookaheads and may create a reduce-reduce conflict.

Resolving conflicts in a parser generator. Yacc and Bison prefer shift in a shift-reduce conflict (which attaches an else to the nearest if) and the earlier production in a reduce-reduce conflict. The author can give operator precedence and associativity (%left, %right, %nonassoc), which turns the conflicts of an ambiguous expression grammar into definite choices. Such a parser is correct only if the choices are what the language intends.

Deciding the class of a grammar (by hand). Check from the cheap test to the expensive: (1) ambiguous? then none. (2) LL(1)? needs FIRST and FOLLOW and no left recursion. (3) Build the LR(0) automaton: any state with a complete item and a second item (or two complete items) means not LR(0). (4) Compute FOLLOW and test the conflicting states: if each conflict disappears, SLR(1). (5) Otherwise compute the lookaheads in the conflicting states: if the exact lookaheads separate the actions after merging same-core states, LALR(1); (6) if only without merging, LR(1).

How it works

Eight grammars, classified by running every construction. Step through them; every "yes" or "no" is the verdict of the table built for that method, and the last two columns are the numbers of states of the LR(0) (= SLR(1) = LALR(1)) and of the canonical LR(1) automaton.

name	grammar
G1	$E \to E + T \mid T$ , $T \to T * F \mid F$ , $F \to ( E ) \mid \text{id}$
G2	the same language with the left recursion removed: $E \to T E'$ , $E' \to + T E' \mid \varepsilon$ , $T \to F T'$ , $T' \to * F T' \mid \varepsilon$ , $F \to ( E ) \mid \text{id}$
G3	$S \to C C$ , $C \to c C \mid d$
G4	$S \to L = R \mid R$ , $L \to * R \mid \text{id}$ , $R \to L$
G5	$S \to a A d \mid b B d \mid a B e \mid b A e$ , $A \to c$ , $B \to c$
G6	$S \to A a A b \mid B b B a$ , $A \to \varepsilon$ , $B \to \varepsilon$
G7	$E \to E + E \mid E * E \mid ( E ) \mid \text{id}$
G8	$S \to i S \mid i S e S \mid a$

Which parsing methods accept which grammars: start

Computed by a script, not typed

grammar	LL(1)	LR(0)	SLR(1)	LALR(1)	LR(1)	states LR(0)	states LR(1)
G1
G2
G3
G4
G5
G6
G7
G8

Step 0

Eight grammars are classified by running every construction. 'yes' means the parsing table of that method has no conflict for the grammar. Read each row from left to right: the classes grow (an LR(0) grammar is SLR(1), an SLR(1) grammar is LALR(1), an LALR(1) grammar is LR(1)).

0 / 8

computed by script: the algorithm is executed, one move per step. python3 scripts/gen-cd-traces.py

Reading the table. G1 is the usual expression grammar: not LL(1) (left recursive) but SLR(1) and everything above. G2 is LL(1) and also SLR(1): removing left recursion makes it LL(1) at the price of more states. G3 is LL(1) and LR(0). G4 is not SLR(1) but LALR(1). G5 is LR(1) but not LALR(1). G6 is LL(1) but not SLR(1) (and not LR(0)), though it is LALR(1): the example that LL(1) is not contained in SLR(1). G7 and G8 are ambiguous: no method works without precedence rules or a conflict resolution.

Worked examples

EX 1Place a grammar in the hierarchy

Easy

$S \to S a \mid b$ . Left recursive, so not LL(1). The LR(0) automaton: after b a complete item alone (reduce), after S the items $S' \to S \cdot$ and $S \to S \cdot a$ (accept on $, shift on a), after S a a complete item alone. No conflict even without lookahead: LR(0), and therefore SLR(1), LALR(1), LR(1). The same language has the LL(1) grammar $S \to b S'$ , $S' \to a S' \mid \varepsilon$ . This example shows that LR(0) is not contained in LL(1) and that LR parsers are happy with left recursion.

EX 2Grammar classes are about grammars, not languages

Easy

The language of G1 and of G2 is the same. G1 is not LL(1) while G2 is: LL(1) is a property of the grammar, and a left-recursive grammar can usually be rewritten. Both are SLR(1). Questions such as "the language $\{a^n b^n\}$ is LL(1)" mean "has an LL(1) grammar": $S \to a S b \mid \varepsilon$ is one (checked on the LL(1) page).

EX 3Which method first fails?

Medium

For G4 ( $S \to L = R \mid R$ , $L \to * R \mid \text{id}$ , $R \to L$ ): LR(0) fails (state with $S \to L \cdot = R$ and $R \to L \cdot$ ). SLR(1) fails: = is in FOLLOW( $R$ ). LALR(1) succeeds: the lookahead of $R \to L \cdot$ in that state is only $. For G5 the first method that succeeds is LR(1). For G7 none succeeds (ambiguity); with %left '+' and %left '*' (the latter listed later, so higher precedence) Yacc resolves every conflict and parses $\text{id} + \text{id} * \text{id}$ with the product first.

EX 4LL(1) but not SLR(1)

Medium

G6: $S \to A a A b \mid B b B a$ , $A \to \varepsilon$ , $B \to \varepsilon$ . LL(1): FIRST( $A a A b$ ) = {a} and FIRST( $B b B a$ ) = {b}, disjoint; $A$ and $B$ have a single production each. LR: the initial state contains $A \to \cdot$ and $B \to \cdot$ (both complete items), a reduce-reduce situation; SLR(1) reduces on FOLLOW( $A$ ) = FOLLOW( $B$ ) = {a, b} for both: conflict. The lookahead of the true context is a for $A \to \varepsilon$ here and b for $B \to \varepsilon$ , so LALR(1) and LR(1) have no conflict. The number of states is 10 for LR(0) and for LR(1).

EX 5True or false

GATE level

(a) "Every LL(1) grammar is LR(1)": true. (b) "Every LL(1) grammar is SLR(1)": false (G6). (c) "An SLR(1) grammar is LALR(1)": true. (d) "LALR(1) parsers have fewer states than canonical LR(1) parsers": true or equal; "fewer" is correct for most real grammars, but never more. (e) "An ambiguous grammar can be LR(1)": false. (f) "The language of a deterministic pushdown automaton has an LR(1) grammar": true. (g) "Every context-free language has an LR(1) grammar": false (inherently non-deterministic languages such as palindromes $w w^R$ have none). (h) "A grammar with left recursion cannot be parsed bottom-up": false; it is the top-down parsers that cannot handle it.

Cheat box

Grammar classes: LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1), and LL(1) ⊂ LR(1). LL(1) and SLR/LR(0) are not comparable.
LR(1) languages = deterministic CFLs. LL(k) languages are a proper subset.
LL(1): no left recursion, no common prefix. LR: no such restriction.
States: LR(0) = SLR = LALR; canonical LR(1) at least as many.
Conflicts: LR(0) ignores lookahead; SLR uses FOLLOW (coarse); LALR merging can add reduce-reduce only; ambiguity gives conflicts everywhere.
Yacc: shift on shift-reduce, earlier production on reduce-reduce, precedence declarations override.
Detection of errors: LL(1) and canonical LR(1) at the first bad token without extra moves.

Traps and GATE patterns

Connections

Builds on

CLR(1) and LALR(1)Top-down parsing and LL(1)

Unlocks

Top-down parsing and LL(1)uses Bottom-up parsing and LRuses LR(0) and SLR(1) constructionuses CLR(1) and LALR(1)uses Operator precedence parsinganalogous to

Across subjects

No cross-subject links yet.

Within this subject

Top-down parsing and LL(1)contrasts-with LR(0) and SLR(1) constructioncontrasts-with CLR(1) and LALR(1)contrasts-with Shift-reduce parsing and handlesuses Ambiguity, left recursion and left factoringuses

The top-down side is LL(1) parsing, the bottom-up side is shift-reduce parsing, LR parsing, LR(0) and SLR(1) and CLR(1) and LALR(1). Making a grammar suitable (removing ambiguity and left recursion) is in grammar transformations. The language classes are those of the Chomsky hierarchy (deterministic context-free languages sit inside the context-free languages).

PYQs

6 previous year questions from your book. I re-solved each one myself (2 by running or simulating, 4 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2022 · MCQ · 1 markQ10 · page 257 of the book

Which one of the following statements is TRUE?

(a)The LALR(1) parser for a grammar G cannot have reduce – reduce conflict if the LR(1) parser for G does not have reduce – reduce conflict.
(b)Symbol table is accessed only during the lexical analysis phase.
(c)Data flow analysis is necessary for run-time memory management.
(d)LR(1) parsing is sufficient for deterministic context – free languages

GATE 2021 · MCQQ12 · page 258 of the book

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?

(a)S1 is true and S2 is false
(b)S1 is false and S2 is false
(c)S1 is false and S2 is true
(d)S1 is true and S2 is true

GATE 2017 · MCQQ18 · page 259 of the book

Which of the following statements about parser
is/are CORRECT?
        I. Canonical LR is more powerful than SLR.

II. SLR is more powerful than LALR.

III. SLR is more powerful than Canonical LR.

(a)I only
(b)II only
(c)III only
(d)II and III only

GATE 2015 · MCQQ24 · page 260 of the book

Among simple LR (SLR), canonical LR, and look-
ahead LR (LALR), which of the following pairs
identify the method that is very easy to implement
and the method that is the most powerful, in that
order?

(a)SLR, LALR
(b)Conical LR, LALR
(c)SLR, conical LR
(d)LALR, conical LR

GATE 2010 · MCQ · 2 marksQ34 · page 263 of the book

The grammar : S → aSa|bS|c is:-

(a)LL(1) but not LR(1)
(b)LR(1) but not LL(1)
(c)Both LL(1) and LR(1)
(d)Neither LL(1) nor LR(1)

GATE 2005 · MCQQ39 · page 263 of the book

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

(a)n1 < n2 < n3
(b)n1 = n3 < n2
(c)n1 = n2 = n3
(d)n1 ≥ n3 ≥ n2

Self-check

Question 1

Give a grammar that is LR(0) but not LL(1).

Show answer

$S \to S a \mid b$ (left recursive), or $S \to a S b \mid a b$ (common prefix).

Question 2

Which is the largest class of deterministic bottom-up grammars, and which languages does it generate?

Show answer

LR(1) grammars; they generate exactly the deterministic context-free languages.

Question 3

Is every SLR(1) grammar LALR(1)? Every LALR(1) grammar SLR(1)?

Show answer

Yes to the first, no to the second ( $S \to L = R \mid R$ , $L \to * R \mid \text{id}$ , $R \to L$ is LALR(1) but not SLR(1)).

Question 4

In Yacc a shift-reduce conflict arises and no precedence is declared. What happens?

Show answer

The parser shifts (this is why the dangling else attaches to the nearest if), and Yacc reports the conflict.

Revision card

One-screen revision

LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1); LL(1) ⊂ LR(1) only. LR(1) = deterministic CFLs.
LL needs no left recursion and left factoring; LR needs neither.
States: LR(0) = SLR = LALR ≤ CLR. SLR conflicts from FOLLOW; LALR only adds reduce-reduce.
Ambiguity conflicts in all; Yacc: shift, then earlier production, or precedence.
Examples: $S \to S a \mid b$ LR(0) not LL(1); $L = R$ grammar LALR not SLR; G6 LL(1) not SLR.

References

·Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools (2nd edition), Chapter 4 Syntax Analysis (4.8 using ambiguous grammars; 4.9 parser generators; relations between LL and LR classes)
·Cooper and Torczon, Engineering a Compiler, Chapter 3 Parsers (the relationships between grammar classes)

Verification

The comparison table of eight grammars is computed: for each grammar the LL(1) test and the LR(0), SLR(1), LALR(1) and LR(1) tables are built by script and the verdicts and state counts are read from them (scripts/gen-cd-traces.py); tests/cd-traces.test.ts checks that no row violates the containments. The containments LR(0), SLR(1), LALR(1), LR(1) and LL(1) in LR(1) were also checked on 1245 random reduced grammars with no violation (scripts/enum-checks/cd_lr.py). Statements about language classes (LR(1) languages are the deterministic context-free languages, the existence of non-LL(k) deterministic languages) are standard theorems quoted from textbooks and were not machine-checked. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand or by a small script (token counts, FIRST and FOLLOW sets, LL(1) tables and moves, LR item sets, state counts and parses, operator-precedence values, attribute evaluation and printing schemes, activation-record counts and access links, parameter-passing results, three-address code, jumping and backpatched code, leaders and blocks, value numbering and DAGs, gen/kill and data flow sets, Sethi-Ullman labels and live ranges); long C programs were not re-read line by line (they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose); tables and animations are machine output and were read, not re-run; No other defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Operator precedence parsing

Syntax-directed definitions: synthesized and inherited attributes