C#에서 간단한 문자열 구문 트리를 평가하고 처리하는 방법은 무엇입니까?

Question

나는 쿼리 방법을 제공하는 토큰 인덱스 기반 문서의 코퍼스를 가지고있다. 사용자가 수동으로 (!) 구문 분석 및 평가가 필요한 쿼리 문자열을 입력합니다. 코퍼스는 주어진 쿼리 문자열과 일치하는 모든 문서의 목록을 반환해야합니다. 쿼리 언어는 단순한 부울 연산자 AND, NOT 및 OR을 특징으로하며 괄호로도 우선 순위를 지정할 수 있습니다. 몇 가지 연구를 한 후에 ANTLR을 사용하여 주어진 쿼리 문자열을 구문 트리로 구문 분석했습니다. 예를 들어

:

"Bill OR (John AND Jim) OR (NOT Simon AND Mike)" 

는 다음과 같은 구문 트리로 번역되는 쿼리 :

편집 :

: 바트 Kiers 포스트에 정확한 그래프 (여기에 복사)를 참조하시기 바랍니다

트리의 모든 노드는 단순한 문자열이며 각 노드는 해당 부모를 알고 있습니다. 자녀가 아니라 형제가 아닙니다. 보시다시피, ANTLR 문법은 이미 작업을 실행해야하는 순서를 지정했습니다. 트리의 맨 아래에있는 것들이 먼저옵니다.

그래서 아마도 트리에서 모든 피연산자를 평가하는 것이 필요합니다. 일반적으로 트리의 각 리프에 대해 Get (문자열 용어) 메서드 (예 : "Bill"또는 "John")를 사용하여 내 코퍼스에서 간단한 검색을 수행 할 수 있습니다. Get()은 잎에 용어가 포함 된 문서 목록을 반환합니다. 또한 각 리프의 부모를 평가하여 가능한 NOT 연산자를 인식 한 다음 잎의 용어를 포함하지 않는 문서의 결과 목록으로 연결합니다 (Get() 대신 Not() 메서드 사용). 목록 1의 AND리스트 2에있는 문서의리스트를 반환

• AND 방법 인터 섹트 (리스트 1,리스트 2)를 호출한다 :

  는 AND 및 OR 연산자 개의 파라미터가 필요 메소드 호출로 변환되어야 .

• OR은 list1 또는 list2에있는 문서 목록을 반환하는 Union (list1, list2) 메서드를 호출해야합니다.

매개 변수 list1과 list2에는 Get() 또는 Not()를 사용하기 전에받은 문서가 들어 있습니다.

내 질문은 : 어떻게 의미 론적으로 그리고 구문 론적으로 C#에서 - 모든 필요한 검색어를 평가하고이를 올바른 순서로 올바른 연산자 메소드를 호출하는 데 사용할 수 있습니까? 직관적으로 재귀처럼 들리지만 어쨌든 나는 그것을 묘사 할 수 없다. 특히 호출해야하는 모든 메소드가 동일한 양의 매개 변수를 가지고있는 것은 아니기 때문에. 아니면 이것을 수행 할 수있는 완전히 다른 방법이 있습니까? 의사 코드

Set Eval (Tree t) { 

    switch (t.Operator) { 
     case OR: 
      Set result = emptySet; 
      foreach(child in T.Children) { 
       result = Union(result, Eval(child)); 
      } 
      return result; 
     case AND: 
      Set result = UniversalSet; 
      foreach(child in T.Children) { 
       result = Intersection(result, Eval(child)); 
      } 
      return result; 
     case blah: // Whatever. 
    } 
    // Unreachable. 
} 

에서

Answer 1

는 도움을합니까?

아니면 평가판 순서를 최적화하고 싶었습니까?

나는 다음과 같은 트리가 생성 될 것으로 예상했을 것이다

Answer 2

:

당신이있는 경우, 어느 쪽이든을

