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 }
What will be the FIRST(S) & FIRST(D)?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. FIRST (S) = { [, x }; FIRST (D) = { *, ε }
Explanation
Since S → AB and A → CD with C → [S] | x (neither alternative is ε), A can never derive ε, so FIRST(S) = FIRST(A) = FIRST(C) = {[, x} (the first symbols of C's two alternatives). For D → *CD | ε, the first alternative starts with the terminal '*' and the second is ε, so FIRST(D) = {*, ε}. Hence FIRST(S) = {[, x}, FIRST(D) = {*, ε}.More Theory of Computation and Compilers questions
- 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…
- Consider the following DFA over Σ = {a, b, c}. Start state q0, which is also the only final state. Transitions:State a b c →* q0 q1 q0 q0 q…
- Match List I with List IIList I List II A. Type 3 Grammar I. V → (V ∪ Σ)* B. Type 2 Grammar II. αVβ → α(V ∪ Σ)⁺β, where α, β ∈ (V ∪ Σ)* C.…
- Arrange the following parsers in increasing order of their power of handling grammars, i.e. from the least powerful parser to the most powe…