#3 strange behavior with explicit rule precedence

[Chucky Ellison]

I am unable to get explicit rule precedences to do very much at all. I'm using the latest version from SF, v0.9.6.1.

I tried to construct a simple example using only two operators, + and ^ over ints. I include the full source in the attached zip, but a snippet below to explain the behavior.
--------------------------------------------------
// Snippet:
%right FAKEPOWER;
%left FAKEPLUS;
...
%goal Exp;

Int =
INT.arg {: ... :}
;

Exp =
Int.arg
| Exp.arg1 PLUS Exp.arg2 @ FAKEPLUS {: ... :}
| Exp.arg1 POWER Exp.arg2 @ FAKEPOWER {: ... :}
;
// end snippet.
--------------------------------------------------
From my above definition, I expect ^ to bind more tightly than +. I also expect ^ to be right associative, and + to be left associative.
--------------------------------------------------
I am getting the following behavior:
%right FAKEPOWER;
%left FAKEPLUS;
@ FAKEPLUS
@ FAKEPOWER
a) "1 + 2 + 3" = ((1+2)+3)
b) "2 ^ 2 ^ 3" = ((2^2)^3)
c) "1 ^ 2 + 3" = ((1^2)+3)
(a) I expect.
(b) I don't expect. Why is it not treating ^ as a right associative operator?
(c) I expect.
--------------------------------------------------
If I use regular terminal precedence, and delete "@ FAKEPLUS" and "@ FAKEPOWER", everything works as expected. So things seem to work properly as long as the actual terminals in the expressions are used.
%right POWER;
%left PLUS;
/* @ FAKEPLUS */
/* @ FAKEPOWER */
a) "1 + 2 + 3" = ((1+2)+3)
b) "2 ^ 2 ^ 3" = (2^(2^3))
c) "1 ^ 2 + 3" = ((1^2)+3)
--------------------------------------------------
Going back to explicit precedence, if I try reversing the precedence to:
%left FAKEPLUS;
%right FAKEPOWER;
@ FAKEPLUS
@ FAKEPOWER
a) "1 + 2 + 3" = ((1+2)+3)
b) "2 ^ 2 ^ 3" = ((2^2)^3)
c) "1 ^ 2 + 3" = ((1^2)+3)
Same as the original. So somehow the order of the explicit precedences doesn't affect the precedence. (b) is still wrong since ^ should be right assoc, and in this case, I expected for (c) to find (1^(2+3)) since I said + should bind more tightly.
--------------------------------------------------
Thinking maybe this has to do with left/right, I make them both left associative and try to adjust precedence.
%left FAKEPOWER;
%left FAKEPLUS;
@ FAKEPLUS
@ FAKEPOWER
a) "1 + 2 + 3" = ((1+2)+3)
b) "2 ^ 2 ^ 3" = ((2^2)^3)
c) "1 ^ 2 + 3" = ((1^2)+3)
--------------------------------------------------
%left FAKEPLUS;
%left FAKEPOWER;
@ FAKEPLUS
@ FAKEPOWER
a) "1 + 2 + 3" = ((1+2)+3)
b) "2 ^ 2 ^ 3" = ((2^2)^3)
c) "1 ^ 2 + 3" = ((1^2)+3)
As you can see, the parsing is the same whether FAKEPLUS or FAKEPOWER is more or less tight.
--------------------------------------------------
At this point, it doesn't seem like beaver is paying attention to either the order OR the left/rightness of the explicit preferences. So, I comment out that part.
/* %right FAKEPOWER; */
/* %left FAKEPLUS; */
@ FAKEPLUS
@ FAKEPOWER
Error: grammar has conflicts
TestParser.beaver: Error: shift-reduce conflict:
shift PLUS in: Exp = Exp.arg1 *PLUS Exp.arg2 @ 21
or reduce: Exp = Exp.arg1 PLUS Exp.arg2 @ 21
- insufficient precedence information
TestParser.beaver: Error: shift-reduce conflict:
shift POWER in: Exp = Exp.arg1 *POWER Exp.arg2 @ 22
or reduce: Exp = Exp.arg1 PLUS Exp.arg2 @ 21
- insufficient precedence information
TestParser.beaver: Error: shift-reduce conflict:
shift PLUS in: Exp = Exp.arg1 *PLUS Exp.arg2 @ 21
or reduce: Exp = Exp.arg1 POWER Exp.arg2 @ 22
- insufficient precedence information
TestParser.beaver: Error: shift-reduce conflict:
shift POWER in: Exp = Exp.arg1 *POWER Exp.arg2 @ 22
or reduce: Exp = Exp.arg1 POWER Exp.arg2 @ 22
- insufficient precedence information

