¿Cómo evaluar y procesar un árbol de sintaxis de cadena simple en C#?

Question

Tengo un corpus de documentos basados ​​en token-index que ofrece un método de consulta. El usuario ingresa manualmente (!) Una cadena de consulta que necesita ser analizada y evaluada. El corpus debería devolver una lista de todos los documentos que coincidan con la cadena de consulta dada. El lenguaje de consulta presenta los operadores booleanos simples AND, NOT y OR que también se pueden priorizar por paréntesis. Después de algunas investigaciones, ya utilicé ANTLR para analizar una cadena de consulta dada en un árbol de sintaxis.

Por ejemplo: La consulta

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

se traduce en el siguiente árbol de sintaxis:

EDIT: Por favor, véase el gráfico correcto en Bart Kiers post (copiado aquí):

Todos los nodos en el árbol son cadenas simples y cada nodo conoce su padre y niños pero no sus hermanos. Como puede ver, la gramática ANTLR ya dictaba el orden en el que las operaciones deben ejecutarse: las que están en la parte inferior del árbol son lo primero.

Entonces, lo que probablemente deba hacer es recusivamente (?) Evaluar todos los operandos en el árbol. En general, puedo hacer una búsqueda simple en mi corpus utilizando un método Get (término de cadena) para cada hoja en el árbol (como "Bill" o "John"). Get() devuelve una lista de documentos que contienen el término en la hoja. También puedo evaluar el padre de cada hoja para reconocer un posible operador NOT que luego llevaría a una lista de resultados de documentos que NO contienen el término en la hoja (usando el método Not() en lugar de Get()).

El AND y OR operador debería transformarse en llamadas a métodos que requieren dos parámetros:

• y debe llamar a un método Intersect (lista1, lista2) que devuelve una lista de documentos que se encuentran en Lista1 y en lista2 .
• O debe llamar a un método Union (list1, list2) que devuelve una lista de documentos que están en list1 O en list2.

Los parámetros list1 y list2 contienen los documentos que recibí antes de usar Get() o Not().

Mi pregunta es: ¿cómo puedo, semánticamente y sintácticamente en C#, evaluar todos los términos de búsqueda necesarios y usarlos para llamar a los métodos correctos del operador en el orden correcto? Intuitivamente suena como recursividad, pero de alguna manera no puedo imaginarlo, especialmente porque no todos los métodos que necesitan ser llamados tienen la misma cantidad de parámetros. ¿O hay otras maneras completamente diferentes de lograr esto?

Answer 1

En Pseudo Código

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. 
} 

ayuda eso?

¿O estabas buscando optimizar el orden de las evaluaciones, que probablemente tiene libros escritos en él ...

Answer 2

lo que habría esperado el siguiente árbol que se genere:

(tenga en cuenta que, en su AST, el nodo OR tiene 3 hijos)

De cualquier manera, si usted tiene creó una gramática ANTLR que es capaz de crear un AST (ya sea en la forma de su imagen original, o la mía publicada anteriormente), significa que ha definido la precedencia apropiada del operador en su gramática. En ese caso, no debe confundirse la ejecución del pedido de sus operadores ya que su árbol ya exige que primero se evalúen (John <- AND -> Jim) y (NOT -> Simon).

¿Podría publicar la gramática ANTLR en la que ha estado trabajando?

Además, está hablando de conjuntos, pero en su ejemplo, solo se muestran valores únicos, por lo que me da la impresión de que su lenguaje es un poco más complejo de lo que ha demostrado hasta ahora. ¿Quizás podría explicar su lenguaje actual, en lugar de una versión simplificada?

PS. La fuente que creó la imagen se puede encontrar aquí: http://graph.gafol.net/elDKbwzbA (la gramática ANTLR también se incluyó)

Answer 3

No estoy exactamente seguro de lo que estás tratando de hacer, pero creo que convertiría el AST en Func<Person, bool>. Cada nodo hoja puede evaulated a un Func<Person, bool> por ejemplo p => p.Name == "Bill" AND, OR y NOT se puede implementar como funciones de orden superior, por ejemplo:

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

Una vez hecho todo esto y se derrumbó su AST en un solo Func<Person, bool> , puede pasar eso como el parámetro al método de extensión Where() en cualquier tipo que implemente IEnumerable<Person>.

En otras palabras, primero "compilaría" el AST en un Func<Person, boo>, y luego usaría LINQ to Objects para filtrar realmente mi colección. La compilación debe ser fácil porque su AST es una implementación del patrón de diseño compuesto. Cada nodo debe ser capaz de exponer el método Func<Person, bool> Compile().

Answer 4

No estoy familiarizado con el modelo de objeto que genera antlr pero asumiendo que es algo como esto:

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

Nota sin embargo, esto se evalúa la consulta con impaciencia, que no es óptimo. Pero debería darle una idea de cómo funcionaría la recursión.