Compiler Design and Construction - Old Questions

5.  Construct LR(1) parse table for

The augmented grammar of given grammar is:

S' → S

S → XX

X → pX | q

Now, Canonical LR(1) item sets are:

I₀ = closure([S' →•S, $]) = {[S' →•S, $], [S →•XX, $], [X → •pX, p/q], [X → •q, p/q]}

goto (I₀, S) = closure([S' →•S, $]) = {[S'→ S•, $]} = I₁

goto(I₀, X) = closure([S → X•X, $] = {[S→X•X, $], [X→•pX, $], [X→•q, $]} = I₂

goto(I₀, p) = closure([X →p•X, p/q]) = {[X →p•X, p/q], [X →•pX, p/q], [X →•q, p/q]} = I₃

goto(I₀, q) = closure([X→q•, p/q]) = {[X→q•, p/q]} = I₄

goto(I₂, X) = closure ([S→XX•, $]) = {[S → XX •, $]} = I₅

goto(I₂, p) = closure([X→p•X, $]) = {[X → p•X, $], [X → • pX, $], [X → • q, $]} = I₆

goto (I₂, q) = closure ([X → q•, $]) = {[X → q•, $]} = I₇

goto (I₃, X) = closure ([X → pX•, p/q]) = {[X → pX•, p/q]} = I₈

goto(I₃, p) = closure([X →p•X, p/q]) =  I₃

goto(I₃, q) = closure([X→q•, p/q]) = I₄

goto(I₆, X) = closure([X → pX•, $]) = {[X →pX•, $]} = I₉

goto (I₆, p) = closure([X→p•X, $]) = I₆

goto(I₆, q) =  closure ([X → q•, $] =  I₇

Now, the LR(1) parsing table is,

1. S → XX

2. X → pX

3. X → q