Students often remember that top-down parsing means a leftmost derivation, but still mix up the parser's job, recursive descent, left recursion, ambiguity, and the precedence a grammar's shape encodes. Nine of the twelve questions below carry a paper tag: GATE 2000 and 2008, ISRO 2015 and 2016, MPPSC 2025, UPPSC Polytechnic Lecturer 2022, BEL 2023, HPSC 2021 and Beltron 2025. Attempt each one before you read the answer, and give Q10 and Q11 the extra minute they need, because both want a derivation written out rather than recognised. If the ground under the questions feels shaky, revise top-down and bottom-up parsing first.
1. Parser purpose and the two broad families (Q1-Q3)
The lexical analyser produces tokens. The parser checks their order against a context-free grammar, builds a parse structure and reports grammar violations. Revise tokens from the lexical analyser if that pipeline boundary is unclear.
Q1. BEL 2023
Parser is categorized into which type of context-free grammar?
A. Three
B. Two
C. Four
D. One
Answer: B. Two. The intended classification is the two broad parser families, top-down and bottom-up. A parser operates on a CFG; “two” refers to parsing strategies, not CFG types. Open the solved question.
Q2. HPSC 2021
Given a string of tokens; which of the following is the method of finding a parse?
A. Analysing
B. Recognizing
C. Parsing
D. Tokenizing
Answer: C. Parsing. For the tokens id, +, id, tokenizing has already happened. Parsing checks whether that ordered sequence fits the grammar and constructs its parse tree. Open the solved question.
Q3. UPPSC Polytechnic Lecturer 2022
Which of the following error can a compiler check?
A. Syntax Error
B. Logical Error
C. Both Logical Error and Syntax Error
D. None of the above
Answer: A. Syntax Error. A parser can reject a grammar violation such as id + * id. Using subtraction where addition was intended can remain syntactically valid, so compilation cannot generally detect it. Open the solved question.
2. What top-down parsing actually does (Q4-Q6)
A top-down parser starts at the start symbol, expands the leftmost non-terminal and scans input from left to right. It grows the tree from root to leaves; bottom-up parsing instead reconstructs a rightmost derivation in reverse.
Q4. MPPSC 2025
Which of the following statements are true about parsing in Compiler design?
i. A parser converts tokens generated by the lexical analyser into a parse tree.
ii. A top-down parser can handle left-recursive grammars without any modifications.
iii. A shift-reduce parser can make decisions based on the current input symbol and the top of the stack.
iv. LL(1) parsing is a type of bottom-up parsing technique.
Choose the correct answer from the option given below.
A. Only i, ii
B. Only i, iii
C. Only ii, iv
D. Only i, iii, iv
Answer: B. Only i, iii. Statement (i) is true. Statement (ii) is false because direct left recursion can recur before consuming input; (iii) is true for shift-reduce decisions; and (iv) is false because LL(1) is top-down predictive parsing. Open the solved question.
Q5. GATE 2000
Which of the following derivations does a top-down parser use while parsing an input string? The input is assumed to be scanned in left to right order.
A. Leftmost derivation
B. Leftmost derivation traced out in reverse
C. Rightmost derivation
D. Rightmost derivation traced out in reverse
Answer: A. Leftmost derivation. For S → aA, A → b and input ab, the parser expands S ⇒ aA ⇒ ab, always choosing the current leftmost non-terminal. Rightmost derivation in reverse describes bottom-up parsing. Open the solved question.
Q6. ISRO 2015
Which one of the following is a top-down parser?
A. Recursive descent parser
B. Shift left associative parser
C. SLR(k) parser
D. LR(k) parser
Answer: A. Recursive descent parser. With S → aA and A → b, procedure S() matches a and calls A(), which matches b. SLR and LR belong to bottom-up shift-reduce families. Open the solved question.
3. Left recursion and parser-generator families (Q7-Q8)
Left recursion determines whether recursive descent can consume input before calling itself again.
Q7. Beltron Programmer 2025
Why must left recursion be eliminated in top-down parsers?
A. It causes infinite recursion during parsing
B. It leads to ambiguity in the grammar
C. It slows down the execution of compiled programs
D. It cannot be represented using regular expressions
Answer: A. It causes infinite recursion during parsing. With S → Sa | b, S() can call itself before consuming a token. Rewrite it as S → bS′ and S′ → aS′ | ε; for baaa, it consumes b, three a tokens, then ε. Open the solved question.
Q8. ANTLR and YACC
Which of the following statements about ANTLR and YACC is correct?
A. ANTLR is an LL-family parser generator, and YACC is an LALR(1) parser generator
B. YACC is an LL-family parser generator, and ANTLR is an LALR(1) parser generator
C. Both ANTLR and YACC are LL-family parser generators
D. Both ANTLR and YACC are LALR(1) parser generators
Answer: A. ANTLR is an LL-family parser generator, and YACC is an LALR(1) parser generator. ANTLR predicts productions top-down, while YACC builds bottom-up LALR tables. Option B swaps those families. Open the solved question.
4. Recursive descent, LMD/RMD and ambiguity evidence (Q9-Q10)
A context-free grammar may have different leftmost and rightmost derivation sequences for one parse tree. Ambiguity requires two distinct parse trees for the same string.
Q9. ISRO 2016
Recursive descent parsing is an example of
A. Top-down parsers
B. Bottom-up parsers
C. Predictive parsers
D. None of the above
Answer: A. Top-down parsers. Recursive descent expands from the start symbol through procedures for non-terminals. It is predictive only when it selects productions without backtracking, so C is too narrow. Open the solved question.
Q10. LMD, RMD and the ambiguity test
Consider the following grammar
S-> PQ
P-> aP | b
Q-> bQ | a
Consider the following statements.
S1: The grammar has different LMD and RMD for string abba.
S2: The grammar is ambiguous.
Select the correct option.
A. Both S1 and S2 are true
B. Both S1 and S2 are false
C. S1 is true but S2 is false
D. S1 is false but S2 is true
Answer: C. S1 is true but S2 is false. LMD is S ⇒ PQ ⇒ aPQ ⇒ abQ ⇒ abbQ ⇒ abba; RMD is S ⇒ PQ ⇒ PbQ ⇒ Pba ⇒ aPba ⇒ abba. Both describe the same unique parse tree, so the different expansion order does not prove ambiguity. Open the solved question.
5. Fully worked derivation count for aabbaab (Q11)
Count production applications, which are the arrows, not the number of sentential forms. Then decide separately how many parse trees generate the target.
Q11. GATE 2008
A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.
S → aS∣A
A → aAb∣bAa∣ϵ
For the string "aabbaab" how many steps are required to derive the string and how many parse trees are there?
A. 6 and 1
B. 6 and 2
C. 7 and 2
D. 4 and 2
Answer: A. 6 and 1. The derivation is S ⇒ aS ⇒ aA ⇒ aaAb ⇒ aabAab ⇒ aabbAaab ⇒ aabbaab. Seven sentential forms are joined by six arrows, so six productions were applied. Uniqueness comes out of the same trace: every A production adds one terminal on each side, so A always yields an even-length string, and a seven-symbol target therefore needs an odd number of S → aS steps. The string starts aab and not aaa, so that number is one, which leaves abbaab for A. Its leading a and trailing b admit only A → aAb, the remaining bbaa admits only A → bAa, the ba after that admits A → bAa again, and the empty remainder takes A → ϵ. No step ever had a choice, so the string has exactly one parse tree. Open the solved question.
6. Read precedence and associativity from the grammar (Q12)
Read the grammar levels, not normal arithmetic convention. Deeper non-terminals bind more tightly, while recursion direction gives associativity here.
Q12. Precedence read from grammar levels
Consider the following grammar:
E → E # X | X
X → T − X | X * T | T
T → T + F | F
F → (E) | id
Here, id stands for an identifier. The grammar is used to generate valid arithmetic expressions in a hypothetical language. Consider the following statements:
(i) # associates from left and has the least precedence.
(ii) − associates from left and has higher precedence than #.
(iii) + associates from left and has the highest precedence.
(iv) * associates from left and has the same precedence as −.
Which option is correct?
A. Only (i), (iii), and (iv) are true
B. Only (ii) and (iii) are true
C. Only (ii), (iii), and (iv) are true
D. All of the above
Answer: A. Only (i), (iii), and (iv) are true. E → E # X is left-recursive, so # is left-associative, and it sits at the outermost level, so it binds least. X → T − X is right-recursive, which makes − right-associative, so (ii) fails on associativity even though its precedence claim is right. X → X * T puts * at that same X level and left-associative, which is (iv), and T → T + F puts + one level deeper and left-associative, which is (iii). Open the solved question.
7. Score the set and choose the next drill
Answer map: Q1 B, Q2 C, Q3 A, Q4 B, Q5 A, Q6 A, Q7 A, Q8 A, Q9 A, Q10 C, Q11 A, Q12 A.
10-12 correct: Move on to FIRST and FOLLOW sets and LL(1) table questions.
7-9 correct: Redo Q4, Q7, Q9, Q10, Q11 and Q12 without looking, then work through the rest of the parser basics and top-down practice set.
0-6 correct: Rebuild the chain from tokens to parse tree, redo the leftmost against rightmost split by hand, then attempt the set again.
These are revision bands, not score predictions. The short version is this: top-down parsing grows the tree from the start symbol through a leftmost derivation, recursive descent implements that direction directly, left recursion has to be rewritten away before a top-down parser can use the grammar, and different LMD and RMD sequences alone do not prove ambiguity. Syntax analysis carries on into FIRST and FOLLOW sets, LL(1) tables and the LR family, and GATE Guidance by Sanchit Sir takes compiler design through that sequence in order.
