Bison grammar shift/reduce conflicts handling factorial along with other unary operators

Question

I'm noodling around with bison as I read a book on it, and I'm working on a simple infix calculator where I use the grammar to dictate precedence rather than using %left/%right and the order of such declarations.

Most bison calculators I've seen have factorial as a function rather than an operator so those examples have not been helpful.

Currently I have:

 15 calclist:
 16   | calclist expr EOL { printf(" = %d\n", $2); }
 17   | calclist EOL { /* nada */ }
 18   ;
 19 expr:
 20     term
 21   | expr '+' term { $$ = $1 + $3; }
 22   | expr '-' term { $$ = $1 - $3; }
 23   ;
 24 term:
 25     factor
 26   | term '*' factor { $$ = $1 * $3; }
 27   | term '/' factor { $$ = $1 / $3; }
 28   ;
 29 factor:
 30     '|' factor { $$ = $2 > 0 ? $2 : -$2; }
 31   | '-' factor { $$ = 0 - $2; }
 32   | '(' expr ')' { $$ = $2; }
 33   | '(' expr ')' '!' { $$ = factorial($2); }
 34   | NUMBER '!' { $$ = factorial($1); }
 35   | NUMBER
 36   ;

Lines 33 and 34 seem overly verbose. I felt like the proper way to do this is replacing 33/34 with:

33   | factor '!' { $$ = factorial($1); }

But then I get shift/reduce conflicts with negation/abs value operators, which makes sense when I looked at the calc.output file generated with bison -v.

Is there a cleaner way to do this while maintaining the expr/term/factor grammar which defines the operator precedence? Or is my working solution the best I can do given my constraints (self imposed or otherwise).

rici rici · Accepted Answer · 2018-06-06T17:55:14

What does -2! mean? If you add factor: factor '!', then you create an ambiguity because you could parse that as either - <factor: 2 !> or <factor: - 2> !, which are obviously semantically different. [Note 1]

I think the normal understanding would be that postfix operators such as ! take precedence over any prefix operator, so that the natural interpretation of -2! as -(2!) should be applied. [Note 2]

So there has to be a precedence level which binds more tightly than unary prefix operators. And every time you introduce a new precedence level, you need to introduce a new corresponding non-terminal (unless you use precedence declarations; see the bison manual for details and examples).

That leads to:

expr:
    term
  | expr '+' term { $$ = $1 + $3; }
  | expr '-' term { $$ = $1 - $3; }
  ;
term:
  factor
  | term '*' factor { $$ = $1 * $3; }
  | term '/' factor { $$ = $1 / $3; }
  ;
factor:
    postfix
  | '|' postfix { $$ = $2 > 0 ? $2 : -$2; }
  | '-' postfix { $$ = 0 - $2; }
  ;
postfix:
    postfix '!'  { $$ = factorial($1); }
  | '(' expr ')' { $$ = $2; }
  | NUMBER
  ;

Notes

(-2)! might or might not be a semantic error but it doesn't seem like there is any possibility of making it a syntactic error, since the syntax cannot know what (3-5)! might be. Semantically, if one were to generalise factorial to the Euler gamma function, it would be meaningful for negative numbers, with the proviso that Γ of a negative integer is infinite. But that's a complete digression.
In languages like C which have postfix ++, this rule is also normal; -x++ means -(x++). More commonly, the prefix operator in this case would be *.

Bison grammar shift/reduce conflicts handling factorial along with other unary operators

1 Answers

Notes