Consider the following grammar.S -> S * ES -> EE -> F + EE...
Let's make the LR(0) set of items. First we need to augment the grammar with the production rule S' -> .S , then we need to find closure of items in a set to complete a set. Below are the LR(0) sets of items.
View all questions of this test
Consider the following grammar.S -> S * ES -> EE -> F + EE...
Explanation:
In order to determine which two items will appear in the same set in the canonical sets-of-items for the given grammar, we need to construct the canonical LR(0) sets of items.
Canonical LR(0) Sets of Items:
The canonical sets-of-items can be constructed using the LR(0) item closure and LR(0) item goto operations. Let's start by constructing the initial set of items.
Initial Set of Items:
The initial set of items consists of the closure of the augmented production S' -> .S.
I0 = Closure({S' -> .S})
The closure operation expands the items by adding additional items based on the productions and the position of the dot. In this case, since the dot is at the beginning of the production, we need to add the productions where the dot is moved one position to the right.
Closure(I0) = {S' -> .S, S -> .S*E, S -> .E, E -> .F, E -> .EQG, F -> .id}
Constructing the Canonical Sets of Items:
Now, we can construct the canonical sets of items by applying the LR(0) item goto operation.
For each item in the current set, we find the non-terminal or terminal symbol immediately to the right of the dot. We then create a new set of items by moving the dot one position to the right for all items that have the same symbol to the right of the dot.
Let's go through the construction of the canonical sets of items:
Set I0:
- S' -> .S
- S -> .S*E
- S -> .E
- E -> .F
- E -> .EQG
- F -> .id
Set I1: (Goto(I0, S))
- S' -> S.
- S -> S.*E
Set I2: (Goto(I0, E))
- E -> .F
- E -> .EQG
Set I3: (Goto(I2, F))
- E -> F.
Set I4: (Goto(I2, Q))
- E -> EQ.G
Set I5: (Goto(I4, G))
- E -> EQG.
Set I6: (Goto(I0, id))
- F -> id.
Set I7: (Goto(I2, id))
- E -> F.id
Set I8: (Goto(I4, id))
- E -> EQG.id
Set I9: (Goto(I2, Q))
- E -> EQ.G
Set I10: (Goto(I0, S*))
- S -> S*.E
Set I11: (Goto(I10, E))
- S -> S*E.
Set I12: (Goto(I2, EQ))
- E -> EQ.G
Set I13: (Goto(I12, G))
- E -> EQG.
Set I14: (Goto(I12, id))
- E -> EQG.id