सी # में एक साधारण स्ट्रिंग वाक्यविन्यास-पेड़ का मूल्यांकन और प्रक्रिया कैसे करें?

Question

मेरे पास टोकन-इंडेक्स आधारित दस्तावेज़ों का एक कॉर्पस है जो एक क्वेरी विधि प्रदान करता है। उपयोगकर्ता मैन्युअल रूप से (!) एक क्वेरी स्ट्रिंग में प्रवेश करता है जिसे पार्स और मूल्यांकन करने की आवश्यकता होती है। कॉर्पस को दिए गए क्वेरी स्ट्रिंग से मेल खाने वाले सभी दस्तावेज़ों की एक सूची वापस करनी चाहिए। क्वेरी भाषा में सरल बूलियन ऑपरेटर और, नहीं और OR शामिल हैं जिन्हें कोष्ठक द्वारा प्राथमिकता भी दी जा सकती है। कुछ शोध के बाद मैंने एक वाक्यविन्यास पेड़ में दिए गए क्वेरी स्ट्रिंग को पार्स करने के लिए पहले ही एएनटीएलआर का उपयोग किया था।

उदाहरण के लिए: क्वेरी

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

निम्न सिंटैक्स पेड़ में अनुवाद किया है:

संपादित करें:

: कृपया बार्ट Kiers पोस्ट में सही ग्राफ (यहां कॉपी) को देखने के

पेड़ में सभी नोड सरल तार हैं और प्रत्येक नोड अपने माता-पिता को जानता है और बच्चे लेकिन इसके भाई बहन नहीं। जैसा कि आप देख सकते हैं, एएनटीएलआर व्याकरण पहले से ही उस क्रम को निर्धारित करता है जिसमें संचालन को निष्पादित करने की आवश्यकता होती है: पेड़ के नीचे वाले लोग पहले आते हैं।

तो मुझे शायद जो करना है वह पेड़ में सभी ऑपरेटरों का मूल्यांकन (?) है। सामान्य रूप से, मैं पेड़ में प्रत्येक पत्ते (जैसे "बिल" या "जॉन") के लिए विधि (स्ट्रिंग टर्म) विधि का उपयोग करके अपने कॉर्पस पर एक साधारण खोज कर सकता हूं। प्राप्त करें() पत्ते में शब्द युक्त दस्तावेजों की एक सूची देता है। मैं एक संभावित नोट ऑपरेटर को पहचानने के लिए प्रत्येक पत्ते के माता-पिता का भी मूल्यांकन कर सकता हूं जो तब कागजात में शब्द (जिसमें विधि() के बजाय विधि() का उपयोग नहीं कर रहा है, दस्तावेजों की परिणाम सूची का नेतृत्व करेगा।

• और एक विधि इंटरसेक्ट (List1, List2) बुलाना चाहिए जो कि List1 में और List2 में हैं दस्तावेजों की एक सूची देता है:

  AND और OR ऑपरेटर विधि कॉल जो दो पैरामीटर की जरूरत के रूप में तब्दील किया जाना चाहिए ।

• या एक विधि संघ (सूची 1, सूची 2) को कॉल करना चाहिए जो दस्तावेजों की एक सूची देता है जो सूची 1 या सूची 2 में हैं।

पैरामीटर सूची 1 और सूची 2 में प्राप्त() या नहीं() का उपयोग करने से पहले प्राप्त दस्तावेज़ शामिल हैं।

मेरा प्रश्न है: मैं कैसे कर सकता हूं - सी # में अर्थात् और वाक्य रचनात्मक रूप से - सभी आवश्यक खोज शब्दों का मूल्यांकन कैसे कर सकता हूं और सही क्रम में सही ऑपरेटर विधियों को कॉल करने के लिए उनका उपयोग कर सकता हूं? सहजता से यह रिकर्सन की तरह लगता है लेकिन किसी भी तरह से मैं इसे चित्रित नहीं कर सकता - खासकर जब सभी विधियों को कॉल करने की आवश्यकता नहीं है, तो समान मात्रा में पैरामीटर हैं। या क्या इसे पूरा करने के लिए शायद पूरी तरह से अन्य तरीके हैं?

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

मैं अपेक्षा की होगी निम्नलिखित पेड़ उत्पन्न हो रहे हैं:

(ध्यान दें कि आपके एएसटी में, OR नोड 3 बच्चे हैं)

किसी भी तरह से, अगर आपके पास एक एएनटीएलआर व्याकरण बनाया जो एएसटी (चाहे आपकी मूल छवि के रूप में, या ऊपर पोस्ट किया गया है) बनाने में सक्षम है, इसका मतलब है कि आपने अपने व्याकरण में उचित ऑपरेटर प्राथमिकता को परिभाषित किया है। उस स्थिति में, आपको अपने ऑपरेटरों के आदेश को निष्पादित करने में भ्रमित नहीं होना चाहिए क्योंकि आपका पेड़ पहले से ही (John <- AND -> Jim) और (NOT -> Simon) का मूल्यांकन करना है।

आप शायद ANTLR व्याकरण आप पर काम कर रहा है पोस्ट कर सकते हैं?

इसके अलावा, आप सेट के बारे में बात कर रहे हैं, लेकिन अपने उदाहरण में, केवल एकल मान दिखाए जाते हैं, तो मैं छाप अपनी भाषा में थोड़ा और अधिक जटिल की तुलना में आप अब तक दिखाया है है मिलता है। शायद आप इसके वास्तविक भाषा को इसके बदले हुए संस्करण के बजाय समझा सकते हैं?

पुनश्च। जिस स्रोत ने छवि बनाई है वह यहां पाया जा सकता है: http://graph.gafol.net/elDKbwzbA (एएनटीएलआर व्याकरण भी शामिल है)

Answer 3

मुझे बिल्कुल यकीन नहीं है कि आप क्या करने की कोशिश कर रहे हैं, लेकिन मुझे लगता है कि मैं एएसटी को Func<Person, bool> में बदल दूंगा। प्रत्येक पत्ती नोड उदाहरण p => p.Name == "Bill" के लिए एक Func<Person, bool> को evaulated जा सकता है और, या, और उदाहरण के लिए उच्च आदेश कार्यों के रूप में नहीं लागू किया जा सकता:

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

एक बार जब आप यह सब किया है और एक भी Func<Person, bool> में अपने एएसटी ढह गए हैं , IEnumerable<Person> लागू करने वाले किसी भी प्रकार पर Where() विस्तार विधि के पैरामीटर के रूप में आप इसे पास कर सकते हैं।

दूसरे शब्दों में, मैं पहले एएसटी को Func<Person, boo> में संकलित करता हूं, और उसके बाद वास्तव में मेरे संग्रह को फ़िल्टर करने के लिए ऑब्जेक्ट्स के लिए LINQ का उपयोग करता हूं। संकलन आसान होना चाहिए क्योंकि आपका एएसटी समग्र डिजाइन पैटर्न का कार्यान्वयन है। प्रत्येक नोड विधि 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(); 
    } 
} 

नोट लेकिन इस उत्सुकता से जिज्ञासा का भी मूल्यांकन, जो इष्टतम नहीं है। लेकिन यह आपको एक विचार देना चाहिए कि कैसे रिकर्सन काम करेगा।