Compiler Design and Construction - Old Questions

7.  Define the term ‘item’, ‘closure’ and ‘goto’ used in LR parsing. Compute the SLR DFA for the following grammar.

Item

An “item” is a production rule that contains a dot(.) somewhere in the right side of the production. For example, A→ .αAβ , A→ α.Aβ, A→ αA.β, A→ αAβ. are items if there is a production A→ αAβ in the grammar.

Closure

If I is a set of items for a grammar G, then closure(I) is the set of LR(0) items constructed from I using the following rules:

 1. Initially, every item in I is added to closure(I).

 2. If A→ α.Bβ is in closure(I) and B →γ is a production, then add the item B → .γ to I if it is not already there.

Apply this rule until no more new items can be added to closure(I).

goto

If I is a set of LR(0) items and X is a grammar symbol (terminal or non-terminal), then goto(I, X) is defined as follows:

    If A → α•Xβ in I then every item in closure({A → αX•β}) will be in goto(I, X).

Now,

The augmented grammar of the given grammar is,

    S‘ → S

    S → CC

    C → aC | b

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

I₀ = closure ({S‘ → •S}) = {S‘ → •S, S → •CC, C → •aC,  C → •b}

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

goto (I₀, C) = closure ({S → C•C}) = {S → C•C, C → •aC, C→ •b} = I₂

goto (I₀, a) = closure ({C→ a•C}) = {C → a•C, C → •aC, C → •b} = I₃

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

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

goto (I₂, a) = closure ({C → a•C}) = {C → a•C, C → •aC, C → •b} = I₃

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

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

goto (I₃, a) = closure ({C → a•C}) = {C→ a•C, C → •aC, C → •b} = I₃

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

Now, the SLR DFA of the given grammar is: