1
$\begingroup$

I'm studying LR(0) parser. But I don't understand how sets of items corresponding to states can be calculated. I think The author would miss some information readers must know. Given the following LR(0) automaton, How the set of items corresponding to I1, I2, I3, ... , and I11 can be calculated?

enter image description here

In addition, is closure of item sets related to with calculating them? If so, what exactly every item in I1, I2, ... , and I11 is?

enter image description here

$\endgroup$
1
$\begingroup$

An item is a rule with dot marker in it. Think of the dot marker as what you've seen so far and what you are hoping to see in the future. Itemsets are sets of items. In the diagram above they are the boxes with all the items (nodes in the graph). The kernel (or core) of an itemset are the rules that are in white. Those items are given to us (rule 1) in CLOSURE from a different part of the table building algorithm. Taking closure of all the kernel items gives you the full itemset and includes non-kernel items (the darker ones in your diagram). The CLOSURE(I) operation is this expansion algorithm.

Take I7 for example. We start with only one kernel item.

T -> T * . F

Step 2 of CLOSURE is saying that since F is in front of the dot we have to expand it, adding those items to the itemset. Hence, we add items the following items.

F -> . ( E )
F -> . id

This is everything that F can expand to. So the full itemset is now:

T -> T * . F
F -> . ( E )
F -> . id

We reapply rule (2), but see that the . is not in front of any new non-terminals that we haven't expanded, we are done. The itemset is now closed.

The other half of the parse table building algorithm generates new itemsets. This involves moving the dot across each symbol of each item. For example, moving the dot over the 'F' gives you the itemset with the kernel item below.

T- > T * F .

This is I10 in your diagram. Note, that edges from I7 to I10 is labeled F (since the dot crossed that symbol). You'd reapply the same closure algorithm here and loop this process.

See the Wikipedia entry on this for more information.

$\endgroup$
  • $\begingroup$ How can you know that the kernel item T -> T * . F corresponds to I7? On what ground? $\endgroup$ – inherithandle May 21 '14 at 3:05
  • $\begingroup$ Your diagram labels it that way. It's just a label in the graph. $\endgroup$ – Tim May 21 '14 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.