(즉, OR 노드가 세 아이가 당신의 AST의 점에 유의)

AST를 만들 수있는 ANTLR 문법을 만들었습니다. (원본 이미지의 형식이든 위의 게시판이든 상관없이) 문법에 올바른 연산자 우선 순위를 정의한 것입니다. 이 경우, 귀하의 나무가 이미 (John <- AND -> Jim)과 (NOT -> Simon)을 먼저 평가해야하기 때문에 운영자의 명령을 혼동해서는 안됩니다.

작업하고있는 ANTLR 문법을 게시 할 수 있습니까?

또한 집합에 대해 이야기하고 있지만, 예에서는 값이 하나만 표시되므로 언어가 지금까지 보여준 것보다 조금 복잡하다는 인상을받습니다. 어쩌면 당신은 실제 언어를 어설픈 다운 버전 대신에 설명 할 수 있습니까?

ps. 이미지를 생성 한 출처는 여기에서 확인할 수 있습니다. http://graph.gafol.net/elDKbwzbA (ANTLR 문법도 포함되어 있지 않습니다.)

Answer 3

정확하게 무엇을 하려는지 확실하지 않지만 AST를 Func<Person, bool>으로 바꿀 것 같습니다. 각 리프 노드는 예를 p => p.Name == "Bill"에 대한 Func<Person, bool>에 evaulated 수 있습니다 AND, OR, 예를 들면 고차 함수로 구현 될 수 없습니다 :

public static Func<T, bool> And<T>(Func<T, bool> a, Func<T, bool> b) 
{ 
    return t => a(t) && b(T); 
} 

이 모든 일을하고 하나의 Func<Person, bool>으로 AST를 붕괴하면 확장 메서드에 대한 매개 변수로 IEnumerable<Person>을 구현하는 모든 유형의 매개 변수로 전달할 수 있습니다.

즉, 먼저 AST를 Func<Person, boo>으로 "컴파일"한 다음 LINQ to Objects를 사용하여 실제로 내 컬렉션을 필터링합니다. AST가 복합 디자인 패턴의 구현이기 때문에 컴파일이 쉬워야합니다. 각 노드는 Func<Person, bool> Compile() 메서드를 노출 할 수 있어야합니다.

Answer 4

나는 ANTLR이 같은 그 뭔가를 가정에 불과 생성하는 객체 모델에 익숙하지 않다 :

class BinaryNode : Node 
{ 
    public Node LeftChild; 
    public Node RightChild;    
    public readonly string Operator;    
} 

class UnaryNode : Node 
{ 
    public Node Child; 
    public readonly string Operator; 
} 

class TerminalNode : Node 
{ 
    public readonly string LeafItem; 
} 

class Node { } 

public class Executor 
{ 
    public IEnumerable<object> Get(string value) 
    { 
     return null; 
    } 
    public IEnumerable<object> GetAll() 
    { 
     return null; 
    } 

    public IEnumerable<object> GetItems(Node node) 
    { 
     if (node is TerminalNode) 
     { 
      var x = node as TerminalNode; 
      return Get(x.LeafItem); 
     } 
     else if (node is BinaryNode) 
     { 
      var x = node as BinaryNode; 
      if (x.Operator == "AND") 
      { 
       return GetItems(x.LeftChild).Intersect(GetItems(x.RightChild)); 
      } 
      else if (x.Operator == "OR") 
      { 
       return GetItems(x.LeftChild).Concat(GetItems(x.RightChild)); 
      } 
     } 
     else if (node is UnaryNode) 
     { 
      var x = node as UnaryNode; 

      if (x.Operator == "NOT") 
      { 
       return GetAll().Except(GetItems(x.Child)); 
      } 
     } 

     throw new NotSupportedException(); 
    } 
} 

참고 그러나이 최적하지 않은, 열심히 쿼리를 평가합니다. 그러나 재귀가 어떻게 작동 할 것인지에 대한 아이디어를 줄 것입니다.