पीईजी पार्सर के लिए मेटा ग्रामर

इस सप्ताह हम पार्सर जनरेटर को "स्वतंत्र" बना रहे हैं, अर्थात यह अपना स्वयं का पार्सर उत्पन्न करेगा।

तो, हमारे पास पहले से ही एक पार्सर जनरेटर है, जिसका एक हिस्सा व्याकरण पार्सर है। हम इसे मेटा-पार्सर कह सकते हैं। मेटा-पार्सर उत्पन्न GrammarParser के समान ही कार्य करता है: GrammarParser विरासत में मिलता है और उसी mark() / reset() / hope() तंत्र का उपयोग करता है। हालाँकि, यह सब हाथ से लिखा गया था। लेकिन क्या यह सही है?

कंपाइलर डिज़ाइन करते समय, कंपाइलर को उस भाषा में लिखे जाने के लिए प्रथागत होता है, जिसे वह संकलित करता है। मुझे याद है कि पास्कल कंपाइलर जिसका उपयोग मैंने तब किया था जब मैंने पहली बार प्रोग्राम करना सीखा था पास्कल में ही लिखा गया था, जीसीसी सी में लिखा गया है, और रस्ट कंपाइलर रस्ट में लिखा गया है।

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

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

यहां क्रियाओं के बिना आरेख का एक सरल संस्करण है:

 start: rules ENDMARKER rules: rule rules | rule rule: NAME ":" alts NEWLINE alts: alt "|" alts | alt alt: items items: item items | item item: NAME | STRING 

मैं आपको दिखाता हूं कि नीचे से ऊपर तक कार्रवाई कैसे जोड़ें। भाग 3 से याद करें कि Rule वस्तुएं हैं जिनके name और alts । प्रारंभ में, alts केवल लाइन सूचियों की एक सूची थी (विकल्पों के लिए एक बाहरी सूची और वैकल्पिक के प्रत्येक तत्व के लिए एक आंतरिक सूची), लेकिन कार्यों को लागू करने के लिए, मैंने इसे बदल दिया ताकि विकल्प वस्तुओं और action विशेषताओं के साथ Alt ऑब्जेक्ट द्वारा प्रतिनिधित्व किए गए। तत्वों को अभी भी सरल तार के रूप में दर्शाया जाता है। item हमें मिलता है:

 item: NAME { name.string } | STRING { string.string } 

इसके लिए थोड़ी व्याख्या की आवश्यकता होती है: जब विश्लेषक टोकन की प्रक्रिया करता है, तो यह एक TokenInfo ऑब्जेक्ट लौटाता है जिसमें type , string और अन्य विशेषताएँ होती हैं। हम नहीं चाहते हैं कि जनरेटर TokenInfo ऑब्जेक्ट्स से TokenInfo , इसलिए यहां कार्रवाई टोकन से स्ट्रिंग TokenInfo । ध्यान दें कि सभी अपरकेस टोकन के लिए, जैसे NAME , उत्पन्न पार्सर स्ट्रिंग संस्करण (यहां name ) को चर के नाम के रूप में उपयोग करता है।

इसके बाद वे items जिन्हें स्ट्रिंग्स की सूची वापस करनी चाहिए:

 items: item items { [item] + items } | item { [item] } 

यहां मैं सही-पुनरावर्ती नियमों का उपयोग करता हूं, इसलिए हम बाईं ओर की पुनरावृत्ति प्रसंस्करण पर निर्भर नहीं हैं, भाग 5 में जोड़ा गया है (क्यों नहीं? यह हमेशा संभव के रूप में चीजों को सरल रखने के लिए अच्छा है, और यह व्याकरण बाएं पुनर्विचार के तहत एक बदलाव से बहुत फायदा नहीं होगा) ध्यान दें कि एक item सूचीबद्ध है, लेकिन पुनरावर्ती items नहीं हैं, क्योंकि यह पहले से ही एक सूची है।

alt ऑब्जेक्ट बनाने के लिए alt नियम:

 alt: items { Alt(items) } 

मैं rules और start लिए क्रियाओं को छोड़ दूंगा, क्योंकि वे इस तरह से परिभाषित किए गए हैं।

हालाँकि, दो खुले प्रश्न हैं। सबसे पहले, मैं Rule और Alt वर्गों की परिभाषा कैसे खोजूं? ऐसा करने के लिए, हमें उत्पन्न कोड में कई import विवरण जोड़ने होंगे। सबसे आसान तरीका होगा कि आप जेनरेटर को झंडा पास करें, जो कहता है कि "यह एक मेटा-व्याकरण है", और जनरेटर को उत्पन्न कार्यक्रम की शुरुआत में एक अतिरिक्त import करने दें। लेकिन अब जब हमारे पास कार्य हैं, तो कई अन्य पार्सर भी अपने आयात को अनुकूलित करना चाहेंगे, इसलिए यह नहीं देखा जाए कि क्या हम अधिक सामान्य दृष्टिकोण को लागू कर सकते हैं।

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

 @subheader "from grammar import Rule, Alt" 

