एक सार सिंटेक्स वृक्ष क्या है/क्या इसकी आवश्यकता है?

Question

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

स्रोत कोड -> लेक्सिकल विश्लेषण -> सार सिंटेक्स ट्री -> सिंटेक्टिक विश्लेषण -> अर्थात् विश्लेषण -> कोड जनरेशन -> निष्पादन योग्य कोड।

(मुझे पता है कि अधिक उत्पादन और निष्पादन योग्य कोड कोड करने के लिए है, लेकिन मुझे लगता है कि अब तक अभी तक नहीं मिला है :)

और उस ज्ञान के साथ, मैं एक बहुत ही बुनियादी lexer बना लिया है (जावा में) लेने के लिए स्रोत फ़ाइल से इनपुट, और टोकन को दूसरी फ़ाइल में आउटपुट करें। एक नमूना इनपुट/आउटपुट इस प्रकार दिखाई देगा:

इनपुट: (lexer से)

int a := 2 
if(a = 3) then 
    print "Yay!" 
endif 

आउटपुट:

INTEGER 
A 
ASSIGN 
2 
IF 
L_PAR 
A 
COMP 
3 
R_PAR 
THEN 
PRINT 
YAY! 
ENDIF 

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

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

धन्यवाद!

Answer 1

सबसे पहले, घटकों की आपकी सूची के बारे में एक बात समझ में नहीं आती है। एएसटी का निर्माण (बहुत अधिक) वाक्य रचनात्मक विश्लेषण है, इसलिए यह वहां नहीं होना चाहिए, या कम से कम एएसटी से पहले आना चाहिए।

आपको वहां क्या मिला है एक लेक्सर है। यह सब आपको व्यक्तिगत टोकन देता है। किसी भी मामले में, आपको एक वास्तविक पार्सर की आवश्यकता होगी, क्योंकि नियमित भाषाएं प्रोग्राम करने के लिए कोई मजेदार नहीं होती हैं। आप घोंसला अभिव्यक्तियों को भी ठीक से नहीं कर सकते हैं। बिल्ली, आप ऑपरेटर प्राथमिकता को भी संभाल नहीं सकते हैं। एक टोकन स्ट्रीम आपको नहीं देता है:

1. एक विचार जहां बयान और अभिव्यक्तियां शुरू होती हैं और समाप्त होती हैं।
2. एक विचार ब्लॉक को ब्लॉक में कैसे समूहीकृत किया जाता है।
3. एक विचार अभिव्यक्ति का कौन सा हिस्सा है जो प्राथमिकता, सहयोगीता, आदि
4. कार्यक्रम की वास्तविक संरचना पर एक स्पष्ट, अव्यवस्थित दृश्य।
5. एक संरचना जिसे कई बदलावों के माध्यम से पारित किया जा सकता है, को जानने वाले प्रत्येक एकल पास के बिना और को समायोजित करने के लिए कोड होने के कारण if में स्थिति कोष्ठक द्वारा संलग्न किया गया है।
6. ... अधिक आम तौर पर, एकल टोकन के स्तर से ऊपर की किसी भी प्रकार की समझ।

मान लीजिए कि आपके संकलक में दो गुजरता जो अनुकूलन ऑपरेटरों के कुछ प्रकार कुछ तर्क (जैसे कि, निरंतर तह और x - x -> 0 तरह बीजीय सरलीकरण) पर लागू होता है। यदि आप x - x * 1 अभिव्यक्ति के लिए उन्हें टोकन देते हैं, तो ये पास यह पता लगाने के साथ अव्यवस्थित हैं कि x * 1 भाग पहले आता है। और में है, यह जानने के लिए कि परिवर्तन गलत है (1 + 2 * 3 पर विचार करें)।

ये चीजें उतनी ही मुश्किल हैं जितनी सही है, इसलिए आप समस्याओं को पार्स करके भी परेशान नहीं होना चाहते हैं। यही कारण है कि आप एक अलग पार्सिंग चरण में पार्सिंग समस्या पहले को हल करते हैं। फिर आप ब्रांड्स को जोड़ने के बारे में चिंता किए बिना फ़ंक्शन कॉल को अपनी परिभाषा के साथ प्रतिस्थापित कर सकते हैं, इसलिए अर्थ वही रहता है। आप समय बचाते हैं, आप चिंताओं को अलग करते हैं, आप पुनरावृत्ति से बचते हैं, आप कई अन्य स्थानों आदि में सरल कोड सक्षम करते हैं।

एक पार्सर उन सभी को आंकड़े बताता है, और एक एएसटी बनाता है जिसके परिणामस्वरूप वह सारी जानकारी होती है। नोड्स पर किसी और डेटा के बिना, अकेले एएसटी का आकार आपको नहीं देता है। 1, 2, 3, और बहुत कुछ, मुफ्त में। कोई भी जो बैजिलियन पासों का पालन करता है, उसके बारे में चिंता करने की ज़रूरत नहीं है।

यह कहना नहीं है कि आपको हमेशा एएसटी होना है। पर्याप्त सरल भाषाओं के लिए, आप एकल-पास कंपाइलर कर सकते हैं। पार्सिंग के दौरान एएसटी या कुछ अन्य मध्यवर्ती प्रतिनिधित्व उत्पन्न करने के बजाय, जब आप जाते हैं तो आप कोड छोड़ देते हैं। हालांकि, यह कम सरल भाषाओं के लिए कठिन हो जाता है और आप उचित रूप से बहुत सारी चीजें नहीं कर सकते हैं (जैसे सभी अनुकूलन और निदान का 70% - और हाँ मैंने अभी उस नंबर को बनाया है)। आम तौर पर, मैं आपको ऐसा करने की सलाह नहीं दूंगा। अच्छे कारण हैं सिंगल पास कंपाइलर ज्यादातर मर चुके हैं। यहां तक ​​कि ऐसी भाषाएं जो उन्हें अनुमति देती हैं (उदा। सी) आजकल कई पास और एएसटी के साथ कार्यान्वित की जाती हैं। यह शुरू करने का एक आसान तरीका है, लेकिन बाद में आपको गंभीर रूप से सीमित कर देगा (और भाषा, यदि आप इसे डिज़ाइन करते हैं)।

Answer 2

आपको अपने प्रवाह आरेख में गलत बिंदु पर एएसटी मिला है। आम तौर पर, लेक्सर का उत्पादन टोकन की एक श्रृंखला है (जैसा कि आपके आउटपुट में है), और इन्हें पार्सर/सिंटेक्टिक विश्लेषक को खिलाया जाता है, जो एएसटी उत्पन्न करता है। तो आपके लेक्सर का आउटपुट एएसटी से अलग है क्योंकि उनका उपयोग संकलन प्रक्रिया में विभिन्न बिंदुओं पर किया जाता है और विभिन्न उद्देश्यों को पूरा करता है।

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

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

जैसा कि आपके कंपाइलर प्रोजेक्ट की प्रगति होती है, मुझे लगता है कि आप इस प्रतिनिधित्व के फायदे देखना शुरू कर देंगे।