CODEWITHSUNDEEP
bisonyacc
somecskid
somecskid

Reputation: 3

How to prevent reduce/reduce conflicts for multiple empty rules?

I'm just getting started learning the ropes with Bison and am very confused with the empty rule. So my first question is, can only one rule match empty? I'm reading here and am wondering, what if I require 2 rules that can have "0 or more of something". Wouldn't that create ambiguity for the parser? I've tested this and it's giving me a reduce/reduce conflict.

The thing that is confusing me even more is that I tested out some toy rules like:

rule1: TOKEN { printf("rule1"); }
    | ANOTHER_TOKEN { printf("rule1"); }
;

rule2: ANOTHER_TOKEN { printf("rule2"); }
;

This is obviously ambiguous since rule1 and rule2 match the same input (I tested it out) yet this does not give me a reduce/reduce conflict warning. Is there a reason why? Should things like the above code be avoided at all costs?

Upvotes: 0

Views: 129

Answers (1)

rici
rici

Reputation: 241791

You can have as many rules as you need with the same right-hand side, whether or not it is empty, as long as they are never both applicable.

This is fine:

 foo_list: %empty
         | foo_list foo
 bar_list: %empty
         | bar_list bar

But an ambiguity is created if you then try this:

either_list: foo_list | bar_list

because it is then not clear which alternative an empty either_list refers to. Both empty rules apply.

On the other hand, this is fine:

both_list: foo_list bar_list

Here an empty both_list unambiguously contains an empty foo_list followed by an empty bar_list.

(Note: the second example requires that foo and bar can be distinguished by their first token. If not, you'll get a shift-reduce conflict.)

Upvotes: 0

Related Questions