CODEWITHSUNDEEP
parsinglr-grammarshift-reduce-conflictreduce-reduce-conflict
Iakob Fokas
Iakob Fokas

Reputation: 303

Resolving reduce/reduce conflicts

We have a CFG grammar and we construct LR(1) Parsing Table. We see that one cell on the parsing table have a reduce - reduce conflict. Is it possible to solve this conflict by using more input symbols of lookahead at each step? I am asking this beacuse I think that by increasing lookahead symbols, we can(not always) only resolve shift - reduce conflicts.I mean the extra lookaheads in a reduce-reduce conflict doesn't help us. Am I right ?

Upvotes: 4

Views: 8042

Answers (2)

Kirill Kobelev
Kirill Kobelev

Reputation: 10557

In general any conflict can be resolved by additional look ahead. In the extreme case you need to read to the end of the file. There is no significant difference between shift/reduce and reduce/reduce conflicts. Their resolution is kind of similar.

I wrote an article about conflict resolution. It proposes a method that allows finding out the reason of the conflict. In certain cases this helps to do refactoring of the grammar or defining the resolution strategy.

Please, take a look: http://cdsan.com/LinkPool/Data/2915/Conflicts-In-The-LR-Grammars.pdf

If you have questions, please let me know.

Upvotes: 1

rici
rici

Reputation: 241911

It might be possible to solve a reduce/reduce conflict with more lookahead. It might also be possible to solve it by refactoring.

It really depends on the nature of the conflict. There is no general procedure.

An example of a reduce/reduce conflict which can be solved by extra lookahead:

A → something
B → A
C → A
D → B u v
D → C u w

Here, the last two productions of D are unambiguous, but the decision about reducing A to B or to C cannot be made when the u is seen. One more symbol of lookahead would do it, though, because the second next symbol determines the reduction.

The refactoring solution:

Au → A u
Bu → Au
Cu → Au
D  → Bu v
D  → Cu w

By deferring the B/C choice by one token, we've succeeded in removing the reduce/reduce conflict. Note that this solution will work even if u is not a single token; it could, for example, by a non-terminal. So this model may work in cases where simply increasing lookahead is not sufficient.

Upvotes: 5

Related Questions