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 }

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