How to write yacc rules

user_8256485 0
Viewed 25

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

yacc
1 Answers

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.

user_15662210
Related