Compiler Design and Construction - Old Questions

5.  Construct the grammar:

Compute the complete LR(0) collection of item set from above grammar.

The augmented grammar of given grammar is;

    E’→E

    E→E+T | T

    T→T*F | F

    F→ (E) | id

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

I₀ = closure ({E‘ → •E})

    = {E‘ → •E, E → •E + T, E → •T, T → •T * F, T → •F, F → • (E), F → •id}

goto(I₀, E) = closure({E‘ → E•, E → E •+ T}) = {E‘ → E•, E → E •+ T} = I₁

goto(I₀, T) = closure({E → T•, T → T •* F}) = { E → T•, T → T •* F } = I₂

goto(I₀, F) = closure({T → F•}) = {T → F•} = I₃

goto(I₀, ( ) = closure({F → (•E)}) = {F → (•E), E → •E + T, E → •T, T → •T * F, T → •F, F → • (E), F → •id} = I₄

goto(I₀, id ) = closure({F → id•}) = {F → id•} = I₅

goto(I₁, + ) = closure({E → E + •T}) = {E → E +• T, T → •T * F, T → •F, F → • (E), F → •id} = I₆

goto(I₂, * ) = closure({T → T * •F}) = {T → T * •F, F → • (E), F → •id} = I₇

goto(I₄, E) = closure({F → (E•), E → E•+ T}) = {F → (E•), E → E•+ T } = I₈

goto(I₄, T) = closure({E → T•, T → T• * F}) = {E → T• , T → T•*F}= I₂

goto(I₄, F) = closure({T → F•}) = {T → F•} = I₃

goto(I₄, () = closure({F → •(E)} = I₄

goto(I₄, id) = closure({F → id•}) = I₅

goto(I₆, T) = closure({E → E +T•, T → T•* F}) = {E → E +T•, T → T•* F} = I₉

goto(I₆, F) = closure ({T→ F•}) = I₃

goto (I₆, () = closure ({F → (• E)} = I₄

goto(I₆, id) = closure({F → id•}) = I₅

goto(I₇, F ) = closure({T → T * F•})= {T → T * F•} = I₁₀

goto( I₇, () = closure({F → •(E)} = I₄

goto(I₇, id) = closure({F → id•}) = I₅

goto(I₈, ) ) = closure({F → (E) •}) = {F → (E) •} = I₁₁

goto(I₈, +) = closure({ E → E+•T} ) = I₆

goto(I₉, *) = closure({T → T*•F}) = { T → T*•F, F→ •(E), F→ •id } = I₇

Now,

The canonical collection of set of LR(0) items for given grammar are: