खूंटी परसेंटर्स

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

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

यहाँ pgen के साथ कुछ समस्याएं हैं जो मुझे परेशान करती हैं। LL (1) नाम में "1" का तात्पर्य है कि यह केवल अगले टोकन का विश्लेषण करता है, और यह अच्छे व्याकरण के नियम बनाने की हमारी क्षमता को सीमित करता है। उदाहरण के लिए, पायथन स्टेटमेंट एक अभिव्यक्ति या एक असाइनमेंट (या कुछ और हो सकता है, लेकिन वे सभी एक हाइलाइट किए गए कीवर्ड से शुरू होते हैं, जैसे कि if या def )। मैं pgen संकेतन का उपयोग करके वाक्यविन्यास का वर्णन करना चाहूंगा। ध्यान दें कि यह केवल एक सरल उदाहरण है, जो पायथन का सबसेट है, जैसा कि आमतौर पर भाषा डिजाइन का वर्णन करते समय किया जाता है। यह एक खिलौना व्याकरण होगा जो आगे प्रदर्शन के लिए काम आएगा।

 statement: assignment | expr | if_statement expr: expr '+' term | expr '-' term | term term: term '*' atom | term '/' atom | atom atom: NAME | NUMBER | '(' expr ')' assignment: target '=' expr target: NAME if_statement: 'if' expr ':' statement 

अंकन के बारे में कुछ शब्द: NAME और NUMBER टोकन हैं और व्याकरण के बाहर पूर्वनिर्धारित हैं। '+' या 'if' टाइप के उद्धृत तार भी टोकन हैं। (आइए अगली बार उनके बारे में बात करते हुए स्थगित करें) व्याकरण के नियम नियम के नाम से शुरू होते हैं, उसके बाद : और फिर एक या एक से अधिक विकल्प, द्वारा अलग किए जाते हैं | ।

समस्या यह है कि यदि आप व्याकरण का इस तरह से वर्णन करते हैं, तो पैजन काम नहीं करेगा। यह इस तथ्य के कारण है कि कुछ नियमों ( expr और term ) को पुनरावर्ती छोड़ दिया जाता है, और वह ऐसी परिस्थितियों को सही ढंग से संभालने के लिए पर्याप्त स्मार्ट नहीं है। आमतौर पर यह केवल इन नियमों को फिर से लिखना द्वारा हल किया जाता है, अन्य नियमों को अपरिवर्तित छोड़ देता है। उदाहरण के लिए:

 expr: term ('+' term | '-' term)* term: atom ('*' atom | '/' atom)* 

यह pgen में EBNF की कई संभावनाओं को प्रकट करता है: आप कोष्ठक में विकल्प चुन सकते हैं और तत्व के बाद * रखकर पुनरावृत्ति बना सकते हैं। तो यहाँ अभिव्यक्ति के लिए नियम का अर्थ है "यह एक शब्द है जिसके बाद अनुक्रम के शून्य या अधिक दोहराव हैं <अवधि प्लस या शून्य, इसके बाद शब्द>"। यह व्याकरण पहले संस्करण के रूप में एक ही भाषा लेता है, लेकिन फिर से यह भाषा के डिजाइन इरादे को प्रतिबिंबित नहीं करता है। विशेष रूप से, यह नहीं दिखाता है कि ऑपरेटर बाईं ओर बंधे हैं, और यह महत्वपूर्ण है जब आप कोड उत्पन्न करने का प्रयास कर रहे हों।

लेकिन इस उदाहरण में एक और कष्टप्रद समस्या है (और पायथन में भी)। केवल एक टोकन पार्स करने के कारण, विश्लेषक यह निर्धारित नहीं कर सकता है कि वह क्या देख रहा है - एक अभिव्यक्ति या असाइनमेंट की शुरुआत। ऑपरेटर प्रसंस्करण की शुरुआत में, पार्सर को केवल पहले टोकन पर निर्णय लेना चाहिए, जो इसे पार करता है। (क्यों? यह कैसे pgen कार्यों में पार्स का कार्यान्वयन है) मान लीजिए कि हमारा कार्यक्रम इस प्रकार है:

 answer = 42 

