13

I currently am studying about compilers and as I understand in LR(0) there are cases where we have "shift/reduce" or "reduce/reduce" conflicts, but it's impossible to have "shift/shift" conflicts! Why we can't have a "shift/shift" conflict?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
user1888149
  • 143
  • 1
  • 4
  • 2
    There are reduce-reduce conflicts because their are 2 productions that can be chosen to reduce the handle. There are shift-reduce conflicts because you can both shift and reduce with some production and apparently still take the parsing forward. Shift just means 1 thing, you advance the input stream, so there cannot be a shift-shift conflict. – axiom Dec 08 '12 at 18:10

1 Answers1

24

Shift/reduce conflicts occur when the parser can't tell whether to shift (push the next input token atop the parsing stack) or reduce (pop a series of terminals and nonterminals from the parsing stack). A reduce/reduce conflict is when the parser knows to reduce, but can't tell which reduction to perform.

If you were to have a shift/shift conflict, the parser would know that it needed to push the next token onto its parsing stack, but wouldn't know how to do it. Since there is only one way to push the token onto the parsing stack, there generally cannot be any conflicts of this form.

That said, it's theoretically possible for a shift/shift conflict to exist if you had a strange setup in which there were two or more transitions leading out of a given parsing state that were labeled with the same terminal symbol. The conflict in that case would be whether to shift and go to one state or shift and go to another. This could happen if you tried to compress an automaton into fewer states and did so incorrectly, or if you were trying to build a nondeterministic parsing automaton. In practice, this would never happen.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • FIRST-FIRST conflicts in LL parser are eliminated by left factoring and I also read that left factoring is used to eliminate non determinism. So is FIRST-FIRST conflict manifestation of non determinism of grammar. Also is Shift-Shift conflict (if we assume it exists) is similar to FF conflict. Similarly I read enforcing association and/or precedence eliminates SR and RR conflicts and also eliminates ambiguity of grammar. So is SR and RR conflicts manifestation of ambiguousness of grammar? – MsA Jun 12 '19 at 06:09
  • A grammar can be both deterministic and left-factorable - the two aren’t mutually exclusive. (Did you mean “ambiguous” rather than “deterministic,” by the way?) Not all FIRST/FIRST conflicts can be eliminated via left-factoring, since some languages aren’t LL(1) and therefore don’t have any LL(1) grammars. Because LL and LR parsers work in fundamentally different ways, I don’t think it’s easy to draw a parallel between FIRST/FIRST conflicts and shift/shift or shift/reduce conflicts; these happen for very different reasons. – templatetypedef Jun 12 '19 at 16:50
  • While every ambiguous grammar will result in shift/reduce or reduce/reduce conflicts, the converse isn’t true. You can have an unambiguous grammar that still leads to these conflicts, since not all context-free languages have LR grammars. – templatetypedef Jun 12 '19 at 16:51