Parsing Questions in GATE CSE: LL(1), SLR, LALR and CLR

Parsing questions in GATE CSE are mechanical. You are handed three to six productions and asked for a set, a count, or a class name. Marks are lost on bookkeeping: an epsilon that should not be in a FOLLOW set, a goto that should have pointed back at an existing state, the accept item counted as a reduce. This guide works the full procedure on one tiny grammar.

Key takeaways

• FIRST is read left to right and stops at the first symbol that is not nullable. FOLLOW never contains epsilon.
• The LL(1) test is a condition on each pair of productions of the same non-terminal, not on the grammar as a whole.
• Left recursion and a common prefix both break LL(1). Left factoring removes the prefix; it does not remove ambiguity.
• Total LR(0) items $= \sum \big(\lvert \text{RHS} \rvert + 1\big)$ over all productions, plus 2 for the augmented production. An epsilon production contributes 1.
• LALR(1) has exactly as many states as SLR(1), never fewer. CLR(1) has at least as many.
• Merging states in LALR can create a reduce-reduce conflict and can never create a shift-reduce one.
• An ambiguous grammar is not LR($k$) for any $k$, so spotting two parse trees settles the whole question.

Where parsing sits in the paper

On the third-party analyst compilation this guide uses, Compiler Design marks per paper from 2009 to 2026 run 2, 4, 3, 4, 3, 6, 4, 5, 3, 4, 6, 4, 8, 4, 5, 8, 5, 5. That is an average of about 4.6 marks, a minimum of 2 and a maximum of 8. Split the record in half and the 2009-2017 average is about 3.8 against about 5.4 for 2018-2026, so the subject has roughly doubled from its 2009-2013 level of 2 to 4 marks. These figures are unofficial and approximate: analysts disagree by two or three marks because borderline questions get filed under Theory of Computation instead.

Inside that budget, parsing is the largest block. LR and LL parsing, FIRST and FOLLOW, and syntax-directed translation are the recurring items, and data-flow analysis has joined them since 2021. Compiler Design and Digital Logic are the most formula-stable subjects in the paper, which is why they return the best marks per hour. The rest of the subject map is in Compiler Design important topics, and classification questions overlap with Theory of Computation important topics. The Section 7 syllabus wording is unchanged for 2027, but check the current notification rather than any copied syllabus.

One grammar to work on

Everything below uses this grammar, with $S$ as the start symbol.

It is nullable in two places on purpose, because the nullable case is where the errors live.

FIRST and FOLLOW, mechanically

FIRST of a string is what can start it. For $A \to X_1 X_2 \dots X_n$, add $\text{FIRST}(X_1) \setminus \{\varepsilon\}$; move to $X_2$ only if $X_1$ is nullable; if every $X_i$ is nullable, add $\varepsilon$. FOLLOW of a non-terminal is what can stand immediately after it. Seed FOLLOW of the start symbol with the end marker $. For every occurrence $A \to \alpha B \beta$, add $\text{FIRST}(\beta) \setminus \{\varepsilon\}$ to $\text{FOLLOW}(B)$, and add $\text{FOLLOW}(A)$ to $\text{FOLLOW}(B)$ when $\beta$ is empty or nullable. Repeat until no set grows.

Two rules cover almost every mistake made here. Epsilon belongs in FIRST sets and never in a FOLLOW set, because FOLLOW holds terminals that actually appear to the right, and epsilon is the absence of a terminal rather than one. And $ belongs in FOLLOW of every non-terminal that can end a sentence, not only the start symbol.

The LL(1) test in one line

A grammar is LL(1) when, for every non-terminal $A$ and every pair of distinct productions $A \to \alpha$ and $A \to \beta$:

• $\text{FIRST}(\alpha) \cap \text{FIRST}(\beta) = \emptyset$, and
• if $\beta \Rightarrow^* \varepsilon$, then $\text{FIRST}(\alpha) \cap \text{FOLLOW}(A) = \emptyset$.

It is a pairwise test, so a non-terminal with four alternatives needs $\binom{4}{2} = 6$ checks, and the grammar fails the moment one pair fails.

Filling the table is the same test written out. Production $A \to \alpha$ goes into cell $M[A, t]$ for every terminal $t \in \text{FIRST}(\alpha)$, and also into $M[A, t]$ for every $t \in \text{FOLLOW}(A)$ when $\alpha \Rightarrow^* \varepsilon$. Any cell holding two productions is a conflict.

For the grammar above: $S \to ABc$ goes under $a$, $b$ and $c$; $A \to a$ under $a$; $A \to \varepsilon$ under $b$ and $c$; $B \to b$ under $b$; $B \to \varepsilon$ under $c$. Eight filled cells, none with two entries, so the grammar is LL(1). The FIRST sets of $A \to a$ and $A \to \varepsilon$ being different was not enough on its own. What decided it was that $a \notin \text{FOLLOW}(A)$.

Left recursion, common prefixes and left factoring

A predictive parser picks a production from one lookahead token and then commits. Two grammar shapes make that impossible.