पार्सर जनरेटर मानक आयात के बाद subheader चर के मूल्य को प्रिंट करेगा, जो डिफ़ॉल्ट रूप से जोड़ा जाता है (उदाहरण के लिए, memoize आयात करने के लिए)। यदि आप कई import तत्व चाहते हैं, तो आप ट्रिपल उद्धरण के साथ एक स्ट्रिंग का उपयोग कर सकते हैं, उदाहरण के लिए,

 @subheader """ from token import OP from grammar import Rule, Alt """ 

मेटा-व्याकरण में जोड़ना आसान है: हम start नियम को निम्नलिखित में तोड़ेंगे:

 start: metas rules ENDMARKER | rules ENDMARKER metas: meta metas | meta meta: "@" NAME STRING NEWLINE 

(मुझे यह याद नहीं है कि मैंने इसे "मेटा" क्यों कहा, लेकिन मैंने यह नाम तब चुना था जब मैंने कोड लिखा था, और मैं इसे चिपकाऊंगा। :-)

हमें इसे बूटस्ट्रैप रूपक में जोड़ना चाहिए। अब जब व्याकरण केवल नियमों की सूची नहीं है, तो आइए metas और rules विशेषताओं के साथ एक व्याकरण वस्तु जोड़ें। हम निम्नलिखित क्रियाएं निर्धारित कर सकते हैं:

 start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } metas: meta metas { [meta] + metas } | meta { [meta] } meta: "@" NAME STRING { (name.string, eval(string.string)) } 

(ध्यान दें कि meta एक टपल लौटाता है; और यह भी कि यह स्ट्रिंग उद्धरणों को संसाधित करने के लिए eval() का उपयोग करता है।)

मैंने नियमों के कार्यों के कार्यान्वयन का उल्लेख नहीं किया है! कारण यह है कि वे थोड़ा गड़बड़ निकलते हैं। लेकिन यह आगे स्थगित करने के लिए कोई मतलब नहीं है, तो यहाँ:

 alt: items action { Alt(items, action) } | items { Alt(items, None) } action: "{" stuffs "}" { stuffs } stuffs: stuff stuffs { stuff + " " + stuffs } | stuff { stuff } stuff: "{" stuffs "}" { "{" + stuffs + "}" } | NAME { name.string } | NUMBER { number.string } | STRING { string.string } | OP { None if op.string in ("{", "}") else op.string } 

परिभाषा में गंदगी घुंघराले एक्शन ब्रैकेट्स के बीच मनमाने पायथन कोड को वैध बनाने की मेरी इच्छा के कारण है, जिसमें नेस्टेड एक और घुंघराले ब्रेसिज़ शामिल हैं। इस उद्देश्य के लिए, हम एक विशेष OP टोकन का उपयोग करते हैं जो पायथन द्वारा मान्यता प्राप्त सभी विराम चिह्न के लिए हमारे टोकन को उत्पन्न करता है (बहु <= लिए OP साथ एकल टोकन लौटाता है जैसे कि <= या ** )। केवल अन्य टोकन जो पायथन अभिव्यक्तियों में हो सकते हैं, वे हैं नाम, संख्या और तार। इस प्रकार, कार्रवाई के बाहरी ब्रेसिज़ के बीच कोड, ऐसा लगता है, NAME | NUMBER | STRING | OP पुनरावृत्ति के माध्यम से व्यक्त किया जा सकता है NAME | NUMBER | STRING | OP NAME | NUMBER | STRING | OP ।

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

इस छोटी सी हैक का उपयोग करते हुए, हम OP गिरावट की तुलना एक घुंघराले ब्रेस पर कर सकते हैं। फिर stuff और action की तुलना संभव होगी।

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

यहां पूरी कार्रवाई मेटा व्याकरण है। वह खुद का विश्लेषण कर सकता है, क्योंकि वह जानता है कि लंबी लाइनों को कैसे जोड़ा जाए:

 @subheader """ from grammar import Grammar, Rule, Alt from token import OP """ start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } metas: meta metas { [meta] + metas } | meta { [meta] } meta: "@" NAME STRING NEWLINE { (name.string, eval(string.string)) } rules: rule rules { [rule] + rules } | rule { [rule] } rule: NAME ":" alts NEWLINE { Rule(name.string, alts) } alts: alt "|" alts { [alt] + alts } | alt { [alt] } alt: items action { Alt(items, action) } | items { Alt(items, None) } items: item items { [item] + items } | item { [item] } item: NAME { name.string } | STRING { string.string } action: "{" stuffs "}" { stuffs } stuffs: stuff stuffs { stuff + " " + stuffs } | stuff { stuff } stuff: "{" stuffs "}" { "{" + stuffs + "}" } | NAME { name.string } | NUMBER { number.string } | STRING { string.string } | OP { None if op.string in ("{", "}") else op.string } 

अब जब हमारे पास एक कार्यशील मेटा-व्याकरण है, तो हम कुछ सुधार करने के लिए लगभग तैयार हैं।

