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 }
The I0 state of the canonical LR(0) set of the SLR(1) parser of this CFG has how many productions?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. 5
Explanation
Augmenting the grammar with S' → S, the initial item set I0 is the closure of {S' → .S}. Since S follows the dot, add S → .AB; since A follows the dot there, add A → .CD; since C follows the dot there, add C → .[S] and C → .x. Closure stops here because each newly added item has the dot immediately before a terminal ('[' or 'x'), with no further nonterminal to expand. This gives 5 items: S' → .S, S → .AB, A → .CD, C → .[S], C → .x, so I0 has 5 productions.More Theory of Computation and Compilers questions
- 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…
- What are the various LEADERS (leading statements) for the TAC given in the passage?