4

I'm working on a Bison file for a mathematical expression parser. Up to now it's mostly fine, but I'm facing a problem with implicit multiplications.

You see, I'd like to support expressions like 2x sin(4x) cos(4x). It should parse like 2 * x * sin(4 * x) * cos(4 * x). Nothing too bad here, but consider the following set of rules:

expr
    : /* snip */
    | '-' expr      { /* negate expression */ }
    | expr '-' expr { /* subtract expressions */ }
    | expr expr     { /* multiply expressions */ }

Having that implicit multiplication rule creates an ambiguity with the subtraction rule: is x - log(x) the subtraction of log(x) to x or the multiplication of x by -log(x)?

I'd be ready to settle for an easy solution, like "it's a multiplication unless it's subtracting", but I don't know how to tell that to Bison.

zneak
  • 134,922
  • 42
  • 253
  • 328

1 Answers1

6

Having that implicit multiplication rule creates an ambiguity with the subtraction rule: is x - log(x) the subtraction of log(x) to x or the multiplication of x by -log(x)?

Or even, is it x - l * o * g * x? Or maybe just x - log * x?

So not quite a simple problem. Suppose you can tell just by looking at log that it is a function. Then you can disambiguate in your lexer, and you're left with "in case of doubt, an operator that looks like an infix operator is an infix operator". Here's a quick solution:

term   : ID
       | NUMBER
       | '(' expr ')'      { $$ = $2; }
       | FUNC '(' expr ')' { $$ = new_expr($1, 'c', $3); }
       ;

factor : term
       | term factor       { $$ = new_expr($1, '*', $2); }
       ;

prefix : factor
       | '-' factor        { $$ = new_expr(0, '-', $2); }
       ;

muldiv : prefix
       | muldiv '/' prefix { $$ = new_expr($1, '/', $3); }
       | muldiv '*' prefix { $$ = new_expr($1, '*', $3); }
       ;

expr   : muldiv
       | expr '+' muldiv { $$ = new_expr($1, '+', $3); }
       | expr '-' muldiv { $$ = new_expr($1, '-', $3); }
       ;

This particular grammar disallows --x, although it's perfectly happy with y--x, which means y-(-x). If you want to accept --x, you could change the second prefix production to '-' prefix.

Personally, I'd prefer to be able to type sin 2x and log 3n but that starts to get a bit tricky. What does sin 2x cos 2x mean? Presumably, it means (sin(2*x))*(cos(2*x)). But does log nlog n not mean log(n*log(n)) ? This can all be achieved; it just requires thinking through all the possibilities.

rici
  • 234,347
  • 28
  • 237
  • 341
  • 1
    Well, it's not `x * l * o * g` because my lexer sees "log" (and, for that matter, all supported function names) as a distinct token and my parser handles functions with a specific rule. – zneak Oct 14 '12 at 03:13
  • @zneak, yes, I guessed that. Hence the use of FUNC as a lexical token in my grammar :) – rici Oct 14 '12 at 03:14