एक सार या ठोस वाक्यविन्यास पेड़ का उपयोग कब करें?

Question

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

this question से यह एक पार्सर एएसटी का निर्माण करेगा। एएसटी में केवल कोड को निष्पादित करने के लिए आवश्यक है, इसलिए ब्रांड्स की तरह चीजें अनावश्यक होंगी क्योंकि ऑपरेटर प्राथमिकता एएसटी में बनाई गई है। एक एएसटी शायद सभी एक कंपाइलर जरूरत है।

लेकिन एक भाषा से दूसरे भाषा में कोड बदलने के बारे में क्या? एक मेक-अप भाषा (व्याकरण) या मौजूदा व्याकरण लेना और उसे दूसरे में परिवर्तित करना जहां ऑपरेटर प्राथमिकता नियम भिन्न हो सकते हैं या नहीं भी हो सकते हैं? ऑपरेटर प्राथमिकता "सीएसटी में" निर्मित "है?

एक उदाहरण के रूप में कहता है कि मैंने एक भाषा बनाई है और इसे PHP कोड में अनुवाद करना चाहता हूं। अधिकांश भाषाओं में टर्नरी ऑपरेटर के पास दाएं से बाएं सहयोगीता होती है। PHP गलत तरीके से बाएं से दाएं सहयोगीता का उपयोग करता है (see more about this here)। मैं "मेरी भाषा" को दाएं से बाएं उपयोग करना चाहता हूं लेकिन परिणामी PHP कोड को PHP में सही परिणाम प्राप्त करने के लिए कोष्ठक लागू करना है (link to Wikipedia के साथ, परिणाम "घोड़े" के बजाय "ट्रेन" होना आवश्यक है)।

तो भाषा अनुवाद के लिए एक सीएसटी बेहतर होगा? क्या ऑपरेटर प्राथमिकता आमतौर पर सीएसटी में बनाई जाती है? क्या बीच में कुछ भी है? क्या दोनों पेड़ों की तुलना एक साधारण बीजगणित समीकरण के साथ कर रहे हैं? एक टर्नरी ऑपरेटर को चित्रित करने वाले कोई भी उदाहरण? यह अधिक उपयुक्त एक का उपयोग कब है:

क्या मैं यह पता लगाने की कोशिश कर रहा हूँ है (?। "ट्रांसकोड" "प्रोग्रामिंग भाषा अनुवाद" के लिए सही शब्द एक गूगल खोज मीडिया परिवर्तित करने को लाता है) दूसरे पर?

Answer 1

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

तो आपकी समस्या एएसटी में नहीं है। यह समान (टर्नरी) ऑपरेटरों का उपयोग करके दूसरी भाषा में पैदा हो रहा है जिसका प्राथमिकता अलग है।

कोड जनरेशन में यह एक पुरानी समस्या है: लक्ष्य के ऑपरेटर स्रोत के ऑपरेटरों से काफी मेल नहीं खाते हैं, और इसलिए आउटपुट एक-एक नहीं हो सकता है। आपके मामले में, आप मूल शब्दावली क्या हासिल करने के लिए आदेश को नियंत्रित करने के लिए उनके चारों ओर कोष्ठक के साथ PHP टर्नरी ऑपरेटरों को उत्पन्न करके समस्या को हल करने में सक्षम होना चाहिए, इसलिए यह एक बड़ी समस्या नहीं है।

सामान्य रूप से, वांछित परिणाम प्राप्त करने वाले कोड के अनुक्रम उत्पन्न करना बहुत जटिल हो सकता है, और ऐसा करने के कई तरीके हैं। यही कारण है कि संकलक पुस्तकें पतली की बजाय मोटी होती हैं। ऐसा लगता है कि आप "एएसटी प्राप्त करें, एएसटी चलें, थूक कोड" पर पूरी तरह से बस गए हैं; यह लगभग एक ऑन-द-फ्लाई कोड जनरेटर है। और यदि आप परवाह नहीं है कि जेनरेट किया गया कोड विशेष रूप से अच्छा है, और लक्ष्य भाषा स्रोत भाषा के बहुत करीब है, तो यह पर्याप्त रूप से काम करता है।

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

इस विचार पर एक भिन्नता स्रोत-से-स्रोत प्रोग्राम रूपांतरण है। यह मानचित्र लक्ष्य कोड में "सीधे" स्रोत कोड में अंतर्निहित होते हैं, हालांकि आमतौर पर एएसटी पर परिचालन करके दृश्यों के पीछे किया जाता है क्योंकि अनपेक्षित प्रोग्रामिंग भाषा टेक्स्ट मिलान करना मुश्किल होता है। हमारे DMS Software Reengineering Toolkit इस तरह के सिस्टम का एक उदाहरण है। इस तरह के एक उपकरण के साथ, आप स्रोत भाषा में पैटर्न लिखते हैं (जो एक पार्स पेड़ के खिलाफ पूरी तरह से मेल खाते हैं), और लक्ष्य लैंगेज में प्रासंगिक पैटर्न (स्पष्ट रूप से लक्ष्य भाषा एएसटी का उत्पादन)। आप जटिल स्रोत या लक्ष्य संरचनाएं लिख सकते हैं जो उपरोक्त डेटा प्रवाह ग्राफ के प्रभाव का अधिक प्रभाव दे रहे हैं। पोस्ट-पीढ़ी के अनुकूलन में नियमों को फिर से लिखना शामिल है जो लक्षित कोड को लक्ष्य कोड में बदल देते हैं।

नीचे पंक्ति: एएसटी होने तक वास्तव में पर्याप्त नहीं है जब तक कि आपका अनुवाद वास्तव में छोटा न हो। आप इस SO उत्तर में जो चाहिए उसे इसके बारे में अधिक पढ़ सकते हैं: https://stackoverflow.com/a/3460977/120163

चेतावनी: जोरदार राय निम्नानुसार है।

पुन "ट्रांसकोडर": मैं "संकलन", "अनुवाद" या "स्रोत-से-स्रोत" कंपाइलर शब्द को अधिक पसंद करता हूं। मैं लगभग 40 वर्षों के लिए प्रोग्राम विश्लेषण और हेरफेर उपकरण बना रहा हूं। जब तक मुझे इस SO प्रश्न का सामना नहीं हुआ तब तक मैंने "ट्रांसकोडर" शब्द कभी नहीं सुना होगा: Experience migrating legacy Cobol/PL1 to Java और आईएमएचओ का वर्णन करने वाली प्रतिक्रिया एनएसीए नामक वास्तव में भयानक कोड अनुवाद योजना है। मैंने सुना है कि यह शब्द कर्षण प्राप्त कर रहा है; मुझे नहीं पता कि हमें एक और शब्द का आविष्कार क्यों करना पड़ा जब हमारे पास पर्याप्त रूप से पर्याप्त लोग हों। आम तौर पर यह एक उच्च पुजारी का आविष्कार करने वाले किसी का संकेत है; "आइए एक चमकदार नए शब्द का आविष्कार करें ताकि लोग वास्तव में समझ सकें कि हम क्या कर रहे हैं"। मुझे इस शब्द को इस तरह के वास्तव में भयानक अनुवादों में छोड़कर खुशी हुई।