13.Precedence and conflict resolution in yacc

We had seen that , when you feed yacc a grammar that is not LALR(1), it shows a warning and resolve the conflicts automatically. For a shift/reduce conflict, yacc will choose the shift. In a reduce/reduce conflict, it will reduce using the rule declared first in the file. We can control what happens by explicitly declaring precedence and associativity for operators.

Rather than re-writing the grammar to implicitly control the precedence and associativity with a bunch of intermediate non-terminals, we can directly indicate the precedence so that yacc will know how to break ties. In the definitions section, we can add any number of precedence levels, one per line, from lowest to highest, and indicate the associativity (either left, right, or nonassoc). Several terminals can be on the same line to assign them equal precedence.

Example:

%token T_Int

%left '+'

%left '*'

%right '^'

%%

E : E '+' E

|E '*' E 

|E '^' E 

|T_Int;

;

The above file says that addition has the lowest precedence and it associates left to right. Multiplication is higher, and is also left associative. Exponentiation is highest precedence and it associates right. These directives disambiguate the conflicts. When we feed yacc the changed file, it uses the precedence and associativity as specified to break ties.For a shift/reduce conflict, if the precedence of the token to be shifted is higher than that of the rule to reduce, it chooses the shift and vice versa. The precedence of a rule is determined by the precedence of the rightmost terminal on the right-hand side (or can be explicitly set with the %prec directive).

So if a 4 + 5 is on the stack and * is coming up, the * has higher precedence than the 4 + 5 , so it shifts. If 4 * 5 is on the stack and + is coming up, it reduces. If 4 + 5 is on the stack and + is coming up, the associativity breaks the tie, a left-to-right associativity would reduce the rule and then go on, a right-to-left would shift and postpone the reduction.

Another way to set precedence is by using the %prec directive. When placed at the end of a production with a terminal symbol as its argument, it explicitly sets the precedence of the production to the same precedence as that terminal. This can be used when the right side has no terminals or when you want to overrule the precedence given by the rightmost terminal.

The keyword, %prec, changes the precedence level associated with a particular grammar rule. %prec appears immediately after the body of the grammar rule, before the action or closing semicolon, and is followed by a token name or literal. It causes the precedence of the grammar rule to become that of the following token name or literal. For example, to make unary minus have the same precedence as multiplication the rules might resemble:

        %left  '+'  '-'

        %left  '*'  '/'

        %%

        expr    :       expr  '+'  expr

                |       expr  '-'  expr

                |       expr  '*'  expr

                |       expr  '/'  expr

                |       '-'  expr      %prec '*'

                |       NAME

                ;

Using yacc 's precedence rules, you can force the choice you want by setting the precedence of the token being shifted versus the precedence of the rule being reduced. Whichever precedence is higher wins out. The precedence of the token is set using the ordinary %left , %right , or %nonassoc directives. The precedence of the rule being reduced is determined by the precedence of the rightmost terminal (set the same way) or via an explicit %prec directive on the production