Antlr4：评估数学函数 f(x)

Question

最后几天我正在研究我的语法，以便能够计算正常表达式，例如：2+2*5；2^2 或设置变量如 y=5+5；等等。

现在我想解析像 f(a,b)=2*a*b; 这样的函数。然后像 f(5,7) 一样稍后调用它们；我有一些麻烦。

所以假设我尝试解析这样的函数声明：

function:name=Var'(' varNames=(MultVar|Var) ')' '=' (Var|Number) (operator=('*'|'/'|'+'|'-') (Var|Number))* SEMI;

所以这（有点）有效，但我认为它有点“脏”或其他什么。所以我和一个听众一起工作，当我在“exitFunction”中时，我真的不知道如何最好地处理这个函数，所以我可以评估 f(5,7) 之类的东西；好简单。

我有一个名为“Function.java”的 Java 类和方法 "public double eval(double... args)"

所以现在我有属性字符串arguments; String expression; String name;，然后我需要在侦听器中花费大量时间并尝试在字符串中找到正确的参数等。很多 substring() 和 indexOf() 等只是试图找到名称、参数和表达式。然后我将该函数保存在 Hashmap 中。

在我的解析器中，函数调用如下所示：

functioncall: name=Vart '('para=(MultipleNumbers) ')' SEMI;

MultipleNumbers 将是：

MultipleNumber: Number(',' Number)+;

在词法分析器中。然后我尝试从字符串中获取参数，并在函数中替换它们。然后我有一个正常的表达式，我的程序可以再次解决它。

由于这对我来说似乎太难了，而且几乎不可能获得所有正确的“子字符串”等，我认为必须有更好的方法来实现这样的事情。尤其是当我想做以下事情时：

 f(a,b)=2*a+b; a=5; f(a,5)

它变得更加困难，因为我无法混合数字和变量。那么有没有一种好方法来实现“功能评估器”。也许我可以在 Hashmap 中保存一整棵树，然后只需更改树内的变量并解析它，或者？认为我的语法对于任务来说也非常糟糕。

由于我过去并没有真正与 antlr 合作，因此我感谢每一个帮助。希望可以有人帮帮我。对不起，我的英语不好，我希望你能理解我。

亲切的问候

FelRPI

Answer 1

一种方法是将具体语法树解析为抽象语法树。然后你的函数对象存储 AST 并在调用时解析它，这通常要简单得多。考虑到您的示例f(a, b) = 2 * a * b，这将被解析为类似的具体语法树：

当然很好理解，但是解析起来却不容易！该表达式的2 * a * b编写方式非常类似于字符串，通过查看树您不太了解运算符优先级（意味着2 + a * b或2 + (a * b)？(2 + a) * b），并且需要一些时间才能以正确的顺序遍历它。

然而，我们只能解析它一次，以构建更可靠、更容易让机器理解的东西：

哦，是的，现在它真的很容易解析：它用params.length参数调用，你将它们设置在 HashMap 或代表你的范围的任何东西中，然后你用*参数2和表达式调用“函数” *(a,b)，这是另一个函数，所以我们称之为它通过将a和传递b给“函数” *。当然，这可以轻松扩展到用户定义的函数。

考虑到函数abs (value) = max(value, -value)，我们将构建一个类似于以下内容的 AST：

解析 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);
   }
}

这可能过于简单化，但却是一个很好的起点。正如您所注意到的， aCallNode有其他AstNode孩子，所以它有点无限递归，当每个孩子都是 a TerminalNode（变量或常量）时就会被破坏。正如代码中所注释的，您可以Function通过实例化或扩展类来将运算符构建为类的成员。当然，这取决于您的Function实现。另一种方法是构建另一个AstNode类BuiltinNode（甚至所有节点PlusNode，DivideNode等等）来使用原语解决调用。

添加此内容是为了回答评论“如何使用内置的 AST”。假设您有一个Function名为 的对象g，它存储表达式的 AST f(x, y) = 2 * a * b。如何实现价值f(4, 2)？

为此，我们使用该Scope对象（或HashMap<String, double>重要的 a）。我们为函数创建一个范围，其中的参数已确定，然后我们使用 AST 调用它，AST 将使用该范围作为其内部级别。

代码可能类似于：

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), 。为了解决第一个函数调用问题，我们需要解决它的两个参数（和）。解决起来很容易，因为它是一个终端节点（会立即返回终端）。为了解决，我们需要调用内部函数的 eval ，生成一个新的作用域，其中和是第二个函数的参数。和都将作为终端节点进行求解，然后第二次调用可以计算其值（通过内置函数计算= ）并将其返回给调用者，这是第一个函数的值。a=2b=x*y*abaevalb{x: 4, y: 2, a: x, b: y}ab*ab*4*28b*

现在有一个类似于 的范围{x: 4, y: 2, a: 2, b: 8}，其中x和是和y的参数，并且是函数的参数。设置完所有参数后，我们可以调用内置函数，yieling ，这是函数的结果！fab**16

_{图片由http://ironcreek.net/phpsyntaxtree生成}