parsingcompiler-constructionautomatalr-grammar

How do I see that there is a conflict in the LR(0) items automata?

There is something I don't fully get about the LR(0). I'm trying to figure out when grammar is not LR(0). As I understand I build the LR(0) items automata. Then I need to look for conflict. But I don't think that I fully understand when there is a conflict between two items in the LR(0) items automata. Is it possible to clear things up about this part? When do I know is there a conflict in the LR(0) items automata? Would be helpful to see an example or two (not for the grammar itself, rather for two items that have a conflict off some kind).

For example for:

S ::= T C
T ::= char
T ::= int
C ::= [ num ] C
C ::= ''

I get:

enter image description here

Why is there a conflict between 4 and 8?

Solution

  • There is not a "conflict between 4 and 8". (That wouldn't make sense, since the parsing machine is always in exactly one state.) Each of the two states (independently) has a conflict.

    LR(0) parsers cannot use lookahead to predict the action, so every state must either have:

    1. A shift transition for every input, or
    2. The same reduction action for every input

    That means that if there is a single item in the state's itemset with the • at the end (i.e. a reducible item), then it must be the only item in the itemset. Any other item would either be a shift or a different reduction. And that's not the case for states 4 and 8 in your machine; both of them have the item C ::= •, along with other items not ending with •.