yacc shift reduce problem

Question

i have what i think is a simple part of my grammar this is getting an error from yacc. i know i need to add a %prec somewhere, but not really sure where.

Assignment : Ref '=' Ref
           | Ref '=' Expression
           | Ref '=' Value
           | Ref '=' FunctionCall
           ;

Ref : ID
    | ID '[' Expression ']'
    ;

Value : INT
      | BOOLEAN
      | CHAR
      | STRING
      ;

The error im getting is:

 warning: rule never reduced because of conflicts: Assignment: Ref '=' Ref
 warning: rule never reduced because of conflicts: Assignment: Ref '=' Value

So ID is just a variable name, and Ref is a reference to a variable.

Answer 1

hmm not sure, would FunctionCall, Value, and Ref also be Expressions? maybe if it works when Expression is removed, that might suggest Expression contains one of those as well...

Answer 2

The problem with Assignment : Ref '=' Ref is Ref = Ref = Ref is ambiguous (of which you're probably already aware); try defining the '=' token using the %right keyword (assuming you want "=" to be right-associative):

%right '='

As for Assignment: Ref '=' Value, I'd have to see the definition for ID and the various Value bodies, though defining '=' as right associative might be enough.

Answer 3

It would appear that the parser can't distinguish between the the various Assignment strings in the grammar within the (rather severe) restrictions on its look-ahead.

If the ID and Value productions were easy to parse I don't think you would have this problem. You could quite possibly group all of the Assignment productions together into one, which would at least make it easier to reduce that one rule and make the problem more obvious.

Answer 4

We'd really need to see the definitions of FunctionCall and (especially) Expression to give a definitive answer, but my guess would be that an Expression can be either a single Ref or a Value. In this case, it's saying it doesn't know (for sure) whether to parse a Ref/Value on the right side of an assignment directly as itself, or as a simple expression.

The surprising thing is that FunctionCall hasn't produced a similar ambiguity -- this tends to indicate that your definition of Expression is probably odd to the point of at least bordering on defective.

If I were doing it, I'd probably change the definition of Assignment to look something like:

%left '-' '+'
%left '*' '/'   

%%

Assignment: Ref '=' Expression;

Expression: Value
          | FunctionCall
          | Ref
          | Expression '+' Expression
          | Expression '-' Expression
          | Expression '/' Expression
          | Expression '*' Expression
          | '(' Expression ')'
          ; 

Of course, you might want to support more operators than the basic four, but it's hard to guess -- I've just tried to throw in enough to give at least a reasonable idea.

In any case, with this structure there's no question that the right side of an assignment has to be an Expression, and the Expression can include the three basic items you've listed, combined with arbitrary arithmetic operators, so something like:

x[i] = a[2] + 1 + f(3)

Has to become (progressively):

Ref = Expression
Ref = Expression '+' Expression
Ref = Expression '+' Expression '+' Expression
Ref = Ref '+' Value '+' FunctionCall
ID '[' ID ']' '=' ID '[' Value ']' '+' Value '+' FunctionCall

(and FunctionCall would probably reduce further to something like: ID '(' Value ')'

Bottom line: at least this part of the grammar is essentially immune to S/R conflicts -- there's a clear, unequivocal path from the top level Assignment to the individual tokens for a particular assignment. This also helps reduce confusion for the user because all expressions have the same syntax.