Two passes when only one is needed?

[bergwerf]

I need to build a math expression parser, so I started playing around a bit with the example. I found some strange behavior though.

When I run this code:

import 'package:petitparser/petitparser.dart';

void main() {
  var number = (char('-').optional() &
          digit().star() &
          char('.').seq(digit().plus()).optional())
      .flatten()
      .trim()
      .map(num.parse);

  var term = undefined();
  var prod = undefined();
  var prim = undefined();

  term.set(prod.seq(char('+').trim()).seq(term).map((values) {
    print(values);
    return values[0] + values[2];
  }).or(prod));
  prod.set(prim.seq(char('*').trim()).seq(prod).map((values) {
    return values[0] * values[2];
  }).or(prim));
  prim.set(char('(').trim().seq(term).seq(char(')'.trim())).map((values) {
    return values[1];
  }).or(number));

  var start = term.end();
  print(start.parse('(1 + 2) + 2 * 3').value);
}

I get this as output:

[1, +, 2]
[1, +, 2]
[3, +, 6]
9

I think that means 1 + 2 went through twice, while it only has to be computed once. Perhaps there is a bug somewhere?

[renggli]

The behavior you observe is correct, given the above grammar. The rule term succeeds parsing prod, but then fails to match the following + so it retries with the second part parsing prod. The same happens for the rule prod. The parens trigger this unfortunate behavior.

Normally this is not a big deal, but you can avoid it by rewriting the grammar (see https://github.com/petitparser/dart-petitparser/blob/master/test/petitparser_test.dart#L70) as:

term <- prod ( '+' prod)*
prod <- prim ('' prim)
prim <- '(' term ')' | num

Or you could use the helper that builds efficient expression parsers more easily: https://github.com/petitparser/dart-petitparser/blob/master/lib/src/petitparser/expression.dart