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"라고 한 "public double eval(double... args)"

그래서 지금 문자열 arguments; String expression; String name; 속성을 가진 메신저 후 난 리스너에 많은 시간을 보내고 찾기 위해 시도해야 String의 올바른 인수 등. 그래서 substring()과 indexOf() 등의 이름을 많이 찾고, 인수와 표현식을 찾으려고합니다. 그런 다음 해시 맵에 함수를 저장합니다.

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

MultipleNumbers은 다음과 같습니다하십시오 함수 호출 내 파서에서

처럼 보이는

MultipleNumber: Number(',' Number)+; 

을 렉서에. 그럼 문자열에서 인수를 가져 와서 함수에서 대체하려고합니다. 그럼 내 프로그램은 다시 해결할 수있는 정상적인 표현을했습니다.

이것은 나에게 너무 힘들고 모든 정확한 "부분 문자열"등을 얻는 것이 거의 불가능한 것처럼 보이기 때문에 이런 식으로 구현하는 더 좋은 방법이 있어야한다고 생각합니다. 내가 RLY 캔트 숫자와 변수를 혼합하기 때문에,

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

는 훨씬 더 힘들어지고 : 는 특히 내가 좋아하는 일을하고 싶어 할 때. 그래서 "함수 평가자"를 구현하는 좋은 방법이 있습니다. 어쩌면 해시 맵에 전체 트리를 저장 한 다음 트리 안의 변수를 변경하고 파싱 할 수 있습니까? 내 문법도 꽤 힘들다고 생각해.

나는 과거에 정말로 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을 "function"*에 전달하여 호출합니다. 물론 이것은 사용자 정의 함수로 쉽게 확장 가능합니다. 대서양 표준시가 좋아, 쉽게 구문 분석

: 함수 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를 사용하는 방법"에 대한 답변에이 내용을 추가하십시오. 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=2 및 b=x*y와 함수 *(a, b)를 호출합니다. 첫 번째 * 함수 호출을 해결하려면 두 인수 (a 및 b)를 모두 해결해야합니다. 해결하려면 a은 터미널 노드이기 때문에 쉽습니다 (eval은 터미널을 즉시 반환합니다).b을 풀려면 내부 함수의 평가를 호출하여 {x: 4, y: 2, a: x, b: y}이라는 새 범위를 생성해야합니다. 여기서 a과 b은 두 번째 * 함수의 인수입니다. a과 b 둘 다 터미널 노드로 해결 된 다음 *에 대한 두 번째 호출은 (4*2 = 8을 계산하는 기본 제공 함수로) 그 값을 계산하여 호출자에게 반환 할 수 있습니다.이 값은 첫 번째 * 인 경우 b입니다 기능.

지금 x 및 y는 f 및 a 및 b의 파라미터는 * 함수의 인자되어있는 {x: 4, y: 2, a: 2, b: 8} 같이 범위를 갖는. 모든 인수를 설정하면 * 내장 함수를 호출하여 함수의 결과 인 16을 얻을 수 있습니다!

_{이미지는 많이, http://ironcreek.net/phpsyntaxtree}