Parsing is the highest-yield topic in compiler design, and GATE tests both halves of it thoroughly: top-down parsing with FIRST and FOLLOW sets and LL(1) tables, and bottom-up parsing with handles and the LR, SLR and LALR family. The questions reward a firm grip on a few definitions rather than heavy computation. Parsing sits directly on top of context-free grammars, so if the grammar machinery feels shaky, pair this set with the Context-Free Grammar MCQs. Below are 12 solved MCQs from KnowledgeGate's published question bank, every one a previous-year GATE problem with the year marked. Attempt each before the explanation, and follow the inline link to its solved page inside the Compiler Design learn module.
Grammars and what they can express
Q1. Which feature cannot be captured by context-free grammars? (GATE 1994, see the solved page)
(a) Syntax of if-then-else statements
(b) Syntax of recursive procedures
(c) Whether a variable has been declared before its use
(d) Variable names of arbitrary length
Answer: (c) Whether a variable has been declared before its use.
Nesting, balanced brackets and recursive structure are all context-free, so options (a), (b) and (d) are fine. Checking that a name was declared before use requires remembering an unbounded set of names across scopes, which is a context-sensitive, symbol-table job that a pure CFG cannot do. This is why semantic analysis exists as a separate phase.
Q2. P: every regular grammar is LL(1). Q: every regular set has an LR(1) grammar. Which is TRUE? (GATE 2007, see the solved page)
(a) Both P and Q are true
(b) P is true and Q is false
(c) P is false and Q is true
(d) Both P and Q are false
Answer: (c) P is false, Q is true.
P fails because a regular grammar can still be left-recursive or ambiguous, and those are not LL(1). Q holds because every regular language has a deterministic grammar, and LR(1) parsers accept all deterministic context-free languages, which include the regular ones. So the LR family is strictly more forgiving than LL(1) here.
Top-down parsing: leftmost, FIRST, FOLLOW and LL(1)
Q3. Which derivation does a top-down parser use, with input scanned left to right? (GATE 2000, see the solved page)
(a) Leftmost derivation
(b) Leftmost derivation traced in reverse
(c) Rightmost derivation
(d) Rightmost derivation traced in reverse
Answer: (a) Leftmost derivation.
A top-down parser starts from the start symbol and expands non-terminals until it reaches the leaves. To keep pace with input read left to right, it always expands the leftmost non-terminal first, which is exactly a leftmost derivation. Contrast this with bottom-up parsers, which build a rightmost derivation in reverse.
Q4. For the grammar p → xQRS, Q → yz | z, R → w | ε, S → y, what is FOLLOW(Q)? (GATE 2017, see the solved page)
(a) {R}
(b) {w}
(c) {w, y}
(d) {w, $}
Answer: (c) {w, y}.
FOLLOW(Q) is whatever can begin the string after Q in p → xQRS, so look at FIRST(R). Since R → w | ε, FIRST(R) = {w, ε}; the w goes into FOLLOW(Q), and because R is nullable you also add FIRST(S) = {y}. The end marker $ is excluded because S → y is not nullable, so FOLLOW(Q) = {w, y}.
Q5. The grammar A → AA | (A) | ε is unsuitable for predictive parsing because it is (GATE 2005, see the solved page)
(a) ambiguous
(b) left-recursive
(c) right-recursive
(d) an operator grammar
Answer: (a) ambiguous.
The empty string alone has two derivations, A ⇒ ε directly, and A ⇒ AA ⇒ εε, so the grammar assigns more than one parse tree and is ambiguous. Predictive parsing needs a unique parse per input, so ambiguity rules it out. The grammar is also left-recursive, but ambiguity is the deeper obstacle since it cannot be removed by a mechanical transformation.
Q6. Which suffices to convert an arbitrary CFG into an LL(1) grammar? (GATE 2003, see the solved page)
(a) Removing left recursion alone
(b) Left factoring alone
(c) Removing left recursion and left factoring
(d) None of these
Answer: (d) None of these.
Removing left recursion and left factoring are useful and often necessary, but they are not sufficient: some grammars are inherently ambiguous or generate languages that simply have no LL(1) grammar. So no fixed recipe turns every CFG into an LL(1) grammar, and you must verify the LL(1) condition on the FIRST and FOLLOW sets afterwards.
Q7. For S → FR, R → *S | ε, F → id, the predictive-table entries M[S, id] and M[R, $] are (GATE 2006, see the solved page)
(a) {S → FR} and {R → ε}
(b) {S → FR} and { }
(c) {S → FR} and {R → *S}
(d) {F → id} and {R → ε}
Answer: (a) {S → FR} and {R → ε}.
FIRST(S) = FIRST(F) = {id}, so id selects S → FR, giving M[S, id] = {S → FR}. Because R is nullable and $ is in FOLLOW(R), the entry under $ takes the epsilon production, so M[R, $] = {R → ε}. Filling entries by FIRST for terminals and by FOLLOW for nullable non-terminals is the whole LL(1)-table routine.
Q8. Which one of the following is a top-down parser? (GATE 2007, see the solved page)
(a) Recursive descent parser
(b) Operator precedence parser
(c) An LR(k) parser
(d) An LALR(k) parser
Answer: (a) Recursive descent parser.
A recursive descent parser is a direct top-down implementation, one mutually recursive procedure per non-terminal, expanding from the start symbol. Operator precedence, LR(k) and LALR(k) are all bottom-up shift-reduce methods, so they sit on the other side of the divide.
Bottom-up parsing: handles, LR, SLR and LALR
Q9. Which kind of derivation is used by LR parsers? (GATE 2019, see the solved page)
(a) Leftmost
(b) Leftmost in reverse
(c) Rightmost
(d) Rightmost in reverse
Answer: (d) Rightmost in reverse.
LR parsers work bottom up, repeatedly finding a handle and reducing it. Each reduction undoes one step of a rightmost derivation, so the parser reconstructs the rightmost derivation backwards until only the start symbol remains. This is the mirror image of the top-down leftmost derivation in Q3.
Q10. Which describes a handle in LR parsing appropriately? (GATE 2008, see the solved page)
(a) The position where the next shift or reduce occurs
(b) A non-terminal whose production is used for the next reduction
(c) A production that may be used for reduction in some future step, with a position
(d) The production used for the next reduction, together with the position of its right-hand side in the sentential form
Answer: (d).
A handle is not just a production or just a position; it is both together, the exact production to reduce and the specific occurrence of its right-hand side in the current sentential form. Naming both parts is what lets the parser take the correct next step of the rightmost-derivation-in-reverse.
Q11. Which statements about parsers are correct? I: CLR is more powerful than SLR. II: SLR is more powerful than LALR. III: SLR is more powerful than CLR. (GATE 2017, see the solved page)
(a) I only
(b) II only
(c) III only
(d) II and III only
Answer: (a) I only.
The power ordering is LR(0) ≤ SLR ≤ LALR ≤ CLR, because each attaches more precise lookahead to its reduce actions. So CLR is the most powerful and I is correct, while II and III both invert the order and are false. Keep this chain memorised; it settles most parser-comparison questions.
Q12. If the SLR parser for a grammar has n1 states and the LALR parser has n2 states, then (GATE 2003, see the solved page)
(a) n1 is necessarily less than n2
(b) n1 is necessarily equal to n2
(c) n1 is necessarily greater than n2
(d) none of these
Answer: (b) n1 is necessarily equal to n2.
SLR states come straight from the LR(0) item sets, one state per LR(0) core. LALR is built by merging the canonical LR(1) states that share the same LR(0) core, so it also ends up with exactly one state per core. The two therefore have the same number of states; LALR only adds sharper lookahead, not extra states.
Where these 12 fit in your preparation
The set runs the way a parser is taught: what grammars can and cannot express (Q1-Q2), top-down parsing through FIRST, FOLLOW and the LL(1) table (Q3-Q8), and bottom-up parsing through handles and the LR hierarchy (Q9-Q12). If the FIRST and FOLLOW question cost you time, practise that computation until it is automatic, because the whole LL(1) table and half the LR questions depend on it.
Rebuild any weak area in the Compiler Design learn module, and start the front end from the beginning with the Lexical Analysis MCQs. The full GATE compiler sequence lives inside GATE Guidance by Sanchit Sir, and the GATE CS category page shows how parsing fits the syllabus. Solve, review the misses, and come back a week later for a clean second pass.
