Which of the following are true of the LR family? (More than one may be correct.)

LALR(1) and SLR(1) parsers have the same number of states

Canonical LR(1) can need more states than LALR(1)

LALR(1) and SLR(1) parsers have the same number of states

An ambiguous grammar can be LALR(1)

Canonical LR(1) can need more states than LALR(1)

A lexical analyser cannot be used to check that brackets in a program are balanced, because:

Balanced brackets are not a regular language

It runs too early in the compiler

Balanced brackets are not a regular language

In filling an LL(1) parsing table, the FOLLOW set of a non-terminal A is consulted:

Only for productions of A whose right side can derive ε

Only when A is the start symbol

Lexical Analysis and Parsing

Section 7 of the Computer Science paper. A compiler's front end has a clean division of labour that the questions follow exactly. Lexical analysis turns characters into tokens and is a regular problem — which is why lexers are built from finite automata and why the classic exam point is that a lexer cannot match nested brackets, since that is not a regular language. Parsing turns tokens into a tree and is a context-free problem, which is where the marks are. Two things account for nearly all of them. The first is mechanical: compute FIRST and FOLLOW, fill the LL(1) table, and a repeated cell is a conflict. Those two set computations are fixpoint algorithms you can run without understanding anything about the language, and running them carefully is worth more than any insight. The second is the LR hierarchy, and the honest summary is a chain of strict inclusions: LL(1) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1), with every one of those containments strict. So a grammar can be LALR(1) and not SLR(1), and asking "is this grammar LR?" is incomplete until it says which LR. Two structural facts settle a great many questions before any table is built. A left-recursive grammar is never LL(1) — a top-down parser would recurse forever without consuming input — so the first thing to look for in an LL question is left recursion. And an ambiguous grammar is never LR of any flavour, because two parse trees for one string mean the parser cannot choose; the dangling-else grammar is the standard witness, and its LL(1) table has exactly one conflicted cell.

What a Lexer Can and Cannot Do

Lexical analysis turns a stream of characters into a stream of tokens. Three words are worth keeping apart because questions use them precisely: a pattern is the rule (a regular expression), a lexeme is the actual run of characters matched in the source, and a token is what the lexer hands the parser — the pattern’s name plus, usually, an attribute. In count = 10, the lexemes are count, = and 10, and the tokens are identifier, assign and number, with the identifier carrying a symbol-table entry and the number its value. The whole phase is built from a finite automaton, which fixes what it can recognise: exactly the regular languages, and nothing more.

🧠 Longest match first, rule order only to break a tie

When two patterns both match at the current position, a lexer applies two rules in this order: take the longest match, and only if two matches are the same length take the pattern listed first. Both halves are examinable and the first is the one that catches people. x<=y is three tokens, not four, because <= beats <. And int x = a+++b; is eight tokens — int, x, =, a, ++, +, b, ; — because at the first + the longest match is ++, leaving a single + behind; the parser then has no choice but to read it as (a++) + b. The tie-break matters for keywords: if matches both the keyword pattern and the identifier pattern at the same length, so the keyword rule is listed first, which is the entire reason a keyword is not an identifier.

⚠️ The lexer is not being lazy about brackets — it cannot count

A lexer will happily report ( and ) as tokens and cannot tell you whether they balance, and the reason is a hard boundary rather than a design choice. Balanced brackets need unbounded counting, so the language of balanced strings is not regular, and a finite automaton has a fixed number of states with nowhere to keep the count. That is the same boundary Section 6 draws, arriving here as an engineering fact: matching brackets is a context-free problem, it belongs to the parser, and it is precisely why a parser is given a stack where the lexer is not. Read the division of labour off the language classes and this phase stops being a list of conventions.

FIRST and FOLLOW, Computed Rather Than Guessed

Take the standard expression grammar with left recursion removed: E → T X, X → + T X | ε, T → F Y, Y → * F Y | ε, F → ( E ) | id. The two sets below were produced by running the fixpoint algorithms, and this grammar turns out to have no LL(1) conflicts at all — it is LL(1), which is the whole reason the left recursion was removed.

FIRST and FOLLOW for that grammar
Non-terminal	FIRST	FOLLOW
E	{ (, id }	{ $, ) }
X	{ +, ε }	{ $, ) }
T	{ (, id }	{ $, ), + }
Y	{ *, ε }	{ $, ), + }
F	{ (, id }	{ $, ), *, + }

🧠 FOLLOW only matters where FIRST contains ε

The LL(1) table is filled from FIRST, and FOLLOW enters in exactly one situation: a production whose right-hand side can derive ε is entered under every terminal in the FOLLOW of its left-hand side, because that is when the parser must decide to produce nothing and move on. So for a grammar with no ε-productions, FOLLOW never touches the table and computing it is wasted effort. Notice which sets above contain ε — only X and Y — and those are exactly the two non-terminals whose FOLLOW sets do any work. Checking for ε-productions first tells you how much of the computation you actually need, and on a timed paper that is the difference between finishing the question and running out of it.

