एक पेड़ संरचना में पार्स स्ट्रिंग?

Question

मैं यह समझने की कोशिश कर रहा हूं कि इस प्रारूप में स्ट्रिंग को मनमाने ढंग से गहराई की डेटा संरचना जैसे पेड़ में कैसे पार्स करना है।

"{{Hello big|Hi|Hey} {world|earth}|{Goodbye|farewell} {planet|rock|globe{.|!}}}" 

[[["Hello big" "Hi" "Hey"] 
    ["world" "earth"]] 
[["Goodbye" "farewell"] 
    ["planet" "rock" "globe" ["." 
          "!"]]]] 

मैं कुछ नियमित इस के लिए अभिव्यक्ति के साथ खेल की कोशिश की है (# जैसा "{([^ {}] *)}"), लेकिन सब कुछ मैं कोशिश की है में पेड़ "समतल" लगता है सूचियों की एक बड़ी सूची। मैं गलत कोण से यह आ रहा था, या शायद एक regex सिर्फ नौकरी के लिए सही उपकरण नहीं है।

आपकी मदद के लिए धन्यवाद!

Answer 1

इस कार्य के लिए नियमित अभिव्यक्तियों का उपयोग न करें। एक व्याकरण (बीएनएफ या ईबीएनएफ) के साथ अपनी स्ट्रिंग का वर्णन करने के लिए एक आसान तरीका होगा और फिर व्याकरण के अनुसार स्ट्रिंग को पार्स करने के लिए एक पार्सर लिखें। आप अपने ईबीएनएफ और बीएनएफ से एक पार्स-पेड़ उत्पन्न कर सकते हैं और इसलिए आप स्वाभाविक रूप से पेड़ की संरचना के साथ समाप्त हो जाते हैं।

आप कुछ इस तरह के साथ शुरू कर सकते हैं:

element  ::= element-type, { ["|"], element-type } 
element-type ::= primitive | "{", element, "}" 
primitive ::= symbol | word 
symbol  ::= "." | "!" 
word   ::= character { character } 
character ::= "a" | "b" | ... | "z" 

नोट: मैं इस जल्दी में लिखा है, और इसलिए यह पूरी तरह से सही नहीं हो सकता। लेकिन यह आपको एक विचार देना चाहिए।

Answer 2

आप एक त्वरित हैक चाहते हैं:

• {साथ वर्ण [
• की जगह} की जगह
• की जगह के साथ वर्ण] | रिक्त स्थान के साथ वर्ण
• आशा है कि आप रिक्त स्थान के साथ इनपुट प्राप्त न करें।

read इसमें यह घोंसला वाले सरणी के रूप में आता है।

ps: मैं मानता हूं कि एक reg-ex यह नहीं कर सकता है।

पीएसएस: सेट * पढ़ने के लिए eval * गलत पर

Answer 3

आप बहुत दूर पाने के लिए नहीं जा रहा है एक भी नियमित अभिव्यक्ति के साथ पूरी बात मिलान करने के लिए कोशिश कर रहा है (यदि आप यह है चल स्वयं इनपुट नहीं करना चाहती) , चूंकि मेलिंग सबस्ट्रिंग पोजिशन की अधिकांश सूची में नियमित अभिव्यक्ति आउटपुट, पेड़ की तरह कुछ नहीं। आप एक लेक्सर या व्याकरण चाहते हैं जो इस तरह कुछ करता है:

टोकन में इनपुट को विभाजित करें - '{', '|', और 'world' जैसे परमाणु टुकड़े, फिर क्रम में उन टोकन को संसाधित करें। एक रूट नोड के साथ एक खाली पेड़ के साथ शुरू करें।

हर बार जब आप { पाते हैं, तो बच्चे नोड बनाएं और जाएं।

हर बार जब आप | पाते हैं, तो एक भाई नोड बनाएं और जाएं।

हर बार जब आप } पाते हैं, तो पैरेंट नोड तक जाएं।

हर बार जब आप कोई शब्द पाते हैं, तो उस शब्द को वर्तमान पत्ता नोड में रखें।

Answer 4

आप amotoen का उपयोग व्याकरण का निर्माण कर सकते हैं और इस पार्स:

(ns pegg.core 
    (:gen-class) 
    (:use 
    (com.lithinos.amotoen 
    core string-wrapper)) 
    (:use clojure.contrib.pprint)) 

(def input "{{Hello big|Hi|Hey} {world|earth}|{Goodbye|farewell} {planet|rock|globe{.|!}}}") 

(def grammar 
    { 
     :Start :List 
     :ws #"^[ \n\r\t]*" 
     :Sep "|" 
     :String #"^[A-Za-z !.]+" 
     :Item '(| :String :List) 
     :Items [:Item '(+ [:Sep :Item])] 
     :List [:ws "{" '(* (| :Items :Item)) "}" :ws] 
     }) 

(def parser (create-parser grammar)) 

(defn parse 
    [^String input] 
    (validate grammar) 
    (pprint (parser (wrap-string input)))) 

परिणाम:

pegg.core> (parse input) 
{:List [{:ws ""} "{" ({:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "Hello big"}} ([{:Sep "|"} {:Item {:String "Hi"}}] [{:Sep "|"} {:Item {:String "Hey"}}])]}) "}" {:ws " "}]}} {:Items [{:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "world"}} ([{:Sep "|"} {:Item {:String "earth"}}])]}) "}" {:ws ""}]}} ([{:Sep "|"} {:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "Goodbye"}} ([{:Sep "|"} {:Item {:String "farewell"}}])]}) "}" {:ws " "}]}}])]} {:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "planet"}} ([{:Sep "|"} {:Item {:String "rock"}}] [{:Sep "|"} {:Item {:String "globe"}}])]} {:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "."}} ([{:Sep "|"} {:Item {:String "!"}}])]}) "}" {:ws ""}]}}) "}" {:ws ""}]}}) "}" {:ws ""}]} 

पी.एस. यह मेरा पहला पेग व्याकरण है और यह बेहतर हो सकता है। यह भी देखें http://en.wikipedia.org/wiki/Parsing_expression_grammar