PYQs / GATE CS / 2021 / Set 1 / Q41 GATE CS 2021 Set 1 — Question 41 Go beyond PYQs with Success Tracker AI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply. MCQ +2 / -0.67 Medium First & Follow Sets Syntax Analysis Compiler Design LL(1) Parsing
Compiler Design → Syntax Analysis → First & Follow Sets
Last updated 5 September 2026
Question Consider the following context-free grammar where the set of terminals is
{ a , b , c , d , f } \{a, b, c, d, f\} { a , b , c , d , f } .
S → d a T ∣ R f S \rightarrow d a T \mid R f S → d a T ∣ R f T → a S ∣ b a T ∣ ϵ T \rightarrow a S \mid b a T \mid \epsilon T → a S ∣ ba T ∣ ϵ R → c a T R ∣ ϵ R \rightarrow c a T R \mid \epsilon R → c a T R ∣ ϵ The following is a partially-filled LL(1) parsing table.
a a a b b b c c c d d d f f f $ \$ $ S (1) S → d a T S \rightarrow d a T S → d a T (2) T T → a S T \rightarrow a S T → a S T → b a T T \rightarrow b a T T → ba T (3) T → ϵ T \rightarrow \epsilon T → ϵ (4) R R → c a T R R \rightarrow c a T R R → c a T R R → ϵ R \rightarrow \epsilon R → ϵ
Which one of the following choices represents the correct combination for the numbered cells in the parsing table ("blank" denotes that the corresponding cell is empty)?
Correct answer (A) (1) S arrow R f (2) S arrow R f (3) T arrow ε (4) T arrow ε
Solution To determine the entries in the LL(1) parsing table, we first compute the FIRST and FOLLOW sets for the non-terminals.
Grammar:
1. S → d a T S \rightarrow d a T S → d a T 2. S → R f S \rightarrow R f S → R f 3. T → a S T \rightarrow a S T → a S 4. T → b a T T \rightarrow b a T T → ba T 5. T → ϵ T \rightarrow \epsilon T → ϵ 6. R → c a T R R \rightarrow c a T R R → c a T R 7. R → ϵ R \rightarrow \epsilon R → ϵ
Step 1: Compute FIRST sets
F I R S T ( R ) = { c , ϵ } FIRST(R) = \{c, \epsilon\} F I R S T ( R ) = { c , ϵ } F I R S T ( T ) = { a , b , ϵ } FIRST(T) = \{a, b, \epsilon\} F I R S T ( T ) = { a , b , ϵ } F I R S T ( S ) = F I R S T ( d a T ) ∪ F I R S T ( R f ) FIRST(S) = FIRST(d a T) \cup FIRST(R f) F I R S T ( S ) = F I R S T ( d a T ) ∪ F I R S T ( R f ) F I R S T ( d a T ) = { d } FIRST(d a T) = \{d\} F I R S T ( d a T ) = { d } F I R S T ( R f ) = ( F I R S T ( R ) − { ϵ } ) ∪ F I R S T ( f ) = { c } ∪ { f } = { c , f } FIRST(R f) = (FIRST(R) - \{\epsilon\}) \cup FIRST(f) = \{c\} \cup \{f\} = \{c, f\} F I R S T ( R f ) = ( F I R S T ( R ) − { ϵ }) ∪ F I R S T ( f ) = { c } ∪ { f } = { c , f } So, F I R S T ( S ) = { d , c , f } FIRST(S) = \{d, c, f\} F I R S T ( S ) = { d , c , f }
Step 2: Compute FOLLOW sets
F O L L O W ( S ) FOLLOW(S) F O LL O W ( S ) $ \$ $ From T → a S T \rightarrow a S T → a S F O L L O W ( S ) ⊇ F O L L O W ( T ) FOLLOW(S) \supseteq FOLLOW(T) F O LL O W ( S ) ⊇ F O LL O W ( T ) From S → d a T S \rightarrow d a T S → d a T F O L L O W ( T ) ⊇ F O L L O W ( S ) FOLLOW(T) \supseteq FOLLOW(S) F O LL O W ( T ) ⊇ F O LL O W ( S ) From T → b a T T \rightarrow b a T T → ba T F O L L O W ( T ) ⊇ F O L L O W ( T ) FOLLOW(T) \supseteq FOLLOW(T) F O LL O W ( T ) ⊇ F O LL O W ( T ) From R → c a T R R \rightarrow c a T R R → c a T R F O L L O W ( T ) ⊇ F I R S T ( R ) FOLLOW(T) \supseteq FIRST(R) F O LL O W ( T ) ⊇ F I R S T ( R ) ϵ ∈ F I R S T ( R ) \epsilon \in FIRST(R) ϵ ∈ F I R S T ( R ) F O L L O W ( T ) ⊇ F O L L O W ( R ) FOLLOW(T) \supseteq FOLLOW(R) F O LL O W ( T ) ⊇ F O LL O W ( R ) From S → R f S \rightarrow R f S → R f F O L L O W ( R ) ⊇ F I R S T ( f ) = { f } FOLLOW(R) \supseteq FIRST(f) = \{f\} F O LL O W ( R ) ⊇ F I R S T ( f ) = { f } From R → c a T R R \rightarrow c a T R R → c a T R F O L L O W ( R ) ⊇ F O L L O W ( R ) FOLLOW(R) \supseteq FOLLOW(R) F O LL O W ( R ) ⊇ F O LL O W ( R )
Solving these constraints:
F O L L O W ( R ) = { f } FOLLOW(R) = \{f\} F O LL O W ( R ) = { f } F O L L O W ( T ) ⊇ F I R S T ( R ) ∖ { ϵ } ∪ F O L L O W ( R ) = { c , f } FOLLOW(T) \supseteq FIRST(R) \setminus \{\epsilon\} \cup FOLLOW(R) = \{c, f\} F O LL O W ( T ) ⊇ F I R S T ( R ) ∖ { ϵ } ∪ F O LL O W ( R ) = { c , f } F O L L O W ( T ) ⊇ F O L L O W ( S ) FOLLOW(T) \supseteq FOLLOW(S) F O LL O W ( T ) ⊇ F O LL O W ( S ) F O L L O W ( S ) ⊇ { $ } ∪ F O L L O W ( T ) FOLLOW(S) \supseteq \{\$\} \cup FOLLOW(T) F O LL O W ( S ) ⊇ { $ } ∪ F O LL O W ( T ) Thus, F O L L O W ( S ) = F O L L O W ( T ) = { c , f , $ } FOLLOW(S) = FOLLOW(T) = \{c, f, \$\} F O LL O W ( S ) = F O LL O W ( T ) = { c , f , $ }
Step 3: Fill the Table Entries
Cell (1): M [ S , c ] M[S, c] M [ S , c ] Look at S → R f S \rightarrow R f S → R f c ∈ F I R S T ( R f ) c \in FIRST(R f) c ∈ F I R S T ( R f ) S → R f S \rightarrow R f S → R f Cell (2): M [ S , f ] M[S, f] M [ S , f ] Look at S → R f S \rightarrow R f S → R f f ∈ F I R S T ( R f ) f \in FIRST(R f) f ∈ F I R S T ( R f ) S → R f S \rightarrow R f S → R f Cell (3): M [ T , c ] M[T, c] M [ T , c ] Look at T → ϵ T \rightarrow \epsilon T → ϵ c ∈ F O L L O W ( T ) c \in FOLLOW(T) c ∈ F O LL O W ( T ) T → ϵ T \rightarrow \epsilon T → ϵ Cell (4): M [ T , $ ] M[T, \$] M [ T , $ ] Look at T → ϵ T \rightarrow \epsilon T → ϵ $ ∈ F O L L O W ( T ) \$ \in FOLLOW(T) $ ∈ F O LL O W ( T ) T → ϵ T \rightarrow \epsilon T → ϵ
Conclusion:
(1) S → R f S \rightarrow R f S → R f (2) S → R f S \rightarrow R f S → R f (3) T → ϵ T \rightarrow \epsilon T → ϵ (4) T → ϵ T \rightarrow \epsilon T → ϵ
This corresponds to Option (A).
Turn this into a strength. Explore AI-powered practice and doubt support with Success Tracker. Review answer and solution without JavaScript Interactive answer checking needs JavaScript. The published solution is available below.
Correct answer (A) (1) S arrow R f (2) S arrow R f (3) T arrow ε (4) T arrow ε
Solution To determine the entries in the LL(1) parsing table, we first compute the FIRST and FOLLOW sets for the non-terminals.
Grammar:
1. S → d a T S \rightarrow d a T S → d a T 2. S → R f S \rightarrow R f S → R f 3. T → a S T \rightarrow a S T → a S 4. T → b a T T \rightarrow b a T T → ba T 5. T → ϵ T \rightarrow \epsilon T → ϵ 6. R → c a T R R \rightarrow c a T R R → c a T R 7. R → ϵ R \rightarrow \epsilon R → ϵ
Step 1: Compute FIRST sets
F I R S T ( R ) = { c , ϵ } FIRST(R) = \{c, \epsilon\} F I R S T ( R ) = { c , ϵ } F I R S T ( T ) = { a , b , ϵ } FIRST(T) = \{a, b, \epsilon\} F I R S T ( T ) = { a , b , ϵ } F I R S T ( S ) = F I R S T ( d a T ) ∪ F I R S T ( R f ) FIRST(S) = FIRST(d a T) \cup FIRST(R f) F I R S T ( S ) = F I R S T ( d a T ) ∪ F I R S T ( R f ) F I R S T ( d a T ) = { d } FIRST(d a T) = \{d\} F I R S T ( d a T ) = { d } F I R S T ( R f ) = ( F I R S T ( R ) − { ϵ } ) ∪ F I R S T ( f ) = { c } ∪ { f } = { c , f } FIRST(R f) = (FIRST(R) - \{\epsilon\}) \cup FIRST(f) = \{c\} \cup \{f\} = \{c, f\} F I R S T ( R f ) = ( F I R S T ( R ) − { ϵ }) ∪ F I R S T ( f ) = { c } ∪ { f } = { c , f } So, F I R S T ( S ) = { d , c , f } FIRST(S) = \{d, c, f\} F I R S T ( S ) = { d , c , f }
Step 2: Compute FOLLOW sets
F O L L O W ( S ) FOLLOW(S) F O LL O W ( S ) $ \$ $ From T → a S T \rightarrow a S T → a S F O L L O W ( S ) ⊇ F O L L O W ( T ) FOLLOW(S) \supseteq FOLLOW(T) F O LL O W ( S ) ⊇ F O LL O W ( T ) From S → d a T S \rightarrow d a T S → d a T F O L L O W ( T ) ⊇ F O L L O W ( S ) FOLLOW(T) \supseteq FOLLOW(S) F O LL O W ( T ) ⊇ F O LL O W ( S ) From T → b a T T \rightarrow b a T T → ba T F O L L O W ( T ) ⊇ F O L L O W ( T ) FOLLOW(T) \supseteq FOLLOW(T) F O LL O W ( T ) ⊇ F O LL O W ( T ) From R → c a T R R \rightarrow c a T R R → c a T R F O L L O W ( T ) ⊇ F I R S T ( R ) FOLLOW(T) \supseteq FIRST(R) F O LL O W ( T ) ⊇ F I R S T ( R ) ϵ ∈ F I R S T ( R ) \epsilon \in FIRST(R) ϵ ∈ F I R S T ( R ) F O L L O W ( T ) ⊇ F O L L O W ( R ) FOLLOW(T) \supseteq FOLLOW(R) F O LL O W ( T ) ⊇ F O LL O W ( R ) From S → R f S \rightarrow R f S → R f F O L L O W ( R ) ⊇ F I R S T ( f ) = { f } FOLLOW(R) \supseteq FIRST(f) = \{f\} F O LL O W ( R ) ⊇ F I R S T ( f ) = { f } From R → c a T R R \rightarrow c a T R R → c a T R F O L L O W ( R ) ⊇ F O L L O W ( R ) FOLLOW(R) \supseteq FOLLOW(R) F O LL O W ( R ) ⊇ F O LL O W ( R )
Solving these constraints:
F O L L O W ( R ) = { f } FOLLOW(R) = \{f\} F O LL O W ( R ) = { f } F O L L O W ( T ) ⊇ F I R S T ( R ) ∖ { ϵ } ∪ F O L L O W ( R ) = { c , f } FOLLOW(T) \supseteq FIRST(R) \setminus \{\epsilon\} \cup FOLLOW(R) = \{c, f\} F O LL O W ( T ) ⊇ F I R S T ( R ) ∖ { ϵ } ∪ F O LL O W ( R ) = { c , f } F O L L O W ( T ) ⊇ F O L L O W ( S ) FOLLOW(T) \supseteq FOLLOW(S) F O LL O W ( T ) ⊇ F O LL O W ( S ) F O L L O W ( S ) ⊇ { $ } ∪ F O L L O W ( T ) FOLLOW(S) \supseteq \{\$\} \cup FOLLOW(T) F O LL O W ( S ) ⊇ { $ } ∪ F O LL O W ( T ) Thus, F O L L O W ( S ) = F O L L O W ( T ) = { c , f , $ } FOLLOW(S) = FOLLOW(T) = \{c, f, \$\} F O LL O W ( S ) = F O LL O W ( T ) = { c , f , $ }
Step 3: Fill the Table Entries
Cell (1): M [ S , c ] M[S, c] M [ S , c ] Look at S → R f S \rightarrow R f S → R f c ∈ F I R S T ( R f ) c \in FIRST(R f) c ∈ F I R S T ( R f ) S → R f S \rightarrow R f S → R f Cell (2): M [ S , f ] M[S, f] M [ S , f ] Look at S → R f S \rightarrow R f S → R f f ∈ F I R S T ( R f ) f \in FIRST(R f) f ∈ F I R S T ( R f ) S → R f S \rightarrow R f S → R f Cell (3): M [ T , c ] M[T, c] M [ T , c ] Look at T → ϵ T \rightarrow \epsilon T → ϵ c ∈ F O L L O W ( T ) c \in FOLLOW(T) c ∈ F O LL O W ( T ) T → ϵ T \rightarrow \epsilon T → ϵ Cell (4): M [ T , $ ] M[T, \$] M [ T , $ ] Look at T → ϵ T \rightarrow \epsilon T → ϵ $ ∈ F O L L O W ( T ) \$ \in FOLLOW(T) $ ∈ F O LL O W ( T ) T → ϵ T \rightarrow \epsilon T → ϵ
Conclusion:
(1) S → R f S \rightarrow R f S → R f (2) S → R f S \rightarrow R f S → R f (3) T → ϵ T \rightarrow \epsilon T → ϵ (4) T → ϵ T \rightarrow \epsilon T → ϵ
This corresponds to Option (A).
Understand the concept, then try another question Revisit Compiler Design with concept notes, common mistakes and an original worked example before your next attempt.
More questions on Syntax Analysis ← Q40 Full paper Q42 → 