3

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 ?

Iakob Fokas
  • 193
  • 1
  • 2
  • 6
  • I haven't seen a lot of questions like this here. Maybe you'd have better luck at Computer Science (http://cs.stackexchange.com/)? – vesan Jan 11 '16 at 22:45

2 Answers2

4

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.

rici
  • 234,347
  • 28
  • 237
  • 341
  • My problem is with this grammar S -> +SS | +S | SS | a In this grammar how can we find more lookaheads ? Your example was simple (and helpful) . I construct the LR(1) table and in one cell , I have 3 actions , shift, reduce and reduce. Is there a way to solve these conflicts without refactoring – Iakob Fokas Jan 12 '16 at 21:00
  • For example (what I mean without refactoring) : I believe that the grammar describes a regular language, so maybe it is possible to resolve the conflict by selecting one of the possibles actions,but how can be sure ? – Iakob Fokas Jan 12 '16 at 21:10
  • @IakobFokas: That grammar is ambiguous in various ways, and you cannot generate a conflict-free parser for an ambiguous grammar no matter how much lookahead you give it. So your first step will be to remove the ambiguities. You are correct that the language recognized by the grammar is regular; if I am not mistaken, it is `(+|a)*a`. I don't think the regular expression is useful for parsing the language, since all structure has been removed, but then neither is an ambiguous grammar. – rici Jan 13 '16 at 01:03
  • @Kirill Kobelev write on his answer that "any conflict can be resolved by additional look ahead..." and you say "cannot generate a conflict-free parser for an ambiguous grammar no matter how much lookahead you give it" . What is true ? – Iakob Fokas Jan 13 '16 at 09:27
  • @Iakob: What I said. Ambiguous grammars allow multiple parses, and that means there will be conflicts. – rici Jan 13 '16 at 12:15
2

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.

Kirill Kobelev
  • 10,252
  • 6
  • 30
  • 51
  • 1
    Not true. If the grammar is ambiguous, no amount of lookahead will resolve the conflict as there are multiple possible parses. – Chris Dodd Apr 15 '21 at 04:55
  • Well, if you speak about grammar theory - this is true. Any parsing has equal value. Parsing programming languages that have semantics is different. Only one parsing will be correct for a complete program. – Kirill Kobelev Apr 16 '21 at 08:26