Canonical collection of LR(0) items -2
Closure Function of LR(0)
Let G be the grammar and I be the set of items of it then closure (I) is defined as the set of items constructed from I as follows.
- Initially, closure (I) contains the item in I.
- If closure (I) contains an item A →α• β ץ and there is a production B then item B → ץ is added to I if it does not exist already.
- Repeat step 2 until there are no new items that can be added to the closure
If α β1 is a viable prefix then X → β1, β2 forms a valid item for αβ1. However, an item can be viable for the number of viable prefixes.
Now, with a valid item for a viable prefix, it is easy to decide whether to perform the shift or reduce action which is as follows,
- If β2 ≠ ∊, then it represents that handle is not shifted onto the stack and thus shift action has to be performed.
- If β2 = ∊, then it represents X → β1as the handle and thus reduce action has to be performed.
Thus, for a single viable, prefix there is a possibility of two valid items directing to perform different actions thereby leading to conflicts. However, these conflicts are solvable by cooking at the next input symbol or by other methods.
Reference Link