Yacc expansion of optional clause using the same keyword as following clause

Question

I'm developing a small DSL and having problems getting Yacc (Bison) to cleanly parse for the following symbols:

START (RETURN expression WHERE expression)* RETURN (expression)?

This is what I have so far, but I keep getting shift / reduce conflicts and I'm not sure how to fix them:

start: START conditional_returns returns |
       START returns;

conditional_returns: conditional_returns conditional_return | conditional_return;

conditional_return: RETURN expression WHERE expression;

returns: RETURN expression | RETURN;

I can see that the fact the RETURN keyword is reused in a different clause is causing problems, but I'd like to understand how to split this up correctly using this many rules. Any help would be appreciated?

Answer 1

By themselves, the above rules don't cause any problems; yacc/bison can handle them just fine with no shift/reduce or reduce/reduce conflicts. Where you might be getting into problems is if start is also a legal expression. If that's the case, the language is ambiguous -- when you have a start within a start, a WHERE might be associated with either one. For example, the input

START RETURN START RETURN expr WHERE expr RETURN expr

could be parsed as either

START RETURN ( START RETURN expr ) WHERE expr RETURN expr

or

START RETURN ( START RETURN expr WHERE expr RETURN expr )

depending on what is right for your DSL, you can change the grammar to enforce one meaning or the other, or to disallow nested start expressions if they don't make sense.