如何評估和處理C＃中的簡單字符串語法樹？

Question

我有一個基於標記索引的文檔提供查詢方法的語料庫。用戶手動（！）輸入一個需要解析和評估的查詢字符串。然後語料庫應該返回與給定查詢字符串匹配的所有文檔的列表。查詢語言的特點是簡單的布爾運算符AND，NOT和OR，它們也可以通過括號來區分優先級。 經過一番研究，我已經使用ANTLR將給定的查詢字符串解析到語法樹中。

例如：查詢

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

在下面的語法樹翻譯：

編輯：請參閱巴特煮布鍋後正確的圖形（複製到此處）：

樹中的所有節點都是簡單的字符串，並且每個節點都知道其母公司和但不是兄弟姐妹。 正如您所看到的，ANTLR語法已經決定了需要執行操作的順序：樹底部的順序首先出現。

所以我可能需要做的是recusively（？）評估樹中的所有操作數。 在一般情況下，我可以做使用樹中的每個葉子（如「條例」或「約翰」）的方法獲取（串項）我的文集一個簡單的搜索。 Get（）返回包含葉中詞的文檔列表。我也可以評估每一片葉子的父親，以識別一個可能的NOT運算符，然後這個運算符會導致不包含該葉子中詞語的結果列表（使用方法Not（）而不是Get（））。

AND和OR操作人員應被轉化爲其中需要兩個參數的方法調用：

• ，應該調用一個方法相交（列表1，列表2），它返回在列表1並在list2中的文件清單。
• OR應該調用的方法聯盟（列表1，列表2），它返回的是無論是在列表1或列表2的文件清單。

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

這是否幫助？

還是你希望優化評估的秩序，這可能有上寫的書...

Answer 2

我沒有料想到會生成以下樹：

（注意，在你的AST，該OR節點有3個孩子）

無論哪種方式，如果你有創建了能夠創建AST的ANTLR語法（無論是以原始圖像的形式，還是我上面發佈的形式），這意味着您已經在語法中定義了適當的運算符優先級。在這種情況下，您不應該對執行您的操作員的訂單感到困惑，因爲您的樹已經要求首先對(John <- AND -> Jim)和(NOT -> Simon)進行評估。

你可能會發布你一直在研究的ANTLR語法嗎？

另外，您正在討論集合，但在您的示例中，只顯示單個值，所以我得到的印象是您的語言比迄今爲止顯示的要複雜一些。也許你可以解釋你的實際語言，而不是一個虛擬的版本？

PS。創建圖像的源可以在這裏找到：http://graph.gafol.net/elDKbwzbA（ANTLR語法也包括）

Answer 3

我不完全確定你想要做什麼，但我想我會把AST變成Func<Person, bool>。每個葉節點可以evaulated到Func<Person, bool>例如p => p.Name == "Bill" AND，OR，並且不能被實現爲更高階的功能，例如：

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> ，那麼可以將該參數作爲參數傳遞給實現IEnumerable<Person>的任何類型的Where()擴展方法。

換句話說，我首先將AST「編譯」成Func<Person, boo>，然後使用LINQ to Objects實際過濾我的集合。編譯應該很容易，因爲AST是Composite設計模式的一個實現。每個節點應該能夠公開方法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(); 
    } 
} 

不過請注意這個期待評估查詢，這是不是最佳的。但它應該給你一個關於遞歸如何工作的想法。