GATE CS

Parsing

Top-down and bottom-up parsers

Parsing turns a stream of tokens into a parse tree by following a context-free grammar, either top-down (LL, building a leftmost derivation) or bottom-up (LR, building a rightmost derivation in reverse). For GATE you must be able to compute FIRST and FOLLOW sets, build LL(1) tables and LR(0), SLR(1), LR(1) and LALR(1) item sets and tables, spot conflicts, place a grammar in the class hierarchy, and count the moves a parser makes on a string.

13 previous-year questions · 12 solved · 5 practice questions

Grammars, derivations and ambiguity

A context-free grammar has terminals, nonterminals, a start symbol and productions of the form $A \to α$ . Convention: the start symbol is the left side of the first production unless stated, $ε$ is the empty string, $ is the end-of-input marker, FIRST and FOLLOW sets are sets of terminals (FIRST may also contain $ε$ ), and an LR item writes the dot as $\cdot$ .

A leftmost derivation always expands the leftmost nonterminal; a rightmost derivation always expands the rightmost one. A top-down parser traces a leftmost derivation. A bottom-up parser traces a rightmost derivation in reverse. A parse tree does not record the order of expansion, so one parse tree corresponds to exactly one leftmost and exactly one rightmost derivation.

A grammar is ambiguous if some string has two different parse trees (equivalently, two leftmost derivations, or two rightmost derivations). An ambiguous grammar is never LL(k) and never LR(k) for any k; put the other way, every LL(k) and every LR(k) grammar is unambiguous. The converse fails: $S \to a S a ∣ b S b ∣ a ∣ b$ is unambiguous but is not LR(k) for any k, because its language (odd-length palindromes) is not deterministic. Ambiguity is a property of the grammar, not the language: some ambiguous grammars have an equivalent unambiguous grammar, and some languages are inherently ambiguous.

Dangling else. In $S \to if E then S ∣ if E then S else S ∣ other$ , the string if E then if E then other else other has two parse trees, one attaching else to the inner if and one to the outer. The usual rule attaches else to the nearest unmatched then. In an LR parser this is a shift-reduce conflict on else, resolved in favour of shift. For top-down parsing the grammar is first left-factored to $S \to if E then S S^{'} ∣ other$ , $S^{'} \to else S ∣ ε$ ; since else is in FOLLOW( $S^{'}$ ), the cell $M [S^{'}, else]$ holds both $S^{'}$ -productions, and keeping $S^{'} \to else S$ gives the nearest-then rule. The grammar is still not LL(1); the parser simply resolves the conflict by choice.

EXAM TIP

Ambiguity is undecidable in general, but one string with two parse trees proves it. A table or item-set conflict proves only that the grammar is not in that class (LL(1), SLR(1), …), not that it is ambiguous.

Preparing a grammar for top-down parsing

A predictive top-down parser loops forever on left recursion ( $A \Rightarrow^{+} A α$ ) and cannot choose between productions that start with a common prefix. Both are removed by rewriting the grammar. The rewritten grammar generates the same language but has a different parse tree shape.

REMOVING IMMEDIATE LEFT RECURSION