Where Grammars Fail, and Which Failure It Is

Three disqualifications, each checkable before building a table
Property of the grammar	What it rules out	Why
Left recursion, A → A α	Never LL(1)	Top-down would recurse without consuming input
Common prefix, A → α β \| α γ	Not LL(1) until left-factored	One lookahead token cannot separate the two
Ambiguity	Never LR of any kind	Two trees for one string — nothing to choose on

🎯 The dangling-else grammar, and its single conflicted cell

Take S → if S else S | if S | a. FIRST(S) = { if, a } and FOLLOW(S) = { $, else }. Filling the LL(1) table puts both if-productions into the cell (S, if), because both begin with the same token — one conflicted cell, and the grammar is not LL(1). The deeper problem is that it is ambiguous: if a else a has two parse trees, and no amount of lookahead fixes an ambiguity, so the grammar is not LR(1) either. Real compilers do not fix the grammar; they add a rule outside it — an else binds to the nearest unmatched if — which is a disambiguation policy rather than a grammatical repair. That distinction is worth having: a question asking how a parser generator handles dangling else is asking about the policy, and one asking whether the grammar is LL(1) is asking about the table.

The LR hierarchy, every containment strict
Class	What it uses	Table size
LR(0)	No lookahead	Smallest
SLR(1)	LR(0) states + FOLLOW sets	Same states as LR(0)
LALR(1)	LR(1) states merged by core	Same states as LR(0) — what yacc builds
LR(1)	Full lookahead per item	Largest — often impractical

Counting LR(0) Item Sets

For the grammar S′ → S, S → C C, C → c C | d, building the canonical collection — closure, then goto on every symbol until nothing new appears — gives 7 item sets, and that count was produced by running the construction rather than drawing it. It is also the number of states in the SLR(1) and LALR(1) tables for this grammar, since both use the LR(0) state set unchanged and differ only in how they fill the action entries.

⚠️ SLR, LALR and LR(0) have the same number of states — that is the point

A question asking for "the number of states in the SLR parser" is asking for the number of LR(0) item sets, because SLR does not change the automaton at all — it only consults FOLLOW when deciding whether to reduce. LALR(1) also keeps that state count, by merging LR(1) states that share a core. Only canonical LR(1) has more states, sometimes many more, which is exactly why it is rarely built and why yacc and its descendants generate LALR(1). So the three classes differ in power, not in size, and a candidate who computes an LR(1) state count when asked for SLR has done far more work and got the wrong answer.

Key takeaways

Lexing is a regular problem and parsing a context-free one — a lexer cannot match nested brackets.
FOLLOW only enters the LL(1) table for productions that can derive ε — check for those first.
A left-recursive grammar is never LL(1); a common prefix needs left-factoring first.
An ambiguous grammar is never LR of any kind — no lookahead repairs an ambiguity.
The dangling-else grammar has exactly one conflicted LL(1) cell, at (S, if).
Real compilers disambiguate dangling else by a rule outside the grammar, not by fixing it.
LL(1) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1), and every containment is strict.
LR(0), SLR and LALR share one state count; only canonical LR(1) has more. yacc builds LALR(1).

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

