1
$\begingroup$

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 > 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 -> 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 -> expr T_EXP expr`
expr . !  # Lookahead is T_NOT(!), reduce as `expr -> expr T_NOT`?
expr ! .  # EOF reached, final stack: expr -> expr T_NOT -> (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 -> expr T_NOT`
2 ^ expr . # EOF reached, final stack: expr -> expr T_EXP expr -> 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?

$\endgroup$

closed as off-topic by David Richerby, Yuval Filmus, Discrete lizard, Evil, vonbrand Aug 1 '18 at 13:24

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions about software development or programming tools are off-topic here, but can be asked on Stack Overflow." – Yuval Filmus, Discrete lizard, Evil, vonbrand
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ I'm not really sure what your question is and what you're looking for in an answer. If it's "Please debug my Bison code", that's off-topic everywhere on Stack Exchange. If it's "Why is Bison doing this with my code?", that seems to be a question for Stack Overflow rather than here, since it's dealing with the specifics of using some technology rather than general computer science principles. $\endgroup$ – David Richerby Jul 31 '18 at 12:44
  • 1
    $\begingroup$ Thanks, although I think this is a (potential) operator precedence problem, it should be in SO at first because a specific software was used as a representation. <s> Who should I contact to arrange a move for this question? </s> Done, I've flagged it. $\endgroup$ – Steve Fan Jul 31 '18 at 12:49
  • $\begingroup$ If the issue is expressing operator precedence correctly in yacc/bison, then it doesn’t belong here. We can help you with the theory of operator precedence, but it seems you’re already on top of it. $\endgroup$ – Yuval Filmus Jul 31 '18 at 13:26
  • $\begingroup$ I've come over a Wikipedia talk page, it seems like the precedence of factorial is ambiguous? $\endgroup$ – Steve Fan Jul 31 '18 at 14:35
1
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.