CODEWITHSUNDEEP
parsinggrammarlalrshift-reduce-conflictreduce-reduce-conflict
Pavel Averin
Pavel Averin

Reputation: 1

What do reduce/reduce and shift/reduce conflicts mean in terms of the grammar structure?

I have to construct LR(0) table to know if there are any sort of conflicts? Is there a way to look at the grammar and tell if there's a conflict without constructing the table? So yeah, the question is more of how think and wrap my head around them. (Examples of grammars are most welcome!)

There were some vague answers in case of shift/reduce conflict here How to solve a shift/reduce conflict? but I'd like to know if there are any specific correlations between rules in grammar and conflicts, or some sort of rule of thumb to identify ones.

Upvotes: 0

Views: 42

Answers (1)

user30482
user30482

Reputation: 333

Is there a way to look at the grammar and tell if there's a conflict without constructing the table?

Yes, but it takes expertise to determine it at a glance and it is not fool-proof. It's generally much faster to just try generating the parser and see whether the generator reports a conflict.

A conflict means that two different parser generators may generate parsers that accept different inputs. A shift-reduce conflict means that one parser may decide to shift while another may decide to reduce, while a reduce-reduce conflict means that there is a state in which two different rules would cause a reduction.

The simplest possible YACC/bison grammar that demonstrates both types of conflicts for LALR(1) follows; I have used bison so that it is easier to reproduce, analyze and experiment with the grammar.

%token A
%%
start : rr rr 
  | sr 
  ;
rr : A 
  | rr A 
  ;
sr : A
  | sr '+' sr
  ;

Storing the above in a file called test.y, we can run bison -Wcounterexamples test.y to see where and why the conflicts occur. Let us look at the shift-reduce conflict first.

test.y: warning: shift/reduce conflict on token '+' [-Wcounterexamples]
  Example: sr '+' sr • '+' sr
  Shift derivation
    sr
    ↳ 6: sr '+' sr
                ↳ 6: sr • '+' sr
  Reduce derivation
    sr
    ↳ 6: sr               '+' sr
         ↳ 6: sr '+' sr •

Here, the example shows us a string of input (e.g. A + A + A) and a position at which the conflict occurs (•). The shift derivation would mean interpreting the string as (A + (A + A)) and the reduce derivation as ((A + A) + A). For a commutative operator (such as the + used here), the order should not be meaningful and we could safely ignore the conflict.

However, the "canonical" shift-reduce conflict is the pair of if/if-else statements, where the interpretation does matter. Consider, for example, if 1 if 1 {} else {}: should the statement be interpreted as (if 1 (if 1 {} else {})) or (if 1 (if 1 {}) else {})? Discussion on solving the conflict can be found here.

Next, let us take a look at the reduce-reduce conflict.

test.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
  Example: rr A • A
  First reduce derivation
    start
    ↳ 1: rr rr
            ↳ 4: rr       A
                 ↳ 3: A •
  Second reduce derivation
    start
    ↳ 1: rr          rr
         ↳ 4: rr A • ↳ 3: A

That is to say, it is ambiguous where in the string A A A ... A A A the first rr ends and the second begins. Reduce-reduce conflicts occur most commonly when there are delimiters or tokens that are used in many different contexts (for example , and ()).

A reduce-reduce conflict effectively means that your grammar is too permissive and that you need to restrict it somehow. Generally, they cannot be ignored, though quite often one can introduce a pre- or post-processing step to the parser to account for them if restructuring the grammar would be inconvenient.

One real-world example of a reduce-reduce conflict is the C-style cast operator, i.e. without a symbol table it is undecidable whether (id)(1) is a type-cast or a function call.

Upvotes: 0

Related Questions