%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 '!'

%%

Mentioned Above is a part in the yacc program for a simple IF ELSE program.... i m just a beginner and don't understand what do we mean by %right and %left terms...... plz help me on this occasion...

回答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.

回答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.