79251119

Date: 2024-12-04 12:23:10
Score: 1
Natty:
Report link

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.

Reasons:
  • Blacklisted phrase (1): Is there a way
  • Long answer (-1):
  • Has code block (-0.5):
  • Contains question mark (0.5):
  • Starts with a question (0.5): Is there a
  • Low reputation (0.5):
Posted by: user30482