All mock tests are FREE till 31 December — register to save your progress

Consider the following Context Free Grammar (G):

S → A B
B → + A B | ε
A → C D
D → * C D | ε
C → [ S ] | x

Variable = { S, A, B, C, D }

Terminals = { +, *, [, ], x }

Find the Follow (A) & Follow (C).

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. Follow (A) = { +, ], $ }; Follow (C) = { *, +, ], $ }

Explanation

Since S is the start symbol, $ ∈ FOLLOW(S), and S also occurs inside C → [S] followed by ']', so FOLLOW(S) = FOLLOW(B) = { ], $ } (B inherits FOLLOW(S) because S → AB and B is nullable). In S → AB and B → +AB, A is followed by FIRST(B)\{ε} = {+} and, since B is nullable, also by FOLLOW(S) and FOLLOW(B), giving FOLLOW(A) = {+, ], $}. In A → CD and D → *CD, C is followed by FIRST(D)\{ε} = {*} and, since D is nullable, also by FOLLOW(A) and FOLLOW(D) (= FOLLOW(A)), giving FOLLOW(C) = {*, +, ], $}. So FOLLOW(A) = {+, ], $}, FOLLOW(C) = {*, +, ], $}.

More Theory of Computation and Compilers questions