खूंटी पार्सर दृश्य

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

<लेख के अंत में स्पॉइलर के नीचे एक gif दिया गया है। यह मुझे एक स्थिर चित्र की तुलना में अधिक समझ में आता था>

आइए विज़ुअलाइज़ेशन को देखें। स्क्रीन को तीन भागों में विभाजित किया गया है, जैसा कि एक हाइफ़न लाइन के साथ ASCII में प्रथागत है:

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

इस विज़ुअलाइज़ेशन को समझने के लिए आपको मुख्य बात जानने की ज़रूरत है कि ऊपरी और निचले हिस्सों में लाइनों का इंडेंटेशन टोकन बफर से मेल खाती है।

• पहली दो पंक्तियाँ ( statement और assignment साथ शुरू) संबंधित पार्सर विधियों को कॉल दिखाती हैं जो अभी विश्लेषण कर रही हैं। उन्हें बुलाया गया था जब टोकन पॉइंटर पहले टोकन ( 'aap' ) से पहले था।
• अगली दो पंक्तियाँ ( expr और term शुरू) 'cat' टोकन की शुरुआत के साथ संरेखित की जाती हैं, जहां संबंधित पार्सर विधियों को बुलाया जाता है।
• स्टैक रेंडरिंग की पांचवीं और अंतिम पंक्ति expect('/') को कॉल दिखाती है, जो None लौटाता है। उन्होंने '+' टोकन स्थिति में स्वेच्छा से भाग लिया।

कैश में आइटम का इंडेंटेशन टोकन बफ़र की स्थिति से भी मेल खाता है। उदाहरण के लिए, नीचे कैश में नकारात्मक प्रविष्टियां हैं, उन्हें टोकन बफ़र की शुरुआत में 'if' टोकन और if_statement नियम की तलाश में प्राप्त किया गया था। हम टोकन '=' और NAME (विशेष रूप से, 'cat' ) और आगे की इनपुट स्थितियों के अनुरूप सफल कैश एंट्री पाते हैं।

एनालाइज़र स्टैक ब्लॉक और कैश ब्लॉक दोनों में, लौटी कॉल को function(args) -> result रूप में प्रदर्शित किया जाता है। कभी-कभी, पार्सर स्टैक पर कई लौटे तरीके प्रदर्शित होते हैं - मैंने लगातार सामग्री परिवर्तनों से पाठ घबराना कम करने के लिए ऐसा किया।

(घबराने की बात करते हुए, स्टैक से हटाए जाने पर कॉल को स्टैक में जोड़ने और ड्रॉप करने पर एनालाइज़र स्टैक की शीर्ष रेखाएँ ऊपर उठती हैं। यानी, स्टैक के विज़ुअलाइज़ेशन ब्लॉक के बहुत नीचे प्रत्येक नई कॉल डाली जाती है, मौजूदा लाइनों को ऊपर उठाती है। यह मुझे लगता है। स्क्रीन के इस हिस्से को देखना कोई समस्या नहीं है, ठीक है, कम से कम मेरे लिए। शायद, हमारे मस्तिष्क का एक महत्वपूर्ण हिस्सा चलती वस्तुओं को ट्रैक करने के लिए समर्पित है। :-)

शीर्ष पर अक्सर उपयोग की जाने वाली वस्तुओं के साथ कैश को LRU के रूप में प्रदान किया जाता है; अधिक दुर्लभ लोग स्क्रीन के नीचे जाते हैं। (पिछले लेखों में मैंने जो प्रोटोटाइप पैकरेट पार्सर दिखाया था, उसमें LRU का उपयोग नहीं किया गया है, लेकिन यह शायद आँखों की खपत को अनुकूलित करने के लिए एक अच्छा विचार है।)

परसिंग स्टैक को प्रस्तुत करते समय कुछ विवरण देखें। शीर्ष चार प्रविष्टियाँ उन पार्सर विधियों के अनुरूप हैं जिन्हें अभी भी संसाधित किया जा रहा है, प्रत्येक पंक्ति व्याकरण से एक पंक्ति है। हाइलाइट की गई वस्तु वह है जो अगली चुनौती उत्पन्न करती है।

यानी स्क्रीनशॉट को देखते हुए, हम statement लिए दूसरे विकल्प पर हैं, अर्थात् assignment । इस नियम में, हम तीसरे बिंदु पर हैं, अर्थात् expr । expr नियम में, हम केवल पहले विकल्प के पहले पैराग्राफ में हैं ( term '+' expr ); और term लिए नियम में हम अंतिम विकल्प ( atom ) में हैं।

नीचे हम उस परिणाम को देखते हैं जिसके परिणामस्वरूप दूसरा विकल्प ( atom '/' term ) की विफलता expect('/') -> None : expect('/') -> None टोकन '+' साथ expect('/') -> None इंडेंट expect('/') -> None । अगले चरण में, हम देखेंगे कि यह कैश में कैसे जाता है।

लेकिन निश्चित रूप से आप बल्कि पूरे एनीमेशन को खुद देखेंगे!

आप तैयार किए गए कोड के साथ भी खेल सकते हैं, लेकिन ध्यान रखें कि यह खेल नहीं है।

जब आप एक रिकॉर्ड किए गए GIF को देखते हैं , तो यह थोड़ा अजीब लग सकता है कि कभी-कभी अगला टोकन प्रदर्शित नहीं होता है (उदाहरण के लिए, बहुत शुरुआत में स्टैक को कई रिकॉर्डों द्वारा बढ़ाया जाता है, इससे पहले 'aap' टोकन का पता चला है)। यह ठीक वैसा ही है जैसा कि विश्लेषक देखता है: टोकन बफर आलसी से भरा होता है। जब तक पार्सर expect() फ़ंक्शन को कॉल करके उन्हें अनुरोध नहीं करता है तब तक स्कैन नहीं किया जाता है। जैसे ही टोकन बफर में प्रवेश करता है, यह वहां रहता है, भले ही विश्लेषक वापस टोकन के अनुक्रम को याद दिलाता है। रिवर्स ट्रैकिंग टोकन बफर में एक कर्सर के साथ दिखाया गया है जो बाईं ओर कूदता है; रिकॉर्ड पर ऐसी कई स्थितियां हैं। जब एनालाइज़र अतिरिक्त पुनरावर्ती कॉल नहीं करता है, तो आप कैश भरने का भी निरीक्षण कर सकते हैं। (ऐसा होने पर मुझे प्रकाश डालना होगा, लेकिन मेरे पास पर्याप्त समय नहीं था।)

अगले हफ्ते मैं एक पार्सर विकसित करूंगा, शायद पुनरावर्ती व्याकरण के बाएं नियमों पर अपना दृष्टिकोण जोड़ रहा हूं। (वे महान हैं!)

आभार: रिकॉर्ड के लिए मैंने इल्या चोली से ttygif इस्तेमाल किया और मैथ्यू रिकॉर्डिंग से ttyrec।

इस लेख के लिए लाइसेंस और कोड का हवाला दिया: CC BY-NC-SA 4.0