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;，然后我需要花大量的时间在监听，并设法找到String中的正确参数等。所以很多substring（）和indexOf（）等只是试图找到名称，参数和表达式。然后我将函数保存在一个Hashmap中。

在我的解析器函数调用的样子：

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

MultipleNumbers是：

MultipleNumber: Number(',' Number)+; 

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

因为这对我来说似乎太难了，而且几乎不可能得到所有正确的“子串”等等，我认为必须有更好的方法来实现这样的事情。 特别是当我想要做的事情，如：

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

它变得更加困难，因为我不能RLY混合数字和变量。那么是否有一种实现“功能评估器”的好方法？也许我可以将一棵树保存在一个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)这是另一个函数的“函数”*，所以我们称之为“函数”*。当然这很容易扩展到用户定义的功能。

考虑到功能abs (value) = max(value, -value)，我们将建立类似于AST：

解析AST是容易的，OK。但是建设它呢？如果我们将所有操作符视为函数（大部分类型为(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（变量或常量）时破坏。正如代码中所评论的那样，您可以通过实例化或扩展类来构建运算符，使其成为类的成员。当然，这取决于你的实现。另一种方法是构建另一个AstNode类，BuiltinNode（或甚至所有节点PlusNode,DivideNode等）来解决使用原语的调用。

---

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

要做到这一点，我们使用Scope对象（或重要的是HashMap<String, double>）。我们为参数已经确定的函数创建一个范围，然后我们使用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