%left and %right in yacc

Question

{%
#include<stdio.h>
#include<stdlib.h>
%}
  
%token ID NUM IF THEN LE GE EQ NE OR AND ELSE

%right '='
%left AND OR
%left '<' '>' LE GE EQ NE
%left '+''-'
%left '*''/'
%right UMINUS
%left '!'

%%

The code mentioned above is part of the yacc for a simple IF ELSE program.

What do %right and %left mean?

Solution 1

%left and %right specify the associativity of an operator. The associativity of an operation determines which of two operations of the same precedence level is carried out first.

Suppose we have the grammar rules:

exp ::= exp + exp
exp ::= ID

and suppose we have to parse the expression x+y-z. You see, as the precedence level of plus and minus is the same, this expression can be interpreted as (x+y)-z or x+(y-z). This does not seem like a big deal, but it introduces an ambiguity into the grammar.

Parsing issues and theory aside, suppose we're parsing the expression. 6+5-7, and suppose that our language can only work with natural numbers, and throws an exception when underflow occurs. The result of (6+5)-7 (4) will not be not equal to 6+(5-7) (exception), so we won't be able to predict the result -- unless we define the evaulation order by specifying the associativity of the operators. Also consider the case of expressions like f()+g()+h(), when the operands are functions which may have side effects.

Solution 2

I know this is an old question but in case some one else is looking for this information :

%left, %right and %nonassoc, defines how yacc will solve repetition of operators. In case you have:

1 + 2 + 3

both operators have the same precedence level ( they are the same :) ), in this case yacc can solve:

// using %left
(1 + 2) + 3

or:

// using %right
1 + (2 + 3)

and finally:

//using %nonassoc
1 + 2 + 3 is considered illegal and a syntax error!

you can read more in here.

Comments

[Ani]

Also as %left '*' '/' is written below %left '+' '-', * and / gets more precedence than + and -