operator precedence with more than 2 recursions

Question

I am trying some combinations of operator precedence and associativity on bison. While some cases it looks odd, basic question appears that if the below rule is valid which do appear not wrong.

expr: expr OP1 expr OP5 '+' expr

According to bison info page, rule takes precedence from last terminal symbol or precedence explicitly assigned to it. Below is a precedence and full expr rules paste from code:

%left OP4
%left OP3
%left OP2
%left OP1
%left '*'
%left '/'
%left '+'
%left '-'

expr:  NUM                               { $$ = $1; }
| expr OP2 expr OP5 '+' expr             { printf("+"); }
| expr OP1 expr OP5 '-' expr             { printf("-"); }
| expr OP4 expr OP5 '*' expr             { printf("*"); }
| expr OP3 expr OP5 '/' expr             { printf("/"); }
          ;
Below is data tokens given:
1op11op5-2op22op5+3op33op5/4op44op5*5

Output on executing parser is below as expected.

-+/*

Now, once precedence is flipped between arithmetic operators and OP, result is reversed indicating that not last terminals are influencing the rule precedence.

%left '*'
%left '/'
%left '+'
%left '-'
%left OP4
%left OP3
%left OP2
%left OP1

Now output of parser is reverse which indicates last terminal precendence is not helping:

*/-+

Further if for first combination with only arithmetic operators at higher precedence than OP operators, if precedence of OP operators is removed, result is still as second combination with no precendece of rules playing. This result makes it difficult to conclude that second expr is used for precdence rather than 3rd one. What can be concluded from above results. What can be the precedence and associativity logic in case more than 2 recursions are used in rules?

Chris Dodd Chris Dodd · Accepted Answer · 2019-11-19T08:51:36

The 'precdence' rules in bison really don't have much to do with operator precedence in the traditional sense -- they're really just a hack for resolving shift-reduce conflicts in a way that can implement simple operator precedence in an ambiguous grammar. So to understand how they work, you need to understand shift/reduce parsing and how the precedence rules are used to resolve conflicts.

The actual mechanism is actually pretty simple. Whenever bison has a shift/reduce conflict in the parser it generates for a grammar, it looks at the rule (to reduce) and the token (to shift) involved in the conflict, and if BOTH have assigned precedence, it resolves the conflict in favor of whichever one has higher precedence. That's it.

So this works pretty well for resolving the precedence of simple binary operators, but if you try to use it for anything more complex, it will likely get you into trouble. In your examples, the conflicts all come between the rules and the shifts for OP1/2/3/4, so all that matters is the relatvie precedence of those two groups -- the precedence within each group is irrelevant as there are never any conflicts between them. So when the rules are higher precedence, they'll reduce left to right, and when the OP tokens are higher precedence it will shift (resulting in eventual right to left reductions).

operator precedence with more than 2 recursions

1 Answers