Why I can't parse factorial? Given that I have a simplified Bison BNF grammar:


%token T_EXP '^'
%token T_NOT '!'

%right T_NOT
%right T_EXP
%right T_FAC
%nonassoc T_LPAREN T_RPAREN T_NUMBER

%type expr

%%

expr:
  T_NOT expr # logical not, e.g. !a
| expr T_EXP expr # exponent, e.g. 2 ^ 3
| expr T_NOT %prec T_FAC # factorial, e.g 3!
| T_LPAREN expr T_RPAREN { $$ = $2; }
| T_NUMBER
;

%%


Given a classical example, 2 ^ 3!, it is natural to human that 3! should be produced first, then the exponent and the answer is 2 ^ 3! -> 2 ^ (3!) -> 2 ^ 6 -> 64. It makes sense to assert that factorial goes before the exponent operator, so its binding power must be higher than that of the exponent. 

However, in reality, the parser didn't produce a correct result. I modified the grammar production so that it shows as an AST:

calc eval &gt; 2 ^ 3!
unary !!
  binary ^
    number 2
    number 3
        [expr: 40320]


This expression was evaluated as (2 ^ 3)! -> 8! -> 40320. And no matter how I move the precedences, it always produces the wrong result. If I wrap the factorial with parentheses, i.e. 2 ^ (3!), the result is correct. What's happening in here? Shouldn't 3! be evaluated first?

At first glance, I thought this could be an ambiguity error.

2 ^ 3!    # Input
. 2 ^ 3!  # Lookahead is T_NUMBER(2), shift
2 . ^ 3!  # Lookahead is T_EXP(^), shift
2 ^ . 3!  # Lookahead is T_NUMBER(3), reduce as `expr -&gt; expr T_EXP expr`?
          # But wait! There's a T_NOT behind it


Diverge 1: 

2 ^ . 3!  # Lookahead is T_NUMBER(3), reduce as `expr -&gt; expr T_EXP expr`
expr . !  # Lookahead is T_NOT(!), reduce as `expr -&gt; expr T_NOT`?
expr ! .  # EOF reached, final stack: expr -&gt; expr T_NOT -&gt; (expr T_EXP expr) T_NOT // Incorrect


Diverge 2:

2 ^ . 3!   # Potential lookahead found T_NOT(!), shift
2 ^ 3 . !  # Lookahead is T_NOT(!), reduce as `expr -&gt; expr T_NOT`
2 ^ expr . # EOF reached, final stack: expr -&gt; expr T_EXP expr -&gt; expr T_EXP (expr T_NOT) // Correct


But I considered this as a pure insanity and absurdity that comes out of nowhere in my mind, still ! should be shifted before the number gets reduced because the binding power of T_FAC is higher than that of T_EXP and T_NUMBER, so diverge 2 should have had happened, am I right?
I have no comment on the precedence of the factorial operator; my inclination is to consider it to have higher precedence than other operators because of the almost universal rule that postfix operators bind more tightly than other operators.

When implementing that, you need to create a pseudotoken to modify the default precedence of the prefix operator:

%precedence PREFIX_OP
%right      '^'
%precedence '!'
%%
expr : '!' expr %prec PREFIX_OP
     | expr '^' expr
     | expr '!'
     | '(' expr ')'
     | T_NUMBER


(Using actual character constants in your grammar really makes it more readable, and it also simplifies writing the lexer. So I did that.)

To understand this, remember that precedence relations always compare the precedence of a reduction with the precedence of a shift. These are two distinct things; they only seem to be the same because (f)lex sets the precedence of a reduction (i.e. the right-hand side of a rule) to be equal to the precedence of the last non-terminal in the rule (unless it is specified explicitly with %prec). That's often the "right thing" but it leads to a lot of confusion because it makes it appear that the precedence comparison is between two objects of the same type.

In the resolution of !3!, the parser must decide what to do after seeing !3. The only thing it can do with the 3 (a T_NUMBER) is reduce it to an expr; there is no ambiguity and thus no need to consult precedence relations. (Consequently, %nonassoc T_NUMBER has absolutely no effect, which is which I removed it from the grammar.) It then has two options:


reduce '!' expr to expr
shift the second !


To decide, it precedence-compares the reduction expr: '!' expr with the terminal !. Since the precedence of the reduction was explicitly set with %prec PREFIX_OP this results in a comparison between reduction PREFIX_OP and shift !; the shift wins. The same would happen with 2^3! because the comparison will involve the reduction expr: expr '^' expr whose last terminal is '^' with the shift !.

In your original grammar, the precedence declaration 

expr: expr '!' %prec T_FAC


had no effect whatsoever, because that reduction is never ambiguous (3 ! 2 is a syntax error; no grammar rule applies to it.) Furthermore, the ambiguity between the reduction expr '^' expr and the shift !  was incorrectly resolved because the terminal was declared as having lower precedence than the reduction. Just changing the order of the precedence list wouldn't have the desired result because that would also change the precedence of the reduction expr: '!' expr.