लाइब्रेरी को नोड पेड़ बदलने के लिए लाइब्रेरी

Question

मैं दोहराए गए स्पेगेटी कोड का एक समूह लिखने के बिना एक पेड़ के सामान्य परिवर्तन को व्यक्त करने में सक्षम होना चाहता हूं। क्या इस समस्या से निपटने के लिए कोई पुस्तकालय हैं? मेरी लक्षित भाषा पायथन है, लेकिन जब तक यह पाइथन को बंदरगाह के लिए संभव हो, तब तक मैं अन्य भाषाओं को देखूंगा।

उदाहरण: मैं इस नोड पेड़ को बदलने के लिए करना चाहते हैं: यह एक में (बहाना कृपया S-expressions)

(A (B) (C) (D)) 

:

(C (B) (D)) 

जब तक अभिभावक के रूप में एक और दूसरा है पूर्वज सी है, संदर्भ के बावजूद (अधिक माता-पिता या पूर्वजों हो सकते हैं)। मैं इस परिवर्तन को एक सरल, संक्षिप्त, और पुनः उपयोग करने योग्य तरीके से व्यक्त करना चाहता हूं। बेशक यह उदाहरण बहुत विशिष्ट है। कृपया सामान्य मामले को संबोधित करने का प्रयास करें।

संपादित करें: RefactoringNG ऐसी चीज है जिसे मैं ढूंढ रहा हूं, हालांकि यह समस्या को हल करने के लिए एक पूरी तरह से नया व्याकरण प्रस्तुत करता है, जिसे मैं टालना चाहता हूं। मैं अभी भी अधिक और/या बेहतर उदाहरण ढूंढ रहा हूं।

---

पृष्ठभूमि:

मैं tokenized पेड़ अभ्यावेदन में अजगर और चीता (मत पूछो!) फ़ाइलों को कनवर्ट करने में सक्षम हूँ, और बदले में lxml पेड़ में उन कन्वर्ट। मैं स्वचालित रीफैक्टरिंग को लागू करने के लिए पेड़ को फिर से व्यवस्थित करने और परिणामों को लिखने की योजना बना रहा हूं। एक्सएसएलटी एक्सएमएल को फिर से लिखने के लिए मानक उपकरण प्रतीत होता है, लेकिन वाक्यविन्यास भयानक है (मेरी राय में, जाहिर है) और हमारी दुकान में कोई भी इसे समझ नहीं पाएगा।

मैं कुछ फ़ंक्शंस लिख सकता हूं जो मेरे रिफैक्टरिंग को लागू करने के लिए केवल lxml विधियों (.xpath और ऐसे) का उपयोग करते हैं, लेकिन मुझे चिंता है कि मैं उद्देश्य-निर्मित स्पेगेटी कोड का एक समूह के साथ हवादार हो जाऊंगा जो कि नहीं हो सकता फिर से इस्तेमाल किया।

Answer 1

क्या तुम सच में IMHO चाहते एक program transformation system जो आप पार्स और सीधे पुनर्लेखन व्यक्त करने के लिए पैटर्न स्रोत कोड (और यहां तक ​​कि लक्ष्य भाषा) सतह वाक्य रचना में व्यक्त का उपयोग कर कोड को बदलने के लिए अनुमति देता है,।

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

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

हमारे DMS Software Reengineering Toolkit में इन सभी क्षमताओं (पार्सिंग, फ्लो विश्लेषण, पैटर्न मिलान/पुनर्लेखन, सुंदर प्रिंटिंग), और robust parsers पाइथन सहित कई भाषाओं के लिए है।(हालांकि इसमें सी, कोबोल, जावा के लिए फ्लोर विश्लेषण क्षमता है, यह पाइथन के लिए तत्काल नहीं है। लेकिन फिर, आपने कहा कि आप संदर्भ के बावजूद परिवर्तन करना चाहते हैं)।

अजगर वाक्य रचना अपने उदाहरण के करीब पर डीएमएस में आपका रीराइट व्यक्त करने के लिए (जो अजगर नहीं है?)

domain Python; 

    rule revise_arguments(f:IDENTIFIER,A:expression,B:expression, 
            C:expression,D:expression):primary->primary 
    = " \f(\A,(\B),(\C),(\D)) " 
    -> " \f(\C,(\B),(\D)) "; 