Left recursion. With $E \to E + T \mid T$, $\text{FIRST}(E + T)$ contains everything in $\text{FIRST}(E)$, so the alternatives can never be distinguished. Immediate left recursion is removed by rewriting $A \to A\alpha \mid \beta$ as $A \to \beta A'$ and $A' \to \alpha A' \mid \varepsilon$. Indirect left recursion, where $A$ derives $B$ which derives $A$, needs the same trick after substituting in a fixed non-terminal order.

Common prefix. With $S \to aSb \mid ab$, seeing $a$ tells you nothing about which alternative to take. Left factoring pulls the prefix out: $S \to aX$ with $X \to Sb \mid b$.

One warning appears as an option almost every year: these two transformations change the grammar, not the language, and neither removes ambiguity. An ambiguous grammar stays outside every LL and LR class.

LR(0) items and how to count them

An item is a production with a dot somewhere in the right side. A production with $k$ symbols on the right gives $k + 1$ items; an epsilon production gives exactly one item, $A \to \cdot$; the augmented production $S' \to S$ gives two.

For our grammar: 4 items from $S \to ABc$, 2 from $A \to a$, 1 from $A \to \varepsilon$, 2 from $B \to b$, 1 from $B \to \varepsilon$, plus 2 for the augmented production:

Twelve items in all.

Building the canonical collection is closure and goto, repeated. Closure adds $B \to \cdot\gamma$ for every non-terminal $B$ sitting just after a dot. Goto on $X$ shifts the dot past $X$ in every item that has $X$ after the dot, then closes the result. The commonest counting error is creating a fresh state for a goto that lands on a set you already have, so check each new set against the existing ones before numbering it.

Our grammar gives seven states. The start state closes to four items, one of which is the reduce item $A \to \cdot$, while the same state also shifts on $a$. In LR(0) terms that is a shift-reduce conflict, so the grammar is not LR(0).

Shift-reduce, reduce-reduce, and what each parser buys

A shift-reduce conflict is a state that holds a complete item $A \to \alpha\cdot$ and also an item with a terminal after the dot: the parser can reduce or read one more token. A reduce-reduce conflict is a state holding two complete items: the parser knows it must reduce but not by which production. Lookahead is what separates them.

The containment stated in exam options is $\text{LL}(1) \subseteq \text{SLR}(1) \subseteq \text{LALR}(1) \subseteq \text{CLR}(1)$, with $\text{LR}(0) \subseteq \text{SLR}(1)$ as well. Return to our grammar and SLR settles it: the reduce $A \to \varepsilon$ is allowed only on $\text{FOLLOW}(A) = \{b, c\}$, the competing shift is on $a$, and the sets are disjoint. The same holds for $B$. So the grammar is SLR(1) but not LR(0), which is exactly the shape of the standard classification question.

Now the LALR fact tested as a true-or-false option again and again. Merging two CLR states with the same core leaves the shift actions untouched, because identical cores have identical symbols after the dots; only the reduce lookahead sets are unioned. So merging can turn two reduces that were separated by disjoint lookaheads into one state with overlapping ones, creating a reduce-reduce conflict, and it can never create a shift-reduce conflict. Two consequences follow: LALR never has fewer states than SLR, and a grammar can be CLR(1) without being LALR(1).

The dangling-else grammar

$S \to iSeS \mid iS \mid a$, with $i$ for if and $e$ for else, is the standard ambiguous example and is worth knowing cold. Top-down, the two alternatives share the prefix $iS$; after left factoring you get $S \to iSX \mid a$ with $X \to eS \mid \varepsilon$, and the cell $M[X, e]$ now holds both productions, because $e \in \text{FIRST}(eS)$ and also $e \in \text{FOLLOW}(X)$. Bottom-up, the same ambiguity is a shift-reduce conflict on $e$, resolved by shifting, which attaches each else to the nearest unmatched if. The grammar itself stays ambiguous and stays outside every LR class.

Answering "which of these is LL(1) or SLR(1)" fast

Run the cheap tests before the expensive ones.

1. Is the grammar ambiguous? If yes, it is neither LL(1) nor LR($k$) for any $k$, and you are done.
2. Is there left recursion or a common prefix? Either one rules out LL(1) without computing a single set.
3. Only then compute FIRST and FOLLOW, and only for the non-terminals the options mention.
4. For LR classification, augment, build the collection, and stop at the first state holding a complete item alongside anything else. Check it against FOLLOW before declaring a conflict.
5. If the ask is a count, recount the accept item $S' \to S\cdot$ and the epsilon items deliberately. That is where the errors cluster.

The recurring slips, including those from other subjects, are collected in common mistakes that cost marks, and the item-count and state-count formulas sit in the GATE CSE formula sheet.

Budgeting time on exam day

These questions reward practice rather than thought, which is what you want under a clock. A FIRST or FOLLOW question should take under a minute once the sets are in a column. An LL(1) table question takes about two minutes. A canonical collection for a four-production grammar takes two to three minutes if you draw the states in a fixed layout every time you practise, and much longer if you improvise the layout each attempt.

So drill the layout, not only the theory. Take five small grammars, build the full collection for each on paper, and time yourself. Redo the same five a week later. The Compiler Design chapter of the GATE CSE 2027 book carries a worked bank of such grammars with the canonical collections drawn out state by state and the conflicts marked, which is the part that is hard to get from prose.