How to avoid parsing the same input multiple times?

[albertodev01]

Hello, I have managed to create a parser for mathematical expression. It's been very easy with petitparser! This is the code I'm using right now:

import 'dart:math' as math;
import 'package:petitparser/petitparser.dart';

/// Parses mathematical expressions with support for variables.
class ExpressionParser {
  /// Builds a new expression parser accepting strings with a single `x` variable.
  /// For example, valid expressions are:
  /// 
  ///   - `2 + x`
  ///   - `3 * x - 6`
  ///   - `x^2 + cos(x / 2)`
  const ExpressionParser();

  /// Evaluates the parsed expression using the given [value].
  num evaluate(String expression, double value) {
    final builder = ExpressionBuilder();

    // Definition of operator groups. This defines how numbers are parsed and how
    // variables are recognized.
    builder.group()
      ..primitive(digit()
          .plus()
          .seq(char('.').seq(digit().plus()).optional())
          .flatten()
          .trim()
          .map(num.tryParse))
      ..primitive(
          char('x').map((value) => value))
      ..primitive(
          char('e').map((value) => math.e))
      ..primitive(
          string('pi').map((value) => math.pi))
      ..wrapper(char('(').trim(), char(')').trim(), (_, num a,__) => a)
      ..wrapper(string('sqrt(').trim(), char(')').trim(), (_, num a,__) => math.sqrt(a))
      ..wrapper(string('sin(').trim(), char(')').trim(), (_, num a,__) => math.sin(a))
      ..wrapper(string('cos(').trim(), char(')').trim(), (_, num a,__) => math.cos(a))
      ..wrapper(string('exp(').trim(), char(')').trim(), (_, num a,__) => math.exp(a))
      ..wrapper(string('log(').trim(), char(')').trim(), (_, num a,__) => math.log(a))
      ..wrapper(string('acos(').trim(), char(')').trim(), (_, num a,__) => math.acos(a))
      ..wrapper(string('asin(').trim(), char(')').trim(), (_, num a,__) => math.asin(a))
      ..wrapper(string('atan(').trim(), char(')').trim(), (_, num a,__) => math.atan(a));

    // Defining operations among operators.
    builder.group()
      ..prefix(char('-').trim(), (String op, num a) => -a);
    builder.group()
      ..right(char('^').trim(), (num a, String op, num b) => math.pow(a, b));

    // multiplication and addition are left-associative
    builder.group()
      ..left(char('*').trim(), (num a, String op, num b) => a * b)
      ..left(char('/').trim(), (num a, String op, num b) => a / b);
    builder.group()
      ..left(char('+').trim(), (num a, String op, num b) => a + b)
      ..left(char('-').trim(), (num a, String op, num b) => a - b);

    return builder
        .build()
        .end()
        .parse(expression)
        .value as num;
  }
}

While this works, I don't really like this at all. To be more precise, this is the line giving me issues:

..primitive(char('x').map((value) => value))

---

Consider this example:

const expr = ExpressionParser();

for(var value in List<double>.generate(100.0, (i) => i)) {
  expr.evaluate("x+3*sqrt(x)", i);
}

In this case, evaluate is called 100 times adn I'm building a parser using build() for 100 times. Sure, I could "cache" a parser inside a static variable but then how can I pass a value to x?

In other words, how can I avoid building multiple times the parser? Basically, a part from x the whole parser will always be the same. I may work with static variables but I don't like the idea.

Thank you!

[renggli]

There are different ways of solving your problem, each with different performance characteristics of performance, flexibility and required coding:

The typical approach described in compiler-construction books is to build an abstract syntax tree (AST), a tree of objects that represent your expression. To evaluate your expression you can then traverse the tree (or print, simplify, or optimize it). However, this comes at the cost of creating a lot of classes for each node type (unary operator, binary operator, value, variable, ...); but is likely the best way in terms of execution speed and flexibility.

A quick and dirty alternative for your use-case is to make you parser build functions of type typedef Evaluator = double Function(double value);. So the digit production would end with .map((String input) => (double value) => double.parse(input)) (could be further optimized); the add production would end with .map((Evaluator a, String op, Evaluator b) => (double value) => a(value) + b(value)); and finally the variable production would simply end with .map((String variable) => (double value) => value). The parse result is then directly a function that you can evaluate repeatedly with different inputs: final expression = parser.parse('x+3*sqrt(x)'); print(expression(16));.

[renggli]

Added an example that shows the second approach with c6fdc5e.