Как оценить и обработать простое синтаксическое дерево строк в C #?

Question

У меня есть набор документов на основе токен-индекса, который предлагает метод запроса.Пользователь вручную (!) Вводит строку запроса, которую необходимо проанализировать и оценить.Корпус должен затем вернуть список всех документов, соответствующих заданной строке запроса.Язык запросов содержит простые логические операторы AND, NOT и OR, которые также могут быть расставлены по приоритетам в скобках.После некоторого исследования я уже использовал ANTLR для анализа данной строки запроса в синтаксическом дереве.

Например: запрос

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

транслируется в следующее синтаксическое дерево:

РЕДАКТИРОВАТЬ: Пожалуйста, смотрите правильный график в записи Барт Киерс (скопировано здесь):

Все узлы в дереве являются простыми строками и каждый узелзнает своих родителей и детей, но не своих братьев и сестер.Как вы можете видеть, грамматика ANTLR уже диктовала порядок, в котором должны выполняться операции: те, что находятся внизу дерева, идут первыми.

Так что мне, вероятно, нужно сделать рекурсивную (?) Оценку всех операндов в дереве.В общем, я могу выполнить простой поиск в моем корпусе, используя метод Get (строковый термин) для каждого листа в дереве (например, «Билл» или «Джон»).Get () возвращает список документов, содержащих термин в листе.Я также могу оценить родителя каждого листа, чтобы распознать возможный оператор NOT, который затем привел бы к списку результатов документов, не содержащих термин в листе (используя метод Not () вместо Get ()).

Операторы AND и OR должны быть преобразованы в вызовы методов, для которых требуется два параметра:

• И должен вызывать метод Intersect (list1, list2), который возвращает список документов, которые находятся в list1 AND вlist2.
• ИЛИ должен вызывать метод Union (list1, list2), который возвращает список документов, которые находятся либо в list1, либо в list2.

Параметры list1 и list2 содержатдокументы, которые я получил до использования Get () или Not ().

Мой вопрос: как я могу - семантически и синтаксически в C # - оценить все необходимые поисковые термины и использовать их для вызова правильных методов оператора в правильномпорядок?Интуитивно это звучит как рекурсия, но почему-то я не могу это представить - тем более что не все методы, которые нужно вызывать, имеют одинаковое количество параметров.Или, может быть, есть и другие способы сделать это?

Answer 1

Я ожидал, что будет сгенерировано следующее дерево:

(обратите внимание, что в вашем AST у узла OR есть 3 дочерних элемента)

В любом случае, если вы создали грамматику ANTLR, которая способна создать AST (в виде вашего исходного изображения или моего сообщения, опубликованного выше), это означает, что вы определили надлежащий приоритет оператора в своей грамматике. В этом случае вы не должны смущаться, выполняя заказ ваших операторов, поскольку ваше дерево уже требует, чтобы (John <- AND -> Jim) и (NOT -> Simon) были оценены первыми.

Не могли бы вы опубликовать грамматику ANTLR, над которой вы работали?

Кроме того, вы говорите о наборах, но в вашем примере показаны только отдельные значения, поэтому у меня сложилось впечатление, что ваш язык немного сложнее, чем вы показывали до сих пор. Возможно, вы могли бы объяснить свой фактический язык, а не глупую версию этого?

PS . Источник, который создал изображение, можно найти здесь: http://graph.gafol.net/elDKbwzbA (грамматика ANTLR также включена)

Answer 2

в псевдокоде

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 3

Я не знаком с объектной моделью, которую генерирует 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();
    }
}

Обратите внимание, однако, что он оценивает запрос с нетерпением, что не является оптимальным.Но это должно дать вам представление о том, как будет работать рекурсия.

Answer 4

Я не совсем уверен, что вы пытаетесь сделать, но я думаю, что превратить AST в Func<Person, bool>. Каждый конечный узел может быть преобразован в Func<Person, bool>, например, p => p.Name == "Bill", И, ИЛИ, и НЕ могут быть реализованы как функции более высокого порядка, например:

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

После того как вы все это сделали и свели AST в один Func<Person, bool>, вы можете передать его в качестве параметра методу расширения Where() для любого типа, который реализует IEnumerable<Person>.

Другими словами, я сначала «скомпилировал» AST в Func<Person, boo>, а затем использовал LINQ to Objects для фактической фильтрации моей коллекции. Компиляция должна быть простой, потому что ваш AST является реализацией шаблона проектирования Composite. Каждый узел должен иметь возможность выставлять метод Func<Person, bool> Compile().