Compiler Design and Construction - Old Questions

7.  What do you mean by kernel and non-kernel items? Compute the kernel items for LR(0) for the following grammar.

Kernel Items

The initial item S‘ → •S and all the other items those with no dot (.) at the beginning of R.H.S are called the kernel items. For example, For any production A→ αBβ

    Kernels are A→ α.Bβ, A→ αB.β, A→ αBβ.

Non-Kernel Items

All items except first item S‘ → •S with dot (.) at the beginning of R.H.S are called the non-kernel items. For example A→ .αBβ

Now,

The augmented grammar of the given grammar is,

    S‘ → S

    S → CC

    C → bC | d

Next, we obtain the canonical collection of sets of LR(0) items, as follows,

I₀ = closure ({S‘ → •S}) = {S‘ → •S, S → •CC, C → •bC,  C → •d}

goto (I₀, S) = closure ({S‘ → S•}) = {S‘ → S•} = I₁

goto (I₀, C) = closure ({S → C•C}) = {S → C•C, C → •bC, C→ •d} = I₂

goto (I₀, b) = closure ({C→ b•C}) = {C → b•C, C → •bC, C → •d} = I₃

goto (I₀, d) = closure ({C → d•}) = {C → d•} = I₄

goto (I₂, C) = closure ({S → CC•}) = {S → CC•} = I₅

goto (I₂, b) = closure ({C → b•C}) = {C → b•C, C → •bC, C → •d} = I₃

goto (I₂, d) = closure ({C → d•}) = {C → d•} = I₄

goto (I₃, C) = closure ({C → bC•}) = {C → bC•} = I₆

goto (I₃, b) = closure ({C → b•C}) = {C→ b•C, C → •bC, C → •d} = I₃

goto (I₃, d) = closure ({C → d•}) = {C → d•} = I₄

Now the Kernel items for LR(0) for the given grammar are;