अंकन ऊपर डीएमएस नियम पुनर्लेखन भाषा (RSL) है। "..." मेटाक्वाट्स हैं जो अलग-अलग पायथन सिंटैक्स (उन उद्धरणों के अंदर, डीएमएस जानते हैं कि यह डोमेन नोटेशन घोषणा के कारण पायथन है) डीएमएस आरएसएल भाषा से। \ N मेटा उद्धरण के अंदर नियम पैरामीटर सूची में परिभाषित नामित nonterminal प्रकार के वाक्यविन्यास परिवर्तनीय प्लेसहोल्डर्स को संदर्भित करता है। हां, (...) मेटाक्वाट्स के अंदर पाइथन() हैं ... जहां तक ​​डीएमएस का संबंध है, वे सिंटैक्स पेड़ों में मौजूद हैं, क्योंकि वे शेष भाषा की तरह हैं, सिर्फ सिंटैक्स हैं।

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

इस नियम के साथ

, डीएमएस की तरह

 foobar(2+3,(x-y),(p),(baz())) 

निर्माण (अपने अजगर पार्सर का उपयोग) अजगर पार्स सकता है एक एएसटी, (पार्स करने वाली एएसटी) कि एएसटी के खिलाफ नियम से मेल, एक और एएसटी करने के लिए इसे फिर से लिखने इसी करने के लिए:

 foobar(p,(x-y),(baz())) 

और उसके बाद सतही वाक्यविन्यास (वैध) पायथन वापस सुंदर प्रिंट करें।

आप अपने उदाहरण का इरादा तो लिस्प कोड पर एक परिवर्तन होने के लिए आपको चाहते डीएमएस (मुश्किल नहीं निर्माण करने के लिए है, लेकिन हम इस बात के लिए बहुत कॉल की जरूरत नहीं है) के लिए एक लिस्प व्याकरण की जरूरत है, और इसी सतह बारे में वाक्य रचना:

domain Lisp; 

    rule revise_form(A:form,B:form, C:form, D:form):form->form 
    = " (\A,(\B),(\C),(\D)) " 
    -> " (\C,(\B),(\D)) "; 

आप Algebra as a DMS domain को देखकर इस के लिए एक बेहतर महसूस कर सकते हैं।

यदि आपका लक्ष्य पाइथन में यह सब लागू करना है ... मुझे बहुत मदद नहीं है। डीएमएस एक बहुत बड़ी प्रणाली है, और यह दोहराने के लिए बहुत प्रयास होगा।

Answer 2

चलिए इसे पायथन कोड में आज़माएं। मैंने पत्तियों के लिए तारों का उपयोग किया है, लेकिन यह किसी भी वस्तु के साथ काम करेगा।

def lift_middle_child(in_tree): 
    (A, (B,), (C,), (D,)) = in_tree 

    return (C, (B,), (D,)) 

print lift_middle_child(('A', ('B',), ('C',), ('D',))) # could use lists too 

पेड़ परिवर्तन इस तरह की आम तौर पर बेहतर एक कार्यात्मक शैली में किया जाता है - अगर आप इन कार्यों में से एक गुच्छा बनाने के लिए, आप उन्हें स्पष्ट लिखें, या में उनके साथ काम करने के लिए एक संरचना समारोह बना सकते हैं एक बिंदु से मुक्त अंदाज।

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

यहाँ कार्रवाई में कोड है: http://ideone.com/02Uv0i

अब, यहाँ बच्चों को उल्टा करने के एक समारोह है, और है कि का उपयोग कर और ऊपर समारोह, एक लिफ्ट और उल्टा करने के लिए:

def compose2(a,b): # might want to get this from the functional library 
    return lambda *x: a(b(*x)) 

def compose(*funcs): #compose(a,b,c) = a(b(c(x))) - you might want to reverse that 
    return reduce(compose2,funcs) 

def reverse_children(in_tree): 
    return in_tree[0:1] + in_tree[1:][::-1] # slightly cryptic, but works for anything subscriptable 

lift_and_reverse = compose(reverse_children,lift_middle_child) # right most function applied first - if you find this confusing, reverse order in compose function. 

print lift_and_reverse(('A', ('B',), ('C',), ('D',)))