यह कार्यक्रम तीन टोकन द्वारा दर्शाया गया है: NAME ( answer मान के साथ), = और NUMBER (मान 42 साथ)। पार्सिंग की शुरुआत के बारे में केवल एक चीज हमें पता है, पहला NAME टोकन है। जिस नियम को हम इस स्तर पर पार्स करने की कोशिश कर रहे हैं वह statement (व्याकरण का प्रारंभिक चरित्र) है। इसके लिए तीन विकल्पों को परिभाषित किया गया है: expr , assignment और if_statement । हम तुरंत if_statement बाहर कर सकते हैं, क्योंकि पिछले टोकन if नहीं if । लेकिन expr और assignment दोनों NAME टोकन के साथ शुरू हो सकते हैं, और इसके कारण, pgen हमारे व्याकरण को अस्पष्ट के रूप में अस्वीकार करता है।

यह पूरी तरह से सही नहीं है, क्योंकि तकनीकी रूप से व्याकरण स्वयं नहीं है; मुझे एक अधिक सटीक सूत्रीकरण नहीं मिल सकता है, इसलिए आइए हम इस पर ध्यान केंद्रित करें। और pgen इसे कैसे हल करता है? यह प्रत्येक व्याकरण नियम के लिए एक FIRST सेट नामक कुछ की गणना करता है, और यदि वे प्रतिच्छेद करते हैं, तो यह एक अपवाद फेंकता है।

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

 table[index + 1].name.first = 'Steven' 

इस मामले में, आपको = हमारे मिलने से पहले दस टोकन पार्स करने होंगे। लेकिन मैं आपको विश्वास दिलाता हूं, लंबे समय तक अभिव्यक्ति हो सकती है। Pgen में इस समस्या को हल करने के लिए, हमने व्याकरण विश्लेषक को बदल दिया ताकि यह कुछ गलत अभिव्यक्तियों को स्वीकार कर ले, बाद के पास में एक अतिरिक्त चेक जोड़ दे। यदि यह बाईं और दाईं ओर से मेल नहीं खा सकता है तो यह सिंटेक्स एरर एरर फेंक देगा। हमारी खिलौना भाषा के लिए, यह निम्नलिखित लिखने के लिए आता है:

 statement: assignment_or_expr | if_statement assignment_or_expr: expr ['=' expr] 

वर्गाकार कोष्ठक एक वैकल्पिक भाग को दर्शाता है। और फिर कंपाइलर के अगले पास (कहते हैं, बाइट-कोड जनरेशन) पर, हम जाँचते हैं कि क्या है या नहीं, और यदि ऐसा है, तो हम जाँचते हैं कि बाईं ओर target सिंटैक्स से मेल खाता है।

फ़ंक्शन कॉल तर्क के लिए एक समान समस्या है। हम कुछ इस तरह से लिखना चाहते हैं (फिर से, पायथन सिंटैक्स के सरलीकृत संस्करण में):

 call: atom '(' arguments ')' arguments: arg (',' arg) * arg: posarg | kwarg posarg: expr kwarg: NAME '=' expr 

लेकिन एक पार्सिंग एल्गोरिथ्म जो केवल अगले टोकन को ध्यान में रखता है, पार्सर को यह नहीं बता सकता है कि तर्कों की शुरुआत में posarg की शुरुआत है (क्योंकि posarg NAME शुरू हो सकता है) या kwarg की शुरुआत। फिर, वर्तमान पायथन पार्सर इस समस्या को निर्धारित करके हल करता है:

 arg: expr ['=' expr] 

