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 }
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'?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. B = 3 entries; D = 4 entries
Explanation
In an LL(1) table, a production X → α adds one entry per terminal in FIRST(α), and if α is nullable, X → ε also adds one entry per terminal in FOLLOW(X). For B → +AB | ε: the +AB alternative gives an entry at '+', and the ε alternative gives entries at FOLLOW(B) = {], $}, for 1 + 2 = 3 entries in row B. For D → *CD | ε: the *CD alternative gives an entry at '*', and the ε alternative gives entries at FOLLOW(D) = FOLLOW(A) = {+, ], $}, for 1 + 3 = 4 entries in row D.More Theory of Computation and Compilers questions
- 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…
- 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…