如何在C#中评估和处理简单的字符串语法树？

Question

我有一个基于令牌索引的文档语料库,它提供了一种查询方法.用户手动(!)输入需要解析和评估的查询字符串.然后,语料库应返回与给定查询字符串匹配的所有文档的列表.查询语言具有简单的布尔运算符AND,NOT和OR,它们也可以通过括号进行优先级排序.经过一些研究,我已经使用ANTLR将给定的查询字符串解析为语法树.

例如:查询

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

在以下语法树中翻译:

编辑:请参阅Bart Kiers帖子中的正确图表(复制到此处):

树中的所有节点都是简单的字符串,每个节点都知道它的父节点和子节点,但不知道它的兄弟节点.正如您所看到的,ANTLR语法已经规定了操作需要执行的顺序:树底部的那些首先出现.

所以我可能需要做的是重复(？)评估树中的所有操作数.一般来说,我可以使用树中每个叶子的方法Get(字符串术语)对我的语料库进行简单搜索(如"Bill"或"John").Get()返回包含叶子中术语的文档列表.我还可以评估每个叶子的父级以识别可能的NOT运算符,然后该运算符将导致不包含叶子中的术语的文档的结果列表(使用方法Not()而不是Get()).

应该将AND和OR运算符转换为需要两个参数的方法调用:

• AND应该调用一个方法Intersect(list1,list2),它返回list1和list2中的文档列表.
• 或者应该调用一个方法Union(list1,list2),它返回list1或list2中的文档列表.

参数list1和list2包含我在使用Get()或Not()之前收到的文档.

我的问题是:我如何 - 在C#语义和语法上 - 评估所有必要的搜索术语并使用它们以正确的顺序调用正确的运算符方法？直觉上它听起来像递归,但不知何故我无法想象 - 特别是因为并非所有需要调用的方法都具有相同数量的参数.或者是否有其他方法可以实现这一目标？

Answer 1

在伪代码中

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

这有帮助吗？

或者您是否希望优化评估顺序，这可能有相关书籍......