Resolving reduce/reduce conflicts in yacc

Question

I want to know how resolve the reduce/reduce conflict without making hundreds of lines. This rule is getting a conflict on every token who is between rvalue... "rvalue token rvalue".

rvalue
    : '(' rvalue ')'                   
    | lvalue                            
    | literal                           
    | lvalue assign rvalue              
    | inc_dec lvalue                    
    | lvalue inc_dec                    
    | '-' rvalue                       
    | '!' rvalue                        
    | '~' rvalue                        
    | '&' lvalue                        
    | rvalue '|' rvalue                 
    | rvalue '^' rvalue                
    | rvalue '&' rvalue                 
    | rvalue RIGHT_SHIFT rvalue         
    | rvalue LEFT_SHIFT rvalue         
    | rvalue COMPARE rvalue             
    | rvalue DIFF rvalue                
    | rvalue '<' rvalue                 
    | rvalue LE rvalue                  
    | rvalue '>' rvalue                 
    | rvalue GE rvalue                  
    | rvalue '-' rvalue                
    | rvalue '+' rvalue                 
    | rvalue '%' rvalue                
    | rvalue '*' rvalue                 
    | rvalue '/' rvalue                   
    | rvalue '?' rvalue ':' rvalue     
    | rvalue '(' ')'                    
    | rvalue '(' rvalue rvalues ')'    
    ;

Thanks for any help...

Answer 1

First, use the -v option to yacc to produce a y.output showing all the states and conflicts for your grammar. This will show you which rules are involved in the shift/reduce and reduce/reduce conflicts that you see.

Second, your grammar fragment is incomplete as its is missing rules for all the non-terminals other than rvalue. The fragment you've posted does not have any reduce/reduce conflicts in itself (though it does have a large number of shift/reduce conflicts, due left/right/procedence conflicts). They can be resolved by adding appropriate precedence rules (%left/%right declarations) for your tokens, or by splitting the rules into multiple precedence level rules.

I suspect you also have a rule like rvalues: rvalue | rvalues rvalue ; which, when combined with the rule above, leads to a large number of reduce/reduce conflicts. These conflicts are also precedence ambiguities, but as there is no tokens in the rvalues rule (its just one or more rvalues in sequence, with no intervening token), it cannot be resolved by yacc precedence rules, but can be resolved by splitting the rules into precedence levels.

If you want more specific help, you'll need to post more of your grammar (at least the rvalues rule)

edit

The general approach for avoiding the reduce/reduce conflicts you get from the ambiguity between infix/prefix operators and allowing consecutive expressions with no intervening tokens is to split the expression rule into two versions -- one that begins with the problematic prefix operator(s) and one that does not. Then, in contexts where an expression immediately follow another expression with no intervening token, you use just the second rule instead of the general rule. In your case, that would give you something like:

rvalue_noprefix
    : '(' rvalue ')'
    | lvalue
    | literal
    | lvalue assign rvalue
    | inc_dec lvalue
    | lvalue inc_dec
    | '!' rvalue
    | '~' rvalue
    | rvalue_noprefix '|' rvalue
    | rvalue_noprefix '^' rvalue
    | rvalue_noprefix '&' rvalue
    | rvalue_noprefix RIGHT_SHIFT rvalue
    | rvalue_noprefix LEFT_SHIFT rvalue
    | rvalue_noprefix COMPARE rvalue
    | rvalue_noprefix DIFF rvalue
    | rvalue_noprefix '<' rvalue
    | rvalue_noprefix LE rvalue
    | rvalue_noprefix '>' rvalue
    | rvalue_noprefix GE rvalue
    | rvalue_noprefix '-' rvalue
    | rvalue_noprefix '+' rvalue
    | rvalue_noprefix '%' rvalue
    | rvalue_noprefix '*' rvalue
    | rvalue_noprefix '/' rvalue
    | rvalue_noprefix '?' rvalue ':' rvalue
    | rvalue_noprefix '(' ')'
    | rvalue_noprefix '(' rvalue rvalues ')'
;

rvalue_prefix
    : '-' rvalue
    | '&' lvalue
    | rvalue_prefix '|' rvalue
    | rvalue_prefix '^' rvalue
    | rvalue_prefix '&' rvalue
    | rvalue_prefix RIGHT_SHIFT rvalue
    | rvalue_prefix LEFT_SHIFT rvalue
    | rvalue_prefix COMPARE rvalue
    | rvalue_prefix DIFF rvalue
    | rvalue_prefix '<' rvalue
    | rvalue_prefix LE rvalue
    | rvalue_prefix '>' rvalue
    | rvalue_prefix GE rvalue
    | rvalue_prefix '-' rvalue
    | rvalue_prefix '+' rvalue
    | rvalue_prefix '%' rvalue
    | rvalue_prefix '*' rvalue
    | rvalue_prefix '/' rvalue
    | rvalue_prefix '?' rvalue ':' rvalue
    | rvalue_prefix '(' ')'
    | rvalue_prefix '(' rvalue rvalues ')'
;

rvalue: rvalue_prefix | rvalue_noprefix ;

You can understand this is as rvalue_prefix matching all the different rvalue expressions that begin with a prefix & or - operator, while rvalue_nonprefix matches all other expressions. Then when you have a context with consecutive rvalues, you change all the following rvalues to be rvalue_nonprefix instead, as anything that looks like it begins with a - or & in that context should be combined with the preceeding rvalue as an infix operator.

This is a substantial growth in the size of your grammar (all the infix operators have been duplicated), but it is by no means "hundreds of additional rules". In particular, you only need one split regardless of how many different ambiguous prefix/infix operators you have. You need an addition split (duplicating everything again) if you also have ambiguous postfix/infix operators, but your example does not appear to have that problem.