लेकिन पहले आपको थोड़ा सोचने की जरूरत है: खाली लाइनें! यह पता चला है कि stdlib tokenize मॉड्यूल तुच्छ लाइन tokenize ( NL टोकन) और टिप्पणियों ( COMMENT टोकन) को ट्रैक करने के लिए अतिरिक्त टोकन बनाता है। व्याकरण में उन्हें शामिल करने के बजाय (मैंने इसे आज़माया, बहुत मज़ा नहीं आया!), कोड का एक बहुत ही सरल टुकड़ा है जिसे हम अपने फ़िल्टर करने के लिए अपने टोकन वर्ग में जोड़ सकते हैं। यहाँ सुधार किया गया है peek_token विधि:

  def peek_token(self): if self.pos == len(self.tokens): while True: token = next(self.tokengen) if token.type in (NL, COMMENT): continue break self.tokens.append(token) self.report() return self.tokens[self.pos] 

यह NL और COMMENT टोकन को पूरी तरह से हटा देता है, इसलिए हमें व्याकरण में उनके बारे में चिंता करने की आवश्यकता नहीं है।

अंत में, मेटा-व्याकरण में सुधार करें! वे विशुद्ध रूप से कॉस्मेटिक होंगे: मुझे यह पसंद नहीं है जब मुझे एक पंक्ति में सभी विकल्पों को लिखने के लिए मजबूर किया जाता है। मेटा व्याकरण जो मैंने ऊपर दिखाया वह वास्तव में ऐसी चीजों के कारण खुद को पार्स नहीं करता है:

 start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } 

यह इस तथ्य के कारण है कि टोकनधारक पहली पंक्ति के अंत में NEWLINE टोकन बनाता है, और इस समय मेटा-पार्सर इसे नियम का अंत मान लेगा। इसके अलावा, इस NEWLINE का अनुसरण INDENT टोकन द्वारा किया जाएगा, क्योंकि अगली पंक्ति इंडेंटेड है। अगले नियम की शुरुआत तक, एक DEDENT टोकन भी मौजूद रहेगा।

इसे संभालना है। एक tokenize मॉड्यूल के व्यवहार को समझने के लिए, हम टोकन मॉड्यूल को स्क्रिप्ट के रूप में चलाकर और इसे कुछ पाठ पास करके इंडेंटेड ब्लॉक के लिए उत्पन्न टोकन के अनुक्रम को देख सकते हैं:

 $ python -m tokenize foo bar baz dah dum ^D 

हम देखते हैं कि यह टोकन के निम्नलिखित अनुक्रम का उत्पादन करता है (मैंने उपरोक्त कोड से आउटपुट को थोड़ा सरल किया):

 NAME 'foo' NAME 'bar' NEWLINE INDENT NAME 'baz' NEWLINE NAME 'dah' NEWLINE DEDENT NAME 'dum' NEWLINE 

इस प्रकार, स्ट्रिंग का एक चयनित समूह INDENT और DEDENT द्वारा इंगित किया गया है। अब हम rule लिए मेटा-व्याकरण rule को फिर से लिख सकते हैं:

 rule: NAME ":" alts NEWLINE INDENT more_alts DEDENT { Rule(name.string, alts + more_alts) } | NAME ":" alts NEWLINE { Rule(name.string, alts) } | NAME ":" NEWLINE INDENT more_alts DEDENT { Rule(name.string, more_alts) } more_alts: "|" alts NEWLINE more_alts { alts + more_alts } | "|" alts NEWLINE { alts } 

(मैं क्रियाओं को लाइनों में तोड़ता हूं ताकि वे पाठ के एक संकीर्ण कॉलम में सामान्य रूप से पढ़ें। यह संभव है क्योंकि टोकन कर्ता इसी घुंघराले ब्रेसिज़ के अंदर लाइन टूटता है।)

इसकी सुंदरता यह है कि हमें जनरेटर को बदलने की आवश्यकता नहीं है: इस बेहतर मेटा-व्याकरण द्वारा बनाई गई डेटा संरचना पहले की तरह ही है। rule के तीसरे विकल्प पर भी ध्यान दें: यह हमें लिखने की अनुमति देता है:

 start: | metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } 

जो कुछ मैंने पहले दिखाया संस्करण की तुलना में इसे साफ कर सकता है। दोनों रूपों को हल करना आसान है, इसलिए हमें शैली के बारे में बहस करने की आवश्यकता नहीं है।

अगली पोस्ट में, मैं दिखाऊंगा कि कैसे मैंने विभिन्न PEG फ़ंक्शंस लागू किए, जैसे कि वैकल्पिक तत्व, दोहराता है, और टूलटिप्स। (ईमानदार होने के लिए, मैंने इस लेख में उनके बारे में बात करने की योजना बनाई है, लेकिन यह पहले से ही बहुत बड़ा है। इसलिए मैं इसे अन्य भागों में विभाजित करूंगा।)

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