java - Antlr4 : Evaluate math functions 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)"
所以现在我有属性 String 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 很容易，好吧。但是 build 它呢？也不太难，如果我们将所有运算符视为函数(大多数类型为 (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 child ，所以它有点无限递归，当每个 child 都是 TerminalNode 时被打破(变量或常数)。正如代码中所评论的，您可以将您的运算符构建为 Function 的成员。类，通过实例化或扩展类。当然，这取决于你的Function执行。另一种方式是再建一个AstNode类，BuiltinNode (甚至所有节点 PlusNode 、 DivideNode 等)使用原语解决调用。

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

为此，我们使用 Scope对象(或 HashMap<String, double> 重要的是什么)。我们为已确定其参数的函数创建一个作用域，然后我们使用 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) , 与 a=2和 b=x*y .解决第一个*函数调用我们需要解决它的两个参数( a 和 b )。解决a很简单，因为它是一个终端节点(eval 将立即返回终端)。解决b ，我们需要调用内部函数的eval，生成一个新的作用域{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 生成的图像