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.