How to write yacc rules

Question

I'm a newbie to yacc and not really understand how to write the rules, especially handle the recursive definitions.

%token NUMBER
%token VARIABLE

%left '+' '-'
%left '*' '/' '%'
%left '(' ')'

%%

S: VARIABLE'='E {
       printf("\nEntered arithmetic expression is Valid\n\n");
       return 0;
     }

E    : E'+'E 
     | E'-'E 
     | E'*'E 
     | E'/'E 
     | E'%'E 
     | '('E')' 
     | NUMBER 
     | VARIABLE
     ;

%%

The above example is work well, but when I changed it as below, it got "5 shift/reduce conflicts".

%token NUMBER
%token VARIABLE
%token MINS
%token PULS
%token MUL
%token DIV
%token MOD
%token LP
%token RP

%left MINS PULS
%left MUL DIV MOD
%left LP RP

%%

S: VARIABLE'='E {
       printf("\nEntered arithmetic expression is Valid\n\n");
       return 0;
     }

E   : E operator E 
    | LP E RP 
    | NUMBER 
    | VARIABLE
    ;

operator:   MINS 
            | PULS
            | MUL 
            | DIV 
            | MOD
            ;

%%

Can any one tell me what is the difference between these examples? Thanks a lot..

I don't think you have to have `%token` declarations for the operators. `%left` already implies they are tokens. That doesn't seem to solve the problem, though. — Piotr Siupa, Jul 21 '22 at 13:10
@NO_NAME: Bison/yacc allows multiple declarations of symbols provided they are consistent with each other. So you cannot declare a name to be both a token and a non-terminal, or to have two different types. If you do that, you'll get an error message. But declaring a token with both `%token` and precedence is fine. In fact, it's the only way to declare a token's precedence as well as its type. (Although it's rare that you need semantic value for an operator with precedence, it is possible to do.) — rici, Jul 21 '22 at 15:58

rici · Answer 1 · 2022-07-21T16:14:49.433

The difference is the additional indirection with the non-terminal operator. That serves to defeat your precedence declarations.

Precedence is immediate, not transparent. That is, it only functions in the production directly including the terminal. In your second grammar, that production is:

operator:   MINS 
            | PULS
            | MUL 
            | DIV 
            | MOD
            ;

But there is no ambiguity to resolve in that production. All of those terminals are unambiguously reduced to operator. The ambiguity is in the production

E   : E operator E

And that production has no terminals in it.

By contrast, in your first grammar, the productions

E    : E'+'E 
     | E'-'E 
     | E'*'E 
     | E'/'E 
     | E'%'E

(which would be easier to read with a bit more whitespace) do include terminals whose precedences can be compared with each other.

The precise working of precedence declarations is explained in the Bison manual. In case, it's useful, here's a description of the algorithm I wrote a few years ago in a different answer on this site.

How to write yacc rules

1 Answers1