Antlr4: вычисление математических функций f(x)

Один из способов сделать это-разбить ваше конкретное синтаксическое дерево на абстрактное синтаксическое дерево. Затем объект функции сохраняет AST и анализирует его при вызове, что обычно намного проще. Учитывая ваш пример, f(a, b) = 2 * a * b, это было бы разбито на аналогичное конкретное синтаксическое дерево:

Конечно, вы можете это хорошо понять, но это не так просто разобрать! Выражение 2 * a * b записывается в значительной степени как строка, вы не совсем знаете приоритет оператора, глядя у дерева (означает ли 2 + a * b 2 + (a * b) или (2 + a) * b?) и потребуется некоторое время, чтобы пересечь его в правильном порядке. Однако мы можем разобрать его только один раз, чтобы построить что-то более надежное, более легкое для понимания машины:

О да, теперь это действительно легко разобрать: его вызывают с параметрами params.length, вы устанавливаете их в хэш-карту или что-то, представляющее вашу область, затем вы вызываете "функцию" * с параметрами 2 и выражением *(a,b), которое является другая функция, поэтому мы называем ее, передавая a и b в "функцию" *. Конечно, это легко расширяется для пользовательских функций.

Рассматривая функцию abs (value) = max(value, -value), мы построим АСТ, подобный:

Разбор AST прост, ОК. Но как насчет того, чтобы построить его? Не слишком сложно, если рассматривать все операторы как функции (большинство типа (num, num) -> num, некоторые (унарные) типа (num) -> num). У нас есть очень стабильное определение для узла в этом дерево:

interface AstNode {
   double eval(Scope scope); // you can look at scope as a HashMap<String, double>
}

class TerminalNode : AstNode {
   String varName;
   double constantValue;

   public TerminalNode(String varName) {
      this.varName = varName;
   }
   public TerminalNode(double constantValue) {
      this.constantValue = constantValue;
      this.varName = null;
   }

   public double eval(Scope scope) {
      if (varName == null) return constantValue;
      return scope.get(varName);
   }
}

class CallNode : AstNode {
   Function target;
   String[] parameters;
   AstNode[] children;

   public CallNode(Function target, String[] parameters, AstNode[] children) {
      this.target = target;
      this.parameters = parameters;
      this.children = children;
   }

   public double eval(Scope scope) {
      double[] subExpressions = new double[children.length];
      Scope innerScope = new Scope(scope); // creates a copy
      for (int i = 0; i < children.length; i++) {
         // I'm using the copy here because of the edge-case: f(x) = g(x) + x; g(x) = x * 2;
         // In this case, the x variable is overriden in the innerScope when we resolve g(x)
         // but we "stored" the previous x value in the "outerScope" so we can add it later
         subExpressions[i] = children[i].eval(scope);
         innerScope.set(target.getParamName(i), subExpressions[i]);
      }
      // usually, you could do target.getNode().eval(innerScope)
      // however, this would limit the target function to only be user-defined functions
      // we leave this way so you can override the Function's eval method to a built-in
      return target.eval(innerScope);
   }
}

Это может быть чрезмерным упрощением, но это хорошая отправная точка. Как вы заметили, у CallNode есть другие AstNode потомки, поэтому это немного бесконечная рекурсия, нарушенная, когда каждый ребенок является TerminalNode (переменная или константа). Как указано в коде, вы можете построить свои операторы как члены класса Function, либо путем создания экземпляра, либо путем расширения класса. Конечно, это зависит от вашей реализации Function. Другой способ-построить другой класс AstNode, BuiltinNode (или даже все узлы PlusNode, DivideNode, и т.д.) Для решения вызова с использованием примитивов.

---

Добавляя это, чтобы ответить на комментарий, "как использовать построенный AST". Предположим, у вас есть объект Function с именем g, который хранит AST для выражений f(x, y) = 2 * a * b. Как достичь значения f(4, 2)?

Для этого мы используем объект Scope (или HashMap<String, double>, если это имеет значение). Мы создаем область видимости для функции, где были определены ее параметры, а затем вызываем ее с помощью АСТ, которая будет использовать эту сферу для своих внутренних уровней.

Код может выглядеть примерно так:

Scope scope = new Scope();
scope.set("x", 4);
scope.set("y", 2);
// remember I stored the function f on the object g, just to make a distinction
// also, note this is equivalent to g.getNode().eval(scope), because the function stored in g is not a built-in!
System.out.println(g.eval(scope));

Чтобы решить этот eval запрос, AST заранее будет иметь область {x: 4, y: 2} (мы ее создали) и вызовет функцию *(a, b), с a=2 и b=x*y. Для решения первого вызова функции * необходимо решить оба ее аргумента (a и b). Решить a легко, потому что это терминальный узел (eval немедленно вернет терминал). Чтобы решить b, нам нужно вызовите оценку внутренней функции, генерируя новую область {x: 4, y: 2, a: x, b: y}, где a и b являются аргументами второй функции *. И a, и b будут решаться как конечные узлы, тогда второй вызов * может вычислить его значение (с помощью встроенной функции, которая вычисляет 4*2=8) и верните его вызывающему объекту, который был b для первой функции *.

Теперь имеет область видимости {x: 4, y: 2, a: 2, b: 8}, где x и y - параметры f и a и b являются аргументами функции *. При всех заданных аргументах мы можем вызвать встроенную функцию *, дающую 16, которая является результатом функции!

_{изображения, генерируемые http://ironcreek.net/phpsyntaxtree}