C# içinde basit bir dize sözdizimi ağacı nasıl değerlendirilir ve işlenir?

Question

Bir sorgu yöntemi sunan bir token-indeks tabanlı belgeler kümesi var. Kullanıcı (!) Elle ayrıştırılması ve değerlendirilmesi gereken bir sorgu dizesi girer. Korpus, verilen sorgu dizesiyle eşleşen tüm belgelerin bir listesini döndürmelidir. Sorgu dili, parantez ile önceliklendirilebilen basit boole işleçleri AND, NOT ve OR'yi içerir. Bazı araştırmalardan sonra, belirli bir sorgu dizesini bir sözdizimi ağacına ayrıştırmak için ANTLR kullanmıştım. Örneğin

:

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

aşağıdaki sözdizimi ağacındaki çevrilmiştir sorgusu:

DÜZENLEME:

: Bart Kiers yayınında doğru grafiği (burada kopyalanan) bakın

Ağdaki tüm düğümler basit dizelerdir ve her düğüm ebeveynini bilir ve çocuklar değil, kardeşleri. Gördüğünüz gibi, ANTLR dilbilgisi, işlemlerin yürütülmesinin gerektiği sıralamayı zaten belirledi: ağacın altındakiler önce gelir.

Bu yüzden muhtemelen yapmam gereken şey, (?) Ağacındaki tüm işlenenleri değerlendirmek. Genel olarak, (Yaprak "ya da" John "gibi) ağacındaki her yaprak için bir yöntem (dize terimi) kullanarak benim corpus üzerinde basit bir arama yapabilirsiniz. Get(), yapraktaki terimi içeren belgelerin bir listesini döndürür. Ayrıca her bir yaprağın ebeveyni, olası bir NOT işlecini tanımak için değerlendirebilirim. Bu, daha sonra yapraktaki terimi içermeyen bir sonuç listesine (Get() yöntemi yerine Not() yöntemini kullanarak) yollayacaktır. Liste1 AND list2 olan belgelerin listesini döndürür

• VE yöntemidir Intersect'i (list1, list2) çağırmalıdır:

  AND ve OR operatörü iki parametre ihtiyaç yöntem çağrıları haline getirilmelidir .

• VEYA liste1 VEYA list2 listesindeki belgelerin listesini veren bir yöntem (liste1, liste2) çağırmalıdır.

parametreleri list1 ve list2 I() veya değil() Get kullanmadan önce alınan belgeleri içermektedir.

Soruma şu sorularım var: C# içinde semantik ve sözdizimsel olarak nasıl olabilir - gerekli tüm arama terimlerini değerlendirebilir ve doğru sırada doğru operatör yöntemlerini çağırmak için bunları kullanabilirler? Sezgisel olarak özyinelemeye benziyor ama bir şekilde onu görüntüleyemiyorum - özellikle çağrılması gereken tüm yöntemlerin aynı miktarda parametresi olmadığı için. Ya da bunu gerçekleştirmek için belki de başka yollar var mı? Sözde Kod

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

yılında

Answer 1

bu yardım ediyor mu?

Ya da muhtemelen üzerinde yazılmış kitapların bulunduğu değerlendirme sırasını optimize etmek mi istiyorsunuz?

Aşağıdaki ağaç üretilecek bekleniyor olurdu

Answer 2

:

varsa, iki yöntemde

(OR düğüm 3 çocuk babasıdır sizin AST unutmayın)

bir AST (orijinal görüntünüzde veya üstte yer alan benim formda olsun) oluşturabilen bir ANTLR dilbilgisi yarattı, bu sizin dilbilginizde doğru operatör önceliğini tanımladığınız anlamına gelir. Bu durumda, ağacınız zaten (John <- AND -> Jim) ve (NOT -> Simon)'un ilk önce değerlendirileceğini bildirdiği için operatörlerin sırasını yürütmekle karıştırılmamalıdır.

Üzerinde çalıştığınız ANTLR dilbilgisini yazabilir misiniz?

Ayrıca, kümeler hakkında konuşuyorsunuz, ancak örneğinizde, yalnızca tek değerler gösteriliyor, bu yüzden, dilinizin gösterdiğinizden biraz daha karmaşık olduğu izlenimini ediniyorum. Belki de gerçek dilinizi, bunun aşağılık bir sürümü yerine açıklayabilirsiniz.

PS. Görüntüyü oluşturan kaynak şu adreste bulunabilir: http://graph.gafol.net/elDKbwzbA (ANTLR dilbilgisi de dahil edilmiştir)

Answer 3

Ne yapmaya çalıştığınızdan tam olarak emin değilim, ama AST'yi Func<Person, bool>'a dönüştürürüm. Her yaprak düğüm örneğin p => p.Name == "Bill" bir Func<Person, bool> için değerlendirilmektedir edilebilir AND, OR ve örneğin yüksek mertebeden fonksiyonları olarak uygulanabilir DEĞİL:

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

Bütün bu yapılan ve tek Func<Person, bool> içine AST çöktü sonra IEnumerable<Person>'u uygulayan herhangi bir türde Where() uzantı yöntemine parametre olarak iletebilirsiniz. Başka bir deyişle, ilk önce AST'yi Func<Person, boo>'a "derlerim" ve daha sonra koleksiyonumu filtrelemek için LINQ'u Nesneler'e kullanırdım. Derleme kolay olmalı çünkü AST'niz Kompozit tasarım modelinin bir uygulamasıdır. Her düğüm, Func<Person, bool> Compile() yöntemini ortaya çıkarabilmelidir.

Answer 4

Ben ANTLR böyle onun bir şey varsayarak ama üretir nesne modeli aşina değilim:

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

Not ancak bu optimal değildir, hangi hevesle sorgusunu değerlendirir. Fakat bu, özyinenin nasıl işe yarayacağı hakkında bir fikir vermelidir.