और फिर बाद के संकलक पास में विकल्प को पूरा करता है। (हमने भी थोड़ी सी गलती की और foo((a) = 1) को foo(a = 1) तरह पार्स किया। यह केवल पायथन 3.8 में तय किया गया था।

तो एक पीईजी पार्सर इन समस्याओं को कैसे हल करता है? एक अनंत बैकअप बफर का उपयोग करना! इसका विशिष्ट कार्यान्वयन तथाकथित पैक्रैट पार्सर का उपयोग करता है, जो न केवल इसे पार्स करने से पहले पूरे कार्यक्रम को मेमोरी में लोड करता है, बल्कि विश्लेषक को वापस टोकन की मनमानी संख्या में रोल करने की अनुमति देता है। हालांकि PEG शब्द मुख्य रूप से व्याकरणिक संकेतन को संदर्भित करता है, PEG व्याकरण से उत्पन्न पार्सर आमतौर पर पुनरावर्ती वंश और असीमित वापसी के साथ पार्सर होते हैं। पैकरट पार्सर उन नियमों को याद करके कुशल बनाता है जो पहले से ही विशिष्ट पदों के लिए तैयार किए गए हैं।

यह एल्गोरिथ्म को सरल करता है, लेकिन निश्चित रूप से एक कीमत है: मेमोरी। तीस साल पहले, मेरे पास एलएल (1) का उपयोग करने का एक अच्छा कारण था: स्मृति महंगी थी। वह (अन्य तकनीकों जैसे एलएएलआर (1), जिसे वाईएसीसी द्वारा प्रसिद्ध किया गया है) एक कुशलतापूर्वक पार्स ट्री बनाने के लिए एक राज्य मशीन और स्टैक का उपयोग करता है।

सौभाग्य से, सीपीथॉन चलाने वाले कंप्यूटरों में 30 साल पहले की तुलना में बहुत अधिक मेमोरी है, और पूरी फाइल को मेमोरी में स्टोर करना अब कोई समस्या नहीं है। उदाहरण के लिए, stdlib में सबसे बड़ी गैर-परीक्षण फ़ाइल जो मुझे मिल सकती है _pydecimal.py है _pydecimal.py , जिसके बारे में 223kb लगते हैं। गीगाबाइट की दुनिया में, यह अनिवार्य रूप से कुछ भी नहीं है, जिसने मुझे पार्सर्स पर एक अलग नज़र डाला।

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

क्यों नहीं तुरंत एक पेड़ से संकलन? ठीक यही है कि यह कैसा था, लेकिन लगभग 15 साल पहले हमें पता चला कि कंपाइलर अधूरा था। इसलिए हमने एएसटी और एएसटी के परिवर्तन चरण को पार्स पेड़ से अलग-थलग कर दिया। जैसे-जैसे पायथन विकसित हुआ, एएसटी पार्सिंग से अधिक स्थिर होता गया, जिससे कंपाइलर में त्रुटियों की संभावना कम होती गई।

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

अब मैं इन चीजों को संयोजित करना चाहता हूं और यह देखना चाहता हूं कि क्या हम CPython के लिए एक नया पार्सर बना सकते हैं, जो PEG और पैकरैट का उपयोग सीधे पार्स करने के दौरान AST बनाने के लिए करता है। इस प्रकार, पार्सिंग के मध्यवर्ती पेड़ की पीढ़ी को छोड़ना संभव होगा, जो टोकन के लिए एक अनंत बफर के उपयोग के बावजूद, हमें स्मृति को बचा सकता है। मैं अभी भी कार्यान्वयन की प्रक्रिया में हूँ, लेकिन मेरे पास पहले से ही एक प्रोटोटाइप है जो वर्तमान CPython पार्सर के समान गति के बारे में AST में पायथन के सबसेट को संकलित कर सकता है। हालाँकि, यह अधिक मेमोरी का उपयोग करता है, और यह मुझे लगता है कि सबसेट को पूर्ण भाषा में विस्तारित करने से पीईजी पार्सर धीमा हो जाएगा। लेकिन अभी तक मैंने किसी भी अनुकूलन के बारे में नहीं सोचा है, इसलिए मैं काम करना जारी रखूंगा।

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

मैं पीईजी और मेरे कार्यान्वयन के बारे में बहुत कुछ बताना चाहता हूं, लेकिन कोड साफ करने के बाद यह अगले पदों पर होगा।

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