So for some reason, it wants the declarations, but doesn't pay attention to what I put in them.
--------------------------------------------------
Now I start trying weird stuff.
%right FAKEPOWER, POWER;
%left FAKEPLUS;
@ FAKEPLUS
@ FAKEPOWER
a) "1 + 2 + 3" = ((1+2)+3)
b) "2 ^ 2 ^ 3" = (2^(2^3))
c) "1 ^ 2 + 3" = ((1^2)+3)
Everything works. Very strange.
--------------------------------------------------
%right POWER;
%left FAKEPLUS;
@ FAKEPLUS
@ FAKEPOWER
Error: grammar has conflicts
TestParser.beaver: Error: shift-reduce conflict:
shift PLUS in: Exp = Exp.arg1 *PLUS Exp.arg2 @ 21
or reduce: Exp = Exp.arg1 POWER Exp.arg2 @ 22
- insufficient precedence information
--------------------------------------------------
If I use only regular terminal precedence, but DON'T delete the explicit precedences, I get
%right POWER;
%left PLUS;
@ FAKEPLUS
@ FAKEPOWER
a) "1 + 2 + 3" = (1+(2+3))
b) "2 ^ 2 ^ 3" = (2^(2^3))
c) "1 ^ 2 + 3" = (1^(2+3))
This breaks (a) and (c). I think this is because all operators are assumed to be right associative by default.
--------------------------------------------------
I am puzzled by the behavior of the explicit precedences. I was hoping to be able to use only explicit precedences to declare all precedences and associativity information, since the actual Terminals used in a production may be shared in multiple, nonrelated productions. However, explicit precedences don't seem to work quite right either for specifying precedence or associativity.

Please let me know if anything is unclear about my above description.

[Chucky Ellison]

Source and .class files for driver/flex/grammar of bug

[Alexander Demenchuk]

Here's the root of the issue - Beaver keeps terminals without explicitly assigned precedence as non-associative at the lowest possible precedence level for terminals (one level above precedence for productions). It was a design choice actually - this assignment makes Beaver prefer shifts.

If the above is not intuitive I'm open to suggestions - being an "insider" makes a lot of stuff "obvious", so a fresh look from the outside is always welcomed.

Now, the issue itself is in the _grammar_ - because of the above rule, PLUS and POWER have the lowest possible precedence and therefore conflict resolver always prefers reducing productions.

Let's walk through the examples:

%right FAKEPOWER;
%left FAKEPLUS;
...
%goal Exp;

Int =
INT.arg {: ... :}
;

Exp =
Int.arg
| Exp.arg1 PLUS Exp.arg2 @ FAKEPLUS {: ... :}
| Exp.arg1 POWER Exp.arg2 @ FAKEPOWER {: ... :}
;

Here the precedence "table" will look like this:
FAKEPOWER : right
FAKEPLUS : left
PLUS, POWER : none
So, the parser will prefer reducing ^ expression even when the next symbol is ^ - POWER symbol has lower precedence than corresponding Exp rule because the latter got higher precedence from FAKEPOWER.
FAKEPLUS and PLUS conflict is not that obvious because of the "left" associativity of FAKEPLUS.

Same issue in this example:

%left FAKEPLUS;
%right FAKEPOWER;
@ FAKEPLUS
@ FAKEPOWER
a) "1 + 2 + 3" = ((1+2)+3)
b) "2 ^ 2 ^ 3" = ((2^2)^3)
c) "1 ^ 2 + 3" = ((1^2)+3)

Again it prefers reducing as PLUS and POWER have lower precedence than any Exp rule.

And finally this example:

%right FAKEPOWER, POWER;
%left FAKEPLUS;
@ FAKEPLUS
@ FAKEPOWER
a) "1 + 2 + 3" = ((1+2)+3)
b) "2 ^ 2 ^ 3" = (2^(2^3))
c) "1 ^ 2 + 3" = ((1^2)+3)

Is not weird at all ;-) Here's the precedence table:
FAKEPOWER, POWER : right
FAKEPLUS : left
PLUS : none
As FAKEPOWER, i.e. Exp rule for ^ and POWER now have the _same_ precedence it'll prefer shifting ^ until it has no choice but reduce. But + here still has the lowest precedence, so when parser sees + it'll prefer reducing (for this grammar as all significant rules have explicit precedence, which is higher than PLUS's precedence) whatever is on the stack because shifting + is the least preferred action.

The example grammar should behave as expected when all terminals have _assigned_ precedence _and_ associativity:

%right FAKEPOWER, POWER;
%left FAKEPLUS, PLUS;

Because Beaver derives production precedence from the rightmost terminal the change above will make this grammar look equivalent to one without "fake" terminals:

%right POWER;
%left PLUS;
/* and no @ */

However using @ will allow you to create something really weird ;-) like this:

%right FAKEPOWER, PLUS;
%left FAKEPLUS, POWER;

Parser with such precedence rules will do this:
1 + 2 + 3 = 1 + (2 + 3); PLUS has higher precedence and therefore shifted
2 ^ 2 ^ 3 = (2 ^ 2) ^ 3; FAKEPLUS has higher precedence, so Exp rule, i.e. reduce, is selected
1 ^ 2 + 3 = 1 ^ (2 + 3); PLUS and FAKEPOWER have same precedence, so the "right" action is preferred
1 + 2 ^ 3 = (1 + 2) ^ 3; FAKEPLUS and POWER have same precedence, so "left" action is selected

Hope this explanation helps.