High yield ●●●

🌳 Grammars, Derivations & FIRST/FOLLOW

Why it matters: Foundation of all parsing questions: ambiguity, derivations and especially FIRST/FOLLOW sets.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 4 done.

Formulas

FIRST(X) for a terminal
FIRST(a) = {a}
FIRST rule
A → Y1 Y2 … Yk: add FIRST(Y1)−ε; if Y1 nullable add FIRST(Y2)−ε, and so on; add ε if all nullable
FOLLOW rule 1
FOLLOW(S) ∋ $
FOLLOW rule 2
A → α B β: FOLLOW(B) ⊇ FIRST(β) − ε
FOLLOW rule 3
A → α B or A → α B β with ε ∈ FIRST(β): FOLLOW(B) ⊇ FOLLOW(A)
FOLLOW never contains ε
FOLLOW sets contain terminals and $ only

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Compute FIRST / FOLLOW sets
Given a grammar with ε-productions, write or count elements of FIRST/FOLLOW of a non-terminal.
★★★
Is the grammar ambiguous?
Find a string with two parse trees, or pick the unambiguous grammar generating the same language.
★★★
Derivation / parse tree questions
Number of nodes/steps, which derivation a parser produces, height of the tree.
★★★
Associativity and precedence from a grammar
Read off the operator behaviour from where the recursion is.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

8 real questions from the official GATE CSE papers (2012 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

8 questions · 0 correct of 0 attempted · marks 0 / 12

Year:
GATE 2025 CS1 · Q46MSQ2 marks
Which of the following statement(s) is/are TRUE while computing First and Follow during top down parsing by a compiler?

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS1 · Q33NAT1 mark
Consider the operator precedence and associativity rules for the integer arithmetic operators given below. +: highest precedence, left associative; −: high, right associative; ∗: medium, right associative; /: low, right associative. The value of the expression 3 + 1 + 5 ∗ 2 / 7 + 2 − 4 − 7 − 6 / 2 as per the above rules is ______.
GATE 2019 Set 2 · Q19NAT1 mark
Consider the grammar:
S → Aa
A → BD
B → b | ε
D → d | ε
Let a, b, d and $ be indexed as follows: a = 3, b = 2, d = 1, $ = 0. Compute the FOLLOW set of the non-terminal B and write the index values for the symbols in the FOLLOW set in the descending order. (For example, if the FOLLOW set is {a, b, d, $}, the answer should be 3210.) Answer: ______.
GATE 2018 · Q38MCQ2 marks
Consider the following parse tree for the expression a#b$c$d#e#f, involving two binary operators $ and #. (Tree: the root is #, with left child a and right child #. That # has left child $ and right child #(e, f). That $ has left child $(b, c) and right child d.) Which one of the following is correct for the given parse tree?
GATE 2017 Set 1 · Q10MCQ1 mark
Consider the following context-free grammar over the alphabet Σ = {a, b, c} with S as the start symbol:
S → abScT | abcT
T → bT | b
Which one of the following represents the language generated by the above grammar?
GATE 2017 Set 1 · Q17MCQ1 mark
Consider the following grammar:
P → x Q R S
Q → y z | z
R → w | ε
S → y
What is FOLLOW(Q)?
GATE 2016 Set 1 · Q45NAT2 marks
The attributes of three arithmetic operators in some programming language are given below. + : precedence High, associativity Left, arity Binary. − : precedence Medium, associativity Right, arity Binary. * : precedence Low, associativity Left, arity Binary. The value of the expression 2 − 5 + 1 − 7 * 3 in this language is ______.
GATE 2012 Code A · Q52MCQ2 marks
For the grammar below, a partial LL(1) parsing table is also presented (entries E1, E2, E3 are to be filled). ε is the empty string, $ indicates end of input
S → a A b B | b A a B | ε
A → S
B → S
Table: M[S,$] = S → ε; M[A,a] = A → S; M[A,b] = A → S; M[A,$] = error; M[B,a] = B → S; M[B,b] = B → S; E1 = M[S,a]; E2 = M[S,b]; E3 = M[B,$]. The FIRST and FOLLOW sets for the non-terminals A and B are

Common traps

FOLLOW(A) must also include FOLLOW of the left side when A ends a production.
ε is never put into FOLLOW.
Both left- and right-recursion for the same operator makes the grammar ambiguous.