For the grammar E → T X, X → + T X | ε, T → F Y, Y → * F Y | ε, F → ( E ) | id, the set FOLLOW(T) is:
1. { $, ) }
2. { $, ), + }
3. { $, ), *, + }
4. { +, * }
Show answer
Answer: B — { $, ), + }
{ $, ), + }. T is followed by X in E → T X, so FIRST(X) − {ε} = { + } goes in; and since X can derive ε, everything in FOLLOW(E) = { $, ) } follows T as well. Option A is FOLLOW(E) and FOLLOW(X), which is a genuinely different set — noticing that E and X share a FOLLOW while T and Y share a larger one is a good check on the whole computation. Option C is FOLLOW(F), which additionally picks up * because F is followed by Y. The mechanical rule doing the work here is that when a trailing non-terminal can vanish, the FOLLOW of the left-hand side flows through.
A grammar contains the production A → A α. It follows that the grammar:
1. Is not LL(1)
2. Is not LR(1)
3. Is ambiguous
4. Has no FOLLOW sets
Show answer
Answer: A — Is not LL(1)
Not LL(1). A top-down parser seeing A on the stack and choosing A → A α would push A again without consuming any input, and could do so forever — so left recursion is an absolute bar to LL(k) for any k. But it is no obstacle at all to LR, which is bottom-up and handles left recursion naturally, indeed prefers it because it keeps the stack shallow. Option C is the error worth naming: left recursion and ambiguity are unrelated, and the standard left-recursive expression grammar is perfectly unambiguous. The practical consequence is that removing left recursion is a step you take for a top-down parser only, and it is what turns the expression grammar into the LL(1) form used above.
For the grammar S′ → S, S → C C, C → c C | d, how many item sets are there in the canonical LR(0) collection?
Numerical answer — type the value.
Show answer
Answer: 7
Seven. Take the closure of S′ → · S, then repeatedly apply goto on S, C, c and d until no new set appears; the construction terminates with seven item sets. The figure matters twice over, because it is also the number of states in the SLR(1) and LALR(1) tables for this grammar — neither of those changes the automaton, they only change how the reduce entries are filled. Only canonical LR(1) would have more. So a question asking for "the number of states in the SLR parser" wants this same 7, and computing an LR(1) collection instead is more work for a wrong answer.
The grammar S → if S else S | if S | a is not LL(1). How many cells of its LL(1) table have a conflict?
1. One
2. Two
3. Three
4. None — it is LL(1)
Show answer
Answer: A — One
One. FIRST(S) = { if, a }, and both if-productions begin with if, so both land in the single cell (S, if). The third production, S → a, goes alone into (S, a). One conflicted cell, and it is enough to disqualify the grammar. Worth separating from that count is the deeper fault: the grammar is ambiguous — if a else a has two parse trees — and ambiguity rules out LR(1) as well, so no amount of lookahead helps. Compilers therefore resolve it with a rule outside the grammar, binding each else to the nearest unmatched if.
Which of the following are true of the LR family? (More than one may be correct.)
1. LALR(1) and SLR(1) parsers have the same number of states
2. Every LL(1) grammar is LR(1)
3. An ambiguous grammar can be LALR(1)
4. Canonical LR(1) can need more states than LALR(1)
Show answer
Answer: A — LALR(1) and SLR(1) parsers have the same number of states; B — Every LL(1) grammar is LR(1); D — Canonical LR(1) can need more states than LALR(1)
A, B and D. Both SLR(1) and LALR(1) are built on the LR(0) state set and differ only in how reduce entries are computed, so their state counts agree (A) — and canonical LR(1), which keeps lookaheads separate instead of merging cores, can have many more (D). B is the containment LL(1) ⊂ LR(1), and it is strict, so the converse fails. C is false: ambiguity means two parse trees for one string, and a deterministic parser has nothing to choose on, so no ambiguous grammar is LR of any flavour. That is why an ambiguous grammar is disqualified before any table is built, and why dangling else is handled by a policy rather than by a stronger parser.
A lexical analyser cannot be used to check that brackets in a program are balanced, because:
1. It runs too early in the compiler
2. Balanced brackets are not a regular language
3. It has no symbol table
4. Brackets are not tokens
Show answer
Answer: B — Balanced brackets are not a regular language
A lexer is a finite automaton, so it recognises exactly the regular languages — and balanced brackets is the standard non-regular language, needing unbounded counting that no fixed number of states can supply. That is a statement about the class of problem, not about the lexer's position in the pipeline (option A) or its data structures (option C). Brackets certainly are tokens (option D); the lexer happily reports each one and simply cannot say whether they pair up. Matching them is the parser's job, and that it is a context-free problem is precisely why parsers use a stack.
In filling an LL(1) parsing table, the FOLLOW set of a non-terminal A is consulted:
1. For every production of A
2. Only for productions of A whose right side can derive ε
3. Never
4. Only when A is the start symbol
Show answer
Answer: B — Only for productions of A whose right side can derive ε
Each production A → α is entered under every terminal of FIRST(α); FOLLOW(A) is used only when α can derive ε, because that is the one situation where the parser must decide to expand A into nothing and let whatever comes next be handled by A's caller. The practical payoff is real: in a grammar with no ε-productions, FOLLOW never touches the table, so computing it is wasted work — and in the expression grammar above only X and Y have ε in their FIRST sets, which is exactly where their FOLLOW sets earn their keep. Checking for ε-productions before starting tells you how much of the computation you need.
Which parser does a tool such as yacc or bison generate?
1. LL(1)
2. SLR(1)
3. LALR(1)
4. Canonical LR(1)
Show answer
Answer: C — LALR(1)
LALR(1), and the reason is the trade it strikes: it is strictly more powerful than SLR(1) while keeping the same number of states as LR(0), because it merges LR(1) states that share a core. Canonical LR(1) is more powerful still but can need far more states, which made it impractical when these tools were written and is still usually not worth the table size. The one cost of the merge is worth knowing: merging cores can introduce reduce–reduce conflicts that canonical LR(1) would not have, so a grammar can be LR(1) and not LALR(1) — which is precisely why the hierarchy is a chain of strict inclusions rather than a set of equivalent labels.