Antlr4: Evaluate math functions f (x)

One way to do this is to parse your Concrete syntax tree into an abstract syntax tree. Then your function object stores the AST and parses it when called, which is usually much easier. Given your example, f(a, b) = 2 * a * b

this would be parsed into a similar concrete syntax tree:

Of course, you can figure it out well, but it's not easy to make out! The expression 2 * a * b

is written almost like a string, you don't quite know the precedence of the operator when looking at the tree ( 2 + a * b

mean 2 + (a * b)

or (2 + a) * b

?), And it will take a while to get through this in the correct order.

However, we can only parse it once to create something more robust, machine-readable:

Oh yeah, now it's very easy to parse: it was called with parameters params.length

, you set them to a HashMap or whatever represents your scope, then you call a "function" *

with parameters 2

and an expression *(a,b)

that is another function, so we call that passing a

and b

"functions" *

. Of course, this is easily extensible for custom functions.

Given the function abs (value) = max(value, -value)

, we would construct an AST like:

AST analysis is easy, good. But what about building it? Not too difficult if we consider all operators as functions (most types (num, num) -> num

, some (unary) types (num) -> num

). We have a very robust definition for a node in this tree:

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 eval method to a built-in
      return target.eval(innerScope);
   }
}

      

        
        
        
      

    

This might be an oversimplification, but it is a good starting point. As you noticed, CallNode

there are other children in there AstNode

, so this is a bit of infinite recursion, broken when each child is TerminalNode

(variable or constant). As indicated in the code, you can create your operators as members of a class, Function

either by instantiating or extending the class. Of course it depends on your implementation Function

. Another way is to create another class AstNode

, BuiltinNode

(or even all nodes PlusNode

, DivideNode

etc.) to solve the call using primitives.

Add this to answer the comment "how to use the built-in AST". Suppose you have a Function

named object g

that stores an AST for expressions f(x, y) = 2 * a * b

. How to achieve the value f(4, 2)

?

For this we use an object Scope

(or HashMap<String, double>

what it matters for). We create an area for the function where its parameters were defined, then we name it using AST, which will use this area for its internal levels.

The code might look something like this:

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));

      

        
        
        
      

    

To resolve this request eval

, the AST will have a scope {x: 4, y: 2}

beforehand (we created it) and the function *(a, b)

, with a=2

and, is b=x*y

called. To solve the first function call *

, we need to solve both of its arguments ( a

and b

). a

Easy to solve because it is terminal node ( eval

will return terminal immediately). To decide b

, we need to call eval internal function by creating a new area {x: 4, y: 2, a: x, b: y}

, where a

and b

are the arguments of the second function *

. Both a

and b

will be resolved as end nodes, then the second call *

can compute its value (by the built-in function that evaluates 4*2

= 8

) and returns it to the caller, which wasb

for the first function *

.

Now, having scope like {x: 4, y: 2, a: 2, b: 8}

, where x

and y

are parameters f

and a

and b

are arguments to the function *

. With all the arguments set, we can call the built-in function *

that yields 16

, which is the result of the function!

_{Images created by http://ironcreek.net/phpsyntaxtree}