Search code examples
syntaxcompiler-constructionyaccoperator-precedence

%left and %right in yacc

{%
#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

  • %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.