[Solved]: LR(0) parsing: how can I know sets of items corresponding to states?

Problem Detail: 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

Asked By : inherithandle

Answered By : Tim

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 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/25924  Ask a Question  Download Related Notes/Documents