रेगेक्स?

Question

क्या वृक्ष संरचनाओं को खोजने और संशोधित करने के लिए नियमित अभिव्यक्ति समकक्ष हैं? संक्षिप्त मिनी-भाषाएं (जैसे पर्ल रेगेक्स) जो मैं ढूंढ रहा हूं।

यहां एक उदाहरण है जो मैं जो खोज रहा हूं उसे स्पष्ट कर सकता हूं।

<root> 
    <node name="1"> 
    subtrees .... 
    </node> 
    <node name="2"> 
    <node name="2.1"> 
    data 
    </node> 
    other subtrees... 
    </node> 
</root> 

कोई कार्रवाई है कि ऊपर पेड़ पर संभव हो जाएगा "नोड 2.1 पर कदम सबट्री में नोड 1. पर सबट्री" है आपरेशन के परिणाम कुछ लग सकता है की तरह ..

<root> 
    <node name="1"> 
    subtrees .... 
    <node name="2.1"> 
    data 
    </node> 
    </node> 
    <node name="2"> 
    other subtrees... 
    </node> 
</root> 

खोजें और कम से कम 2 बच्चों के साथ सभी नोड्स लगता है जैसे कार्य की जगह, अगर सभी नोड्स जिसका डेटा "एक" और साथ "बी" से बदलने के साथ शुरू होता लगता है subtrees कम से कम 2 अन्य भाई बहन, आदि समर्थित होना चाहिए।

स्ट्रिंग्स के लिए, जहां स्ट्रिंग की लंबाई में एकमात्र आयाम है, हम नियमित अभिव्यक्तियों का उपयोग करके उपरोक्त कई ऑपरेशन (या उनके 1 डी समकक्ष) कर सकते हैं। मुझे आश्चर्य है कि पेड़ों के लिए समकक्ष हैं या नहीं। (एक एकल regex के बजाय, आपको परिवर्तन नियमों का एक सेट लिखने की आवश्यकता हो सकती है, लेकिन यह ठीक है)।

मैं जानना चाहता हूं कि कुछ सरल मिनी भाषा है (regex per.se नहीं, लेकिन कुछ ऐसा है जो पुस्तकालयों के माध्यम से रेगेक्स के रूप में सुलभ है ..)। इन परिचालनों को करने के लिए? अधिमानतः, एक अजगर पुस्तकालय के रूप में।

Answer 1

स्टैनफोर्ड से टीएसर्जन और ट्रेगेक्स ऐसा करने में सक्षम है। आप http://nlp.stanford.edu/software/tregex.shtml

Answer 2

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

निश्चित रूप से, आप किसी दिए गए मान के साथ नोड की खोज कर सकते हैं, लेकिन उदाहरण के लिए, यदि आप अपने माता-पिता को नहीं जानते हैं तो एक नोड को हटा दें जो एक पत्ता नहीं है?

और यहां तक ​​कि यदि आप नोड द्वारा आपूर्ति की गई जानकारी के माध्यम से माता-पिता को जानते हैं, तो आप बाएं सबट्री का न्यूनतम निर्धारण कैसे निर्धारित करते हैं, इसे हटाते हैं और इसे नोड में रखते हैं?

मुझे लगता है कि आप एफएसए के लिए बहुत कुछ पूछ रहे हैं।

Answer 3

मुझे ऐसा कोई सामान्य उद्देश्य नहीं है जो ऐसा कर सकता है, लेकिन ऐसा लगता है कि आप XPath जैसे कुछ ढूंढ रहे हैं।

Answer 4

पैटर्न आधारित पेड़ पुनर्लेखन के लिए TXL है।

ट्री पैटर्न के साथ फिर से लिखने भी नीचे से ऊपर पेड़ फिर से लिखना, गूगल BURS या BURG के साथ इस तरह ANTLR

कोड पीढ़ी के रूप में पार्सर उपकरणकिटें के साथ किया जाता है।

Answer 5

This लेख रिकर्सिव पर्ल नियमित अभिव्यक्तियों के बारे में कुछ स्वादिष्ट संकेत देता है, लेकिन ईमानदारी से पेड़ संरचना को इस तरह से देखना दुर्लभ है।

अधिक आम तौर पर, एक राज्य मशीन स्टाइल पार्सर लिखता है, जो वृक्ष में प्रत्येक विशेष नोड को पार्स करने के लिए रेगेक्स का उपयोग कर सकता है।

Expat शायद देखने के लिए एक अच्छा उदाहरण है।

Answer 6

पैटर्न मिलान, स्कैला, एफ #, एरलांग और हास्केल जैसी भाषाओं द्वारा प्रदान की गई (मुझे यकीन है कि और भी है) को रिकर्सन के साथ उपयोग किए जाने पर पेड़ों, एएसपी जैसे डेटा संरचनाओं में संक्षेप में हेरफेर करने के लिए डिज़ाइन किया गया है।

here स्कैला में पैटरेन मिलान क्या कर सकता है इसका एक बहुत ही उच्च स्तर का दृश्य है। दिखाए गए उदाहरण वास्तव में पैटर्न मिलान न्याय नहीं करते हैं।

विकिपीडिया में पैटर्न मिलान के कुछ संदर्भ भी हैं। Here और here।

Answer 7

मुझे कुछ आश्चर्य है कि XSLT उत्तर के रूप में नहीं आया है। अनुमोदित, मुझे नहीं लगता कि यह एक विशेष रूप से सुरुचिपूर्ण भाषा है, और अधिकांश अस्तित्व के समाधान पैटर्न मिलान के बजाय प्रक्रियात्मक दृष्टिकोण का पक्ष लेते हैं, और यह अंधेरे से लागू होने से एक शक्तिशाली बुरे प्रतिनिधि को प्राप्त कर लिया गया है क्योंकि यह एक्सएमएल एक्सएमएल पर लागू किया जा रहा है - लेकिन अन्यथा यह बिल फिट बैठता है। दयालुता इसके कैननिकल प्रतिनिधित्व इतनी वर्बोज़ है, हालांकि ...