|
An LR(0) item is a production of the grammar with exactly one dot on the right-hand side. For example, production T → T * F leads to four LR(0) items:
| T → ⋅ T * F |
| T → T ⋅ * F |
| T → T * ⋅ F |
| T → T * F ⋅ |
What is to the left of the dot has just been read, and the parser is ready to read the remainder, after the dot.
Two LR(0) items that come from the same production but have the dot in different places are considered different LR(0) items.
Suppose that S is a set of LR(0) items. The following rules tell how to build closure(S), the closure of S. You must add LR(0) items to S until there are no more to add.
All members of S are in the closure(S).
Suppose closure(S) contains item A → α⋅Bβ, where B is a nonterminal. Find all productions B → γ1, …, B → γn with B on the left-hand side. Add LR(0) items B → ⋅γ1, … B → ⋅γn to closure(S).
For example, let's take the closure of set {E → E + ⋅ T}.
Since there is an item with a dot immediately before nonterminal T, we add T → ⋅ F and T → ⋅ T * F.
The set now contains the following LR(0) items.
| E → E + ⋅ T |
| T → ⋅ F |
| T → ⋅ T * F |
Now there is an item in the set with a dot immediately followed by F. So we add items F → ⋅ n and F → ⋅ ( E ).
The set now contains the following items.
| E → E + ⋅ T |
| T → ⋅ F |
| T → ⋅ T * F |
| F → ⋅ n |
| F → ⋅ ( E ) |
No more LR(0) items need to be added, so the closure is finished.
What is the point of the closure? LR(0) item E → E + ⋅ T indicates that the parser has just finished reading an expression followed by a + sign. In fact, E + are the top two symbols on the stack.
Now, the parser is looking to see if there is a T next. (It does not predict that there is a T next. It is just considering that as a possibility.)
But that means it should be looking for something that is the right-hand side of a production for T. So we add items for T with the dot at the beginning.
|