Menu
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?
400
In shift-reduce parsing, there is two types of conflicts: one is shift-reduce conflict (SR conflict) and another is reduce – reduce conflict (RR) conflict.
There are two kinds of conflicts that can occur in an SLR(1) parsing table. A shift-reduce conflict occurs in a state that requests both a shift action and a reduce action. A reduce-reduce conflict occurs in a state that requests two or more different reduce actions.
Rule 1. If there is a shift-reduce conflict in situations where no precedence rules have been created to resolve the conflict, the default action is to shift. The conflict is also reported in the yacc output so you can check that shifting is actually what you want.
The Shift-Reduce Conflict is the most common type of conflict found in grammars. It is caused when the grammar allows a rule to be reduced for particular token, but, at the same time, allowing another rule to be shifted for that same token.
Shift Reduce Parser is a type of Bottom-Up Parser. It generates the Parse Tree from Leaves to the Root. In Shift Reduce Parser, the input string will be reduced to the starting symbol. This reduction can be produced by handling the rightmost derivation in reverse, i.e., from starting symbol to the input string.
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!
60
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