A A A^{'} \to A α_{1} ∣ \dots ∣ A α_{m} ∣ β_{1} ∣ \dots ∣ β_{n} ⇓ \to β_{1} A^{'} ∣ \dots ∣ β_{n} A^{'} \to α_{1} A^{'} ∣ \dots ∣ α_{m} A^{'} ∣ ε

Conditions: no $β_{i}$ starts with $A$ , and no $α_{i}$ is $ε$ . $A^{'}$ is a new nonterminal. The new grammar has $n + m + 1$ alternatives in total: $n$ for $A$ and $m + 1$ for $A^{'}$ .

LEFT FACTORING

A A A^{'} \to α β_{1} ∣ α β_{2} ∣ γ ⇓ \to α A^{'} ∣ γ \to β_{1} ∣ β_{2}

Applies when two or more alternatives of $A$ share a nonempty prefix $α$ (take the longest one); $A^{'}$ is a new nonterminal, and an empty $β_{i}$ becomes $ε$ . Repeat until no two alternatives of any nonterminal share a prefix.

Removing indirect left recursion

Order the nonterminals $A_{1}, A_{2}, \dots, A_{n}$ .
For $i = 1$ to $n$ : for each $j < i$ , replace every production $A_{i} \to A_{j} γ$ by $A_{i} \to δ_{1} γ ∣ \dots ∣ δ_{k} γ$ , where $A_{j} \to δ_{1} ∣ \dots ∣ δ_{k}$ are the current productions of $A_{j}$ .
Then remove the immediate left recursion of $A_{i}$ using the formula above.
The algorithm is guaranteed to work on a grammar with no cycles ( $A \Rightarrow^{+} A$ ) and no $ε$ -productions; remove those first if present.

EXAM TIP

Removing left recursion and left factoring are necessary for LL(1) but not sufficient: the result can still fail the LL(1) test. Bottom-up parsers have no trouble with left recursion; on a long list, left recursion keeps an LR parser's stack shallow, while right recursion makes the stack grow with the length of the list.

FIRST and FOLLOW sets

$FIRST (α)$ is the set of terminals that can begin a string derived from $α$ , plus $ε$ if $α \Rightarrow^{*} ε$ . $FOLLOW (A)$ is the set of terminals that can appear immediately to the right of $A$ in some sentential form derived from the start symbol, plus $ if $A$ can be the rightmost symbol of such a sentential form. FOLLOW never contains $ε$ and is defined only for nonterminals.

Computing FIRST

For a terminal $a$ : $FIRST (a) = {a}$ .
For a production $A \to ε$ : add $ε$ to $FIRST (A)$ .
For a production $A \to X_{1} X_{2} \dots X_{k}$ : add $FIRST (X_{1}) ∖ {ε}$ to $FIRST (A)$ ; if $ε \in FIRST (X_{1})$ , also add $FIRST (X_{2}) ∖ {ε}$ , and so on.
Add $ε$ to $FIRST (A)$ from this production only if every $X_{i}$ can derive $ε$ .
FIRST of a string $X_{1} X_{2} \dots X_{k}$ is computed the same way.
Repeat over all productions until no set changes.

Computing FOLLOW

Put $ in $FOLLOW (S)$ for the start symbol $S$ .
For a production $A \to α B β$ : add $FIRST (β) ∖ {ε}$ to $FOLLOW (B)$ .
For a production $A \to α B$ , or $A \to α B β$ with $ε \in FIRST (β)$ : add all of $FOLLOW (A)$ to $FOLLOW (B)$ .
Repeat until no set changes.

WORKED EXAMPLE

Grammar (start symbol $S$ ): $S \to A B c$ , $A \to a A ∣ ε$ , $B \to b B ∣ ε$ . Compute FIRST and FOLLOW for every nonterminal.

Solution

FIRST( $A$ ) = ${a, ε}$ and FIRST( $B$ ) = ${b, ε}$ , since each has an $ε$ -alternative.
FIRST( $S$ ): start with FIRST( $A$ ) minus $ε$ = ${a}$ ; $A$ is nullable, so add FIRST( $B$ ) minus $ε$ = ${b}$ ; $B$ is nullable too, so add FIRST( $c$ ) = ${c}$ . So FIRST( $S$ ) = ${a, b, c}$ with no $ε$ , because $c$ is a terminal.
FOLLOW( $S$ ) = {$} (start symbol, and $S$ appears on no right side).
FOLLOW( $A$ ): in $S \to A B c$ the string after $A$ is $B c$ , with FIRST( $B c$ ) = ${b, c}$ . In $A \to a A$ the symbol $A$ is last, so add FOLLOW( $A$ ) to itself (no change). So FOLLOW( $A$ ) = ${b, c}$ .
FOLLOW( $B$ ): the string after $B$ in $S \to A B c$ is $c$ , giving ${c}$ ; $B \to b B$ adds FOLLOW( $B$ ) to itself. So FOLLOW( $B$ ) = ${c}$ .

Answer: FIRST: S = {a, b, c}, A = {a, ε}, B = {b, ε}. FOLLOW: S = {$}, A = {b, c}, B = {c}.

The sets from the worked example

Nonterminal	FIRST	FOLLOW
$S$	${a, b, c}$	{`$`}
$A$	${a, ε}$	${b, c}$
$B$	${b, ε}$	${c}$

EXAM TIP

Keep a separate list of nullable nonterminals first. The usual slips are stopping at a nullable symbol instead of continuing past it, and putting $ε$ into a FOLLOW set.

LL(1) grammars and predictive parsing

An LL(1) parser reads the input Left to right, builds a Leftmost derivation, and uses 1 symbol of lookahead. A predictive parser keeps a stack of grammar symbols (start symbol on top of $) and a table $M [A, a]$ with a row per nonterminal and a column per terminal plus $. If the top is a terminal it must match the input; if it is a nonterminal $A$ and the lookahead is $a$ , it pops $A$ and pushes the right side of $M [A, a]$ so that its leftmost symbol ends on top (that is, in reverse order). It accepts when the stack top and the input are both $. An empty entry is a syntax error. A recursive-descent parser (one procedure per nonterminal) that picks each production from one lookahead symbol, with no backtracking, implements the same idea.

Building the LL(1) table

For each production $A \to α$ and each terminal $a \in FIRST (α)$ , put $A \to α$ in $M [A, a]$ .
If $ε \in FIRST (α)$ , put $A \to α$ in $M [A, b]$ for every $b \in FOLLOW (A)$ , including $.
Every cell left empty is an error entry.
A cell holding two or more productions is a conflict, and the grammar is not LL(1).

LL(1) CONDITION

For every pair A \to α ∣ β : FIRST (α) \cap FIRST (β) = \emptyset, and if β \Rightarrow^{*} ε then FIRST (α) \cap FOLLOW (A) = \emptyset

Also at most one alternative of $A$ may derive $ε$ . The condition holds for every nonterminal exactly when no cell of the LL(1) table has two entries.

LL(1) table for $S \to ABc$, $A \to aA \mid \varepsilon$, $B \to bB \mid \varepsilon$

	$a$	$b$	$c$	`$`
$S$	$S \to A B c$	$S \to A B c$	$S \to A B c$	error
$A$	$A \to a A$	$A \to ε$	$A \to ε$	error
$B$	error	$B \to b B$	$B \to ε$	error

No cell has two entries, so this grammar is LL(1). The entries $A \to ε$ under $b$ and $c$ come from FOLLOW( $A$ ) = ${b, c}$ , and $B \to ε$ under $c$ comes from FOLLOW( $B$ ) = ${c}$ .

EXAM TIP

A grammar is not LL(1) if it is ambiguous, left recursive (in a nonterminal that is reachable and derives some terminal string), or has two alternatives of one nonterminal with a common first terminal. Check nullable alternatives against FOLLOW: for $A \to a A ∣ ε$ with $a \in FOLLOW (A)$ the entry $M [A, a]$ gets both productions, which is the classic hidden conflict.

Bottom-up parsing: shift-reduce, LR(0) and SLR(1)

A bottom-up parser reduces the input to the start symbol. A handle of a right-sentential form is the right side of a production, at a particular position, whose replacement by the production's left side gives the previous right-sentential form of a rightmost derivation. Reducing handles one after another is called handle pruning. A shift-reduce parser has a stack and four moves: shift the next input symbol, reduce a handle on top of the stack, accept and error. The stack contents are always a viable prefix: a prefix of a right-sentential form that does not extend past the right end of its handle. The set of viable prefixes is a regular language, and the LR(0) automaton built below is a DFA that recognises it.

Two conflicts can arise. A shift-reduce conflict: the parser cannot tell whether to shift or to reduce. A reduce-reduce conflict: two different reductions are possible. Shift-shift conflicts cannot occur, because shifting a given symbol leads to one state.

An LR(0) item is a production with a dot marking how much of the right side has been seen, written $A \to α \cdot β$ . A production whose right side has $n$ symbols gives $n + 1$ items; for $A \to ε$ the only item is $A \to \cdot$ . The grammar is augmented with a new start production $S^{'} \to S$ , and reaching $S^{'} \to S \cdot$ with $ as the next input means accept.

Building the LR(0) automaton (canonical collection)

Closure( $I$ ): start with the items of $I$ . While some item $A \to α \cdot B β$ is present, add $B \to \cdot γ$ for every production of $B$ .
Goto( $I$ , $X$ ): move the dot over $X$ in every item of $I$ of the form $A \to α \cdot X β$ , then take the closure.
Start with $I_{0}$ = closure of ${S^{'} \to \cdot S}$ . Repeatedly apply Goto for every grammar symbol until no new set appears. Each set is a state.
Action table, LR(0): if $A \to α \cdot a β$ is in a state, shift on terminal $a$ . If a completed item $A \to α \cdot$ (other than $S^{'} \to S \cdot$ ) is in a state, reduce by it in every terminal column, including $. $S^{'} \to S \cdot$ gives accept under $. The goto table holds transitions on nonterminals.
SLR(1): the same automaton, but reduce by $A \to α$ only on terminals in $FOLLOW (A)$ .

WORKED EXAMPLE

Augmented grammar: $S^{'} \to S$ , $S \to (S) ∣ x$ . Build the LR(0) states, say whether the grammar is LR(0), and count the moves the parser makes on ((x)).

Solution

$I_{0}$ : $S^{'} \to \cdot S$ , $S \to \cdot (S)$ , $S \to \cdot x$ .
Goto( $I_{0}$ , $S$ ) = $I_{1}$ : $S^{'} \to S \cdot$ . Goto( $I_{0}$ , () = $I_{2}$ : $S \to (\cdot S)$ , $S \to \cdot (S)$ , $S \to \cdot x$ . Goto( $I_{0}$ , x) = $I_{3}$ : $S \to x \cdot$ .
Goto( $I_{2}$ , $S$ ) = $I_{4}$ : $S \to (S \cdot)$ . Goto( $I_{2}$ , () = $I_{2}$ and Goto( $I_{2}$ , x) = $I_{3}$ .
Goto( $I_{4}$ , )) = $I_{5}$ : $S \to (S) \cdot$ . No further sets appear, so there are 6 states.
The only states with a completed item are $I_{1}$ (accept), $I_{3}$ and $I_{5}$ , each holding that single item. No state mixes a completed item with another item, so there is no conflict: the grammar is LR(0).
Moves on ((x)): shift (, shift (, shift x, reduce $S \to x$ , shift ), reduce $S \to (S)$ , shift ), reduce $S \to (S)$ , then accept. That is 5 shifts and 3 reductions: 8 moves before accept.

Answer: 6 states; the grammar is LR(0); the parse takes 5 shifts and 3 reductions (8 moves), then accept.

MOVES OF A DETERMINISTIC PARSER

moves = ∣ w ∣ + p

Applies to LL(1) and LR parsers on an accepted string $w$ of $∣ w ∣$ tokens whose parse tree has $p$ internal nodes, not counting the augmented start $S^{'}$ . In LL, $∣ w ∣$ counts the matches and $p$ the expansions; in LR, $∣ w ∣$ counts the shifts and $p$ the reductions. A node for an $ε$ -production counts in $p$ . Accept, and the final match of $, are not counted unless the question says so.

EXAM TIP

Conflicts in an LR(0) state: $A \to α \cdot$ together with $B \to β \cdot aγ$ is a shift-reduce conflict, and two completed items are a reduce-reduce conflict. SLR(1) removes the shift-reduce conflict when $a \in / FOLLOW (A)$ , and removes the reduce-reduce conflict between $A \to α \cdot$ and $B \to β \cdot$ when $FOLLOW (A) \cap FOLLOW (B) = \emptyset$ .

Canonical LR(1) and LALR(1)

An LR(1) item $[A \to α \cdot β, a]$ pairs an LR(0) item with a lookahead terminal $a$ (or $): the parser may reduce by $A \to α β$ only if the next input symbol is $a$ . This is more precise than FOLLOW( $A$ ), which merges every context in which $A$ appears. Convention: several lookaheads for one item are written as $[A \to α \cdot β, a / b]$ .

LR(1) CLOSURE

[A \to α \cdot B β, a] \Rightarrow add [B \to \cdot γ, b] for every production B \to γ and every b \in FIRST (β a)

If $β$ is empty or nullable, $a$ itself is among the new lookaheads. The initial item is $S^{'} \to \cdot S$ with lookahead $. Goto works exactly as in LR(0), carrying the lookaheads along unchanged. Reduce by $A \to α$ only on the item's own lookahead.

Building LALR(1)

Build the canonical LR(1) collection.
Find states with identical cores (the same LR(0) items, ignoring lookaheads) and merge each group into one state, taking the union of the lookaheads item by item.
The merged cores are exactly the states of the LR(0) automaton, so LALR(1) has as many states as LR(0). Build the action table as for LR(1), reducing on the merged lookaheads.

What merging can and cannot do. Merging can never create a shift-reduce conflict: the shift items depend only on the core, so a merged state with a shift-reduce conflict on $a$ means one of the original states already held the same reduce item with lookahead $a$ and the same shift item. Merging can create reduce-reduce conflicts, because two states may reduce by different productions with different lookaheads, and the union makes those lookaheads overlap. On an erroneous input an LALR(1) parser may make some extra reductions before it reports the error, but it never shifts an input symbol beyond the point where the canonical LR(1) parser would report it.

WORKED EXAMPLE

Grammar: $S \to a A d ∣ b B d ∣ a B e ∣ b A e$ , $A \to c$ , $B \to c$ . Show that it is LR(1) but not LALR(1).

Solution

After shifting a, the closure contains $[A \to \cdot c, d]$ (from $a A d$ ) and $[B \to \cdot c, e]$ (from $a B e$ ). After shifting c the state is ${[A \to c \cdot, d], [B \to c \cdot, e]}$ . The lookaheads differ, so there is no conflict.
After shifting b, the closure has $[B \to \cdot c, d]$ (from $b B d$ ) and $[A \to \cdot c, e]$ (from $b A e$ ). After c the state is ${[A \to c \cdot, e], [B \to c \cdot, d]}$ . Again no conflict, and no other state has a conflict, so the grammar is LR(1).
The two states after c have the same core ${A \to c \cdot, B \to c \cdot}$ , so LALR merges them into ${[A \to c \cdot, d / e], [B \to c \cdot, d / e]}$ .
On d or e the merged state can reduce by $A \to c$ or by $B \to c$ : a reduce-reduce conflict.

Answer: The grammar is LR(1) but not LALR(1). It is not SLR(1) either, since FOLLOW( $A$ ) = FOLLOW( $B$ ) = ${d, e}$ .

Comparing parsers, and operator precedence

GRAMMAR-CLASS HIERARCHY

LR (0) \subset SLR (1) \subset LALR (1) \subset LR (1), LL (1) \subset LR (1)

Each inclusion is proper. A grammar class here means the set of grammars the method parses without conflict. LL(1) is not contained in LALR(1), SLR(1) or LR(0), and none of those is contained in LL(1): LL(1) is incomparable with each of them. More generally every LL(k) grammar is LR(k).

Comparison of the bottom-up methods

Method	Item set	Reduce $A \to α$ when lookahead is	Number of states	Conflicts possible
LR(0)	LR(0) items	any terminal or `$`	$n$ (the LR(0) count)	shift-reduce, reduce-reduce
SLR(1)	LR(0) items	in $FOLLOW (A)$	same as LR(0)	shift-reduce, reduce-reduce
LALR(1)	LR(1) items merged by core	in the item's merged lookahead set	same as LR(0)	reduce-reduce (new ones), shift-reduce only if LR(1) had them
LR(1)	LR(1) items	the item's own lookahead	at least as many as LR(0), often many more	shift-reduce, reduce-reduce

EXAM TIP

LR(0), SLR(1) and LALR(1) always have the same number of states for one grammar; canonical LR(1) has the same or more. Parser generators of the YACC/Bison family build LALR(1) tables. An LL(1) grammar need not be SLR(1): $S \to A a A b ∣ B b B a$ , $A \to ε$ , $B \to ε$ is LL(1), but $I_{0}$ holds both $A \to \cdot$ and $B \to \cdot$ , and FOLLOW( $A$ ) = FOLLOW( $B$ ) = ${a, b}$ gives a reduce-reduce conflict in the SLR table.

EXAM TIP

An LL(1) grammar need not be LALR(1) either: $S \to a A ∣ b B$ , $A \to C a ∣ D b$ , $B \to C b ∣ D a$ , $C \to E$ , $D \to E$ , $E \to ε$ is LL(1), but the LR(1) states ${[C \to E \cdot, a], [D \to E \cdot, b]}$ (reached after a) and ${[C \to E \cdot, b], [D \to E \cdot, a]}$ (reached after b) share a core, and merging them gives a reduce-reduce conflict on a and b.

WORKED EXAMPLE

Grammar: $S \to L = R ∣ R$ , $L \to * R ∣ id$ , $R \to L$ . Show that it is LALR(1) but not SLR(1).

Solution

$I_{0}$ = closure of $S^{'} \to \cdot S$ contains $S \to \cdot L = R$ , $S \to \cdot R$ , $L \to \cdot * R$ , $L \to \cdot id$ , $R \to \cdot L$ . Goto( $I_{0}$ , $L$ ) = ${S \to L \cdot = R, R \to L \cdot}$ .
FOLLOW: $ is in FOLLOW( $S$ ), hence in FOLLOW( $R$ ) (from $S \to R$ ). From $S \to L = R$ , = is in FOLLOW( $L$ ). From $R \to L$ and $L \to * R$ , FOLLOW( $L$ ) = FOLLOW( $R$ ) = {=, $}.
SLR(1): in Goto( $I_{0}$ , $L$ ), shift on = and reduce $R \to L$ on FOLLOW( $R$ ), which contains =: a shift-reduce conflict, so the grammar is not SLR(1).
LR(1): in $I_{0}$ the item $R \to \cdot L$ comes from $S \to \cdot R$ with lookahead $ only, so the state after $L$ holds $R \to L \cdot$ with lookahead $ only. There it shifts on = and reduces on $: no conflict.
No other LR(1) state has the core ${S \to L \cdot = R, R \to L \cdot}$ , so merging leaves that state unchanged; the merged states elsewhere contain a single completed item or only shifts. So the LALR(1) table has no conflict.

Answer: The grammar is LALR(1) (hence LR(1)) but not SLR(1).

Operator-precedence parsing works for operator grammars: no right side is $ε$ and no right side has two adjacent nonterminals. For each pair of terminals $a, b$ the parser uses one relation: $a ⋖ b$ ( $a$ yields precedence to $b$ : shift), $a ≐ b$ (same handle, keep shifting), or $a ⋗ b$ ( $a$ takes precedence: reduce). The handle is the span between the nearest $⋖$ and the $⋗$ that holds between the top terminal of the stack and the next input symbol, and the parser looks only at terminals, ignoring which nonterminals sit between them. It is simple and fast, and it can parse some ambiguous expression grammars once precedence and associativity are given. Because it ignores nonterminals, it works for only a small class of grammars, it cannot handle an operator such as unary minus that shares its symbol with a binary operator, and one cannot always be sure it accepts exactly the language of the grammar.

EXAM TIP

When an LR parser generator is given an ambiguous expression grammar, precedence and associativity declarations settle each shift-reduce conflict. With $E op_{1} E$ on the stack and $op_{2}$ next: if $op_{2}$ has higher precedence, shift; if lower, reduce; if equal, reduce for a left-associative operator and shift for a right-associative one.

PREVIOUS-YEAR QUESTIONS

13 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 1 · GATE CSE 2026 Set 2 · GATE CSE 2025 Set 1 · GATE CSE 2025 Set 2 · GATE CSE 2024 Set 1 · GATE CSE 2024 Set 2 · GATE CSE 2022 · GATE CSE 2020 · GATE CSE 2018

GATE 2026 CS1 Q.28

GATE 2026 · CS1Q.28 · 1 mark · MSQ

Which of the following statements is/are true?

(A)
LL(1) parser uses backtracking
(B)
For a grammar to be LL(1), it must be left-recursive
(C)
For a grammar to be LL(1), it must be left-factored
(D)
The LL(1) parsers are more powerful than the SLR parsers

Official answer

Official answer: CSource: Official answer key, GATE 2026 CS1 (IIT Guwahati)

See the question in the paper

Tap to open full size

GATE 2026 CS1 Q.28: official answer

GATE 2026 CS2 Q.41

GATE 2026 · CS2Q.41 · 2 marks · MCQ

Consider the canonical $L R (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 \to A C B$
$A \to a A ∣ ϵ$
$C \to c C ∣ ϵ$
$B \to b B ∣ b$

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

(A)
2
(B)
3
(C)
4
(D)
5

Answer and solution

GATE 2026 CS2 Q.41: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS2 Q.41: answer and solution

GATE 2025 CS1 Q.46

GATE 2025 · CS1Q.46 · 2 marks · MSQ

Which of the following statement(s) is/are TRUE while computing First and Follow during top down parsing by a compiler?

(A)
For a production $A \to ϵ$ , $ϵ$ will be added to $First (A)$ .
(B)
If there is any input right end marker, it will be added to $First (S)$ , where $S$ is the start symbol.
(C)
For a production $A \to ϵ$ , $ϵ$ will be added to $Follow (A)$ .
(D)
If there is any input right end marker, it will be added to $Follow (S)$ , where $S$ is the start symbol.

Answer and solution

GATE 2025 CS1 Q.46: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS1 Q.46: answer and solution

GATE 2025 CS2 Q.40

GATE 2025 · CS2Q.40 · 2 marks · MCQ

Given a Context-Free Grammar $G$ as follows:

$S \to A a ∣ b A c ∣ d c ∣ b d a$

$A \to d$

Which ONE of the following statements is TRUE?

(A)
$G$ is neither LALR(1) nor SLR(1)
(B)
$G$ is CLR(1), not LALR(1)
(C)
$G$ is LALR(1), not SLR(1)
(D)
$G$ is LALR(1), also SLR(1)

Answer and solution

GATE 2025 CS2 Q.40: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS2 Q.40: answer and solution

GATE 2025 CS2 Q.51

GATE 2025 · CS2Q.51 · 2 marks · MSQ

Consider two grammars $G_{1}$ and $G_{2}$ with the production rules given below:

$G_{1}$ : $S \to i f E t h e n S ∣ i f E t h e n S e l se S ∣ a$ ; $E \to b$

$G_{2}$ : $S \to i f E t h e n S ∣ M$ ; $M \to i f E t h e n M e l se S ∣ c$ ; $E \to b$

where $i f, t h e n, e l se, a, b, c$ are the terminals. Which of the following option(s) is/are CORRECT?

(A)
$G_{1}$ is not $LL (1)$ and $G_{2}$ is $LL (1)$ .
(B)
$G_{1}$ is $LL (1)$ and $G_{2}$ is not $LL (1)$ .
(C)
$G_{1}$ and $G_{2}$ are not $LL (1)$ .
(D)
$G_{1}$ and $G_{2}$ are ambiguous.

Answer and solution

GATE 2025 CS2 Q.51: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS2 Q.51: answer and solution

GATE 2024 CS1 Q.26

GATE 2024 · CS1Q.26 · 1 mark · MSQ

Which of the following is/are Bottom-Up Parser(s)?

(A)
Shift-reduce Parser
(B)
Predictive Parser
(C)
LL(1) Parser
(D)
LR Parser

Answer and solution

GATE 2024 CS1 Q.26: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS1 Q.26: answer and solution

GATE 2024 CS1 Q.38

GATE 2024 · CS1Q.38 · 2 marks · MCQ

Consider the following grammar $G$ , with $S$ as the start symbol. The grammar $G$ has three incomplete productions denoted by (1), (2), and (3).

S \to d a T ∣ \underline{(1)} T \to a S ∣ b T ∣ \underline{(2)} R \to \underline{(3)} ∣ ε

The set of terminals is ${a, b, c, d, f}$ . The FIRST and FOLLOW sets of the different non-terminals are as follows.

$FIRST (S) = {c, d, f}$ , $FIRST (T) = {a, b, ε}$ , $FIRST (R) = {c, ε}$

$FOLLOW (S) = FOLLOW (T)$ is the set of the three symbols $c$ , $f$ and the end marker $, and $FOLLOW (R) = {f}$ .

Which one of the following options CORRECTLY fills in the incomplete productions?

(A)
(1) $S \to R f$ , (2) $T \to ε$ , (3) $R \to c T R$
(B)
(1) $S \to f R$ , (2) $T \to ε$ , (3) $R \to c T R$
(C)
(1) $S \to f R$ , (2) $T \to c T$ , (3) $R \to c R$
(D)
(1) $S \to R f$ , (2) $T \to c T$ , (3) $R \to c R$

Answer and solution

GATE 2024 CS1 Q.38: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS1 Q.38: answer and solution

GATE 2024 CS2 Q.40

GATE 2024 · CS2Q.40 · 2 marks · MCQ

Consider the following context-free grammar where the start symbol is $S$ and the set of terminals is ${a, b, c, d}$ .

$S \to A a A b ∣ B b B a$
$A \to c S ∣ ε$
$B \to d S ∣ ε$

The following is a partially-filled LL(1) parsing table (rows S, A, B; columns a, b, c, d, $).

Which one of the following options represents the CORRECT combination for the numbered cells in the parsing table?

Note: In the options, "blank" denotes that the corresponding cell is empty.

GATE 2024 CS2 question 40: LL(1) parsing table with columns a, b, c, d, and rows S, A, B. — Figure from the GATE 2024 CS2 paper. It is part of the question.

(A)
(1) S -> AaAb (2) S -> BbBa (3) A -> epsilon (4) B -> epsilon
(B)
(1) S -> BbBa (2) S -> AaAb (3) A -> epsilon (4) B -> epsilon
(C)
(1) S -> AaAb (2) S -> BbBa (3) blank (4) blank
(D)
(1) S -> BbBa (2) S -> AaAb (3) blank (4) blank

Answer and solution

GATE 2024 CS2 Q.40: answer and solution

GATE 2024 CS2 Q.65

GATE 2024 · CS2Q.65 · 2 marks · NAT

Consider the following augmented grammar, which is to be parsed with a SLR parser. The set of terminals is {a, b, c, d, #, @}

$S^{'} \to S$
$S \to S S ∣ A a ∣ b A c ∣ B c ∣ b B a$
$A \to d #$
$B \to @$

Let $I_{0} = CLOSURE ({S^{'} \to ∙ S})$ . The number of items in the set $GOTO (I_{0}, S)$ is ______

Answer and solution

GATE 2024 CS2 Q.65: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS2 Q.65: answer and solution

GATE 2022 CS Q.13

GATE 2022 · CSQ.13 · 1 mark · MCQ

Which one of the following statements is TRUE?

(A)
The $L A L R (1)$ parser for a grammar $G$ cannot have reduce-reduce conflict if the $L R (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)
$L R (1)$ parsing is sufficient for deterministic context-free languages.

Answer and solution

GATE 2022 CS Q.13: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 CS Q.13: answer and solution

Show the other 3 questions

GATE 2022 CS Q.29

GATE 2022 · CSQ.29 · 1 mark · NAT

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 $I_{0}$ is the set of two LR(0) items ${[S^{'} \to S \cdot], [S \to S \cdot + R]}$ , then $g o t o (c l os u r e (I_{0}), +)$ contains exactly ______ items.

Answer and solution

GATE 2022 CS Q.29: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 CS Q.29: answer and solution

GATE 2020 CS Q.24

GATE 2020 · CSQ.24 · 1 mark · NAT

Consider the following grammar.

$S \to a S B ∣ d$
$B \to b$

The number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is ____.

Answer and solution

GATE 2020 CS Q.24: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 CS Q.24: answer and solution

GATE 2018 CS Q.38

GATE 2018 · CSQ.38 · 2 marks · MCQ

Consider the following parse tree for the expression a#b$c$d#e#f, involving two binary operators $ and #.

Which one of the following is correct for the given parse tree?

GATE 2018 CS question 38: Parse tree. — Figure from the GATE 2018 CS paper. It is part of the question.

(A)
$ has higher precedence and is left associative; # is right associative
(B)
# has higher precedence and is left associative; $ is right associative
(C)
$ has higher precedence and is left associative; # is left associative
(D)
# has higher precedence and is right associative; $ is left associative

Answer and solution

GATE 2018 CS Q.38: answer and solution

OTHER EXAMS

ISRO: 2 questions

From ISRO's Scientist/Engineer written test: ISRO CS 2025, ISRO CS 2023. They are not counted in the GATE numbers on this page.

ISRO CS 2025 Q.31

ISRO 2025 · CSQ.31 · 1 mark · MCQ

Which one of the following tools generates parser from BNF notation?

(A)
lex
(B)
yacc
(C)
ed
(D)
gdb

Answer and solution

ISRO CS 2025 Q.31: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2025 Q.31: answer and solution

ISRO CS 2023 Q.11

ISRO 2023 · CSQ.11 · 1 mark · MCQ

In the context of parsing techniques, LL(1) refers to:

(A)
Grammars that parse the input from left to right, produce a rightmost derivation, with a lookahead of 1 symbol.
(B)
Grammars that parse the input from left to right, produce a leftmost derivation, with a lookahead of 1 symbol.
(C)
Grammars that parse the input from left to right, and backtrack at most once.
(D)
Grammars that parse the input from right to left, produce a leftmost derivation, and backtrack at most once.

Answer and solution

ISRO CS 2023 Q.11: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2023 Q.11: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 11 mark · NAT

The grammar $A \to A a ∣ A b ∣ c ∣ d$ is rewritten by the standard procedure for removing immediate left recursion. Counting every alternative as a separate production, how many productions does the new grammar have?

Answer and solution

Answer: $5$

Here $α_{1} = a$ , $α_{2} = b$ , $β_{1} = c$ , $β_{2} = d$ .
The new grammar is $A \to c A^{'} ∣ d A^{'}$ and $A^{'} \to a A^{'} ∣ b A^{'} ∣ ε$ .
That is 2 alternatives for $A$ and 3 for $A^{'}$ , so $2 + 3 = 5$ productions.

PRACTICE 22 marks · NAT

Grammar (start symbol $S$ ): $S \to A B$ , $A \to a A ∣ ε$ , $B \to b B ∣ A c$ . What is $∣ FOLLOW (A) ∣ + ∣ FOLLOW (B) ∣$ ? (The end marker $ counts as a member where it appears.)

Answer and solution

Answer: $4$

FIRST( $A$ ) = ${a, ε}$ . FIRST( $B$ ): from $b B$ we get $b$ ; from $A c$ we get $a$ , and since $A$ is nullable also $c$ . So FIRST( $B$ ) = ${a, b, c}$ and $B$ is not nullable.
FOLLOW( $S$ ) = {$}.
FOLLOW( $A$ ): from $S \to A B$ add FIRST( $B$ ) = ${a, b, c}$ ( $B$ is not nullable, so nothing from FOLLOW( $S$ )); from $A \to a A$ add FOLLOW( $A$ ) to itself; from $B \to A c$ add $c$ . So FOLLOW( $A$ ) = ${a, b, c}$ , size 3.
FOLLOW( $B$ ): from $S \to A B$ add FOLLOW( $S$ ) = {$}; $B \to b B$ adds nothing new. So FOLLOW( $B$ ) = {$}, size 1.
Sum = $3 + 1 = 4$ .

PRACTICE 32 marks · MSQ

Which of the following statements are true?

(A)
Every LL(1) grammar is LR(1).
(B)
Every LR(0) grammar is SLR(1).
(C)
Merging LR(1) states with the same core can introduce a new shift-reduce conflict.
(D)
For a given grammar, the SLR(1) and LALR(1) parsers have the same number of states.

Answer and solution

Answer: (A), (B), (D)

A is true: LL(1) grammars form a proper subset of LR(1) grammars.
B is true: the SLR(1) table only removes reductions (they happen on FOLLOW instead of everywhere), so an LR(0) grammar stays conflict-free.
C is false: merging can introduce only reduce-reduce conflicts, since shift items depend on the core alone.
D is true: both use exactly the states of the LR(0) automaton.

PRACTICE 41 mark · MCQ

Which one of the following grammars (start symbol $S$ ) is LL(1)?

(A)
$S \to a S ∣ a$
(B)
$S \to S a ∣ b$
(C)
$S \to a S b ∣ ε$
(D)
$S \to A a ∣ b, A \to a ∣ ε$

Answer and solution

Answer: (C)

A: both alternatives begin with $a$ , so $M [S, a]$ has two entries (it needs left factoring).
B: left recursive. FIRST( $S a$ ) = FIRST( $S$ ) = ${b}$ = FIRST( $b$ ), so $M [S, b]$ holds both productions; not LL(1).
C: FIRST( $a S b$ ) = ${a}$ ; the $ε$ -alternative goes under FOLLOW( $S$ ) = { $b$ , $}. These do not meet, so there is no conflict: LL(1).
D: FOLLOW( $A$ ) = ${a}$ , so $A \to ε$ is placed under $a$ , where $A \to a$ is also placed: a conflict.

PRACTICE 52 marks · NAT

Consider the grammar $E \to E + n ∣ n$ (start symbol $E$ , terminals $+$ and $n$ ). An SLR(1) parser parses the string $n + n + n$ and accepts it. Counting only shift and reduce moves (the accept move is not counted), how many moves does the parser make?

Answer and solution

Answer: $8$

The string has $∣ w ∣ = 5$ tokens, so there are 5 shifts.
The parse tree uses $E \to n$ once and $E \to E + n$ twice, so $p = 3$ reductions.
Total moves = $∣ w ∣ + p = 5 + 3 = 8$ .
The sequence is: shift $n$ , reduce $E \to n$ , shift $+$ , shift $n$ , reduce $E \to E + n$ , shift $+$ , shift $n$ , reduce $E \to E + n$ .

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

parsing

Preparing in Kolkata? IAE Academy's course for GATE CSE.