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
- In the LL(1) Parsing table of the given CFG, how many valid non-blank entries will be there in the rows for variables 'B' and 'D'?
- Identify the correct statement from the following.
- What will be the FIRST(S) & FIRST(D)?
- The I0 state of the canonical LR(0) set of the SLR(1) parser of this CFG has how many productions?
- Which of the following Grammars is/are only Context Free (i.e. context-free but not regular grammars)?Grammar Productions A S → Ab aS → aA…
- Consider the following DFA over Σ = {a, b, c}. Start state q0; final states q2, q3, q4, q5. Transitions (any missing transition goes to a d…