खूंटी पार्सर कार्यान्वयन

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

इस खंड में, मैंने पिछले लेख से खिलौना व्याकरण के एक सरल स्व-लिखित कार्यान्वयन के उदाहरण का उपयोग करते हुए, पार्सर के काम को समझने के लिए नींव रखी।

(वैसे, एक प्रयोग के रूप में, मैं अपने पाठ में लिंक नहीं देता हूं। यदि आप कुछ नहीं समझते हैं, तो आप इसे केवल समझ सकते हैं। :-)

आमतौर पर, एक पीईजी एक असीमित बफर के साथ एक पुनरावर्ती वंश पार्सर का उपयोग करता है। यहाँ पिछले लेख से एक खिलौना व्याकरण है:

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 

इस भाषा के लिए पुनरावर्ती वंश का सुपर-अमूर्त पार्सर प्रत्येक नियम के लिए अपने कार्य को परिभाषित करेगा जिसमें विकल्पों को समझा जाएगा। उदाहरण के लिए, statement , हमारे पास यह फ़ंक्शन होगा:

 def statement(): if assignment(): return True if expr(): return True if if_statement(): return True return False 

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

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

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

एक क्लासिक टोकन में आमतौर पर एक एकल get_token() फ़ंक्शन से युक्त एक सरल इंटरफ़ेस होता है। हर बार, यह इनपुट अनुक्रम में अगला टोकन देता है, वर्णों के समूह का विश्लेषण करता है। CPython का tokenize मॉड्यूल कोई अपवाद नहीं है: इसका मुख्य API एक जनरेटर है जो एक समय में एक टोकन जारी करता है। प्रत्येक टोकन प्रकार TypeInfo का एक ऑब्जेक्ट है, जिसमें कई फ़ील्ड्स हैं, जिनमें से सबसे महत्वपूर्ण है टोकन का प्रकार (उदाहरण के लिए, NAME , NUMBER , STRING ) और इसका स्ट्रिंग मान उन वर्णों का समूह है, जिनमें यह शामिल है (उदाहरण के लिए, abc , 42 या "Hello, world" )। अतिरिक्त क्षेत्र भी हैं। उदाहरण के लिए, इनपुट स्ट्रीम में टोकन इंडेक्स के लिए, जो त्रुटि संदेशों में उपयोगी है।

एक विशेष प्रकार का टोकन ENDMARKER , जो इंगित करता है कि इनपुट फ़ाइल का अंत पहुँच गया है। यदि आप इसे अनदेखा करते हैं और अगला टोकन प्राप्त करने का प्रयास करते हैं तो जनरेटर गिर जाएगा।

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

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

कोर एपीआई बहुत सरल है। Tokenizer ऑब्जेक्ट इस सरणी में टोकन और स्थिति के एक सरणी को Tokenizer करता है। उसकी तीन मुख्य विधियाँ हैं:

• get_token() अगला टोकन लौटाता है, पॉइंटर को get_token() या स्रोत से अगला टोकन पढ़ता है, अगर हम टोकन बफर के अंत में हैं);
• mark() बफर में वर्तमान स्थिति लौटाता है;
• reset(pos) बफर में स्थिति निर्धारित करता है (तर्क को mark() से प्राप्त किया जाना चाहिए)।

हमने एक हेल्पर फंक्शन peek_token() जोड़ा, जो बफर में स्थिति को शिफ्ट किए बिना अगला टोकन लौटाता है।

यह Tokenizer वर्ग का आधार जैसा दिखता है:

 class Tokenizer: def __init__(self, tokengen): """Call with tokenize.generate_tokens(...).""" self.tokengen = tokengen self.tokens = [] self.pos = 0 def mark(self): return self.pos def reset(self, pos): self.pos = pos def get_token(self): token = self.peek_token() self.pos += 1 return token def peek_token(self): if self.pos == len(self.tokens): self.tokens.append(next(self.tokengen)) return self.tokens[self.pos] 

यहाँ, सादगी के लिए कुछ छोड़ा गया है (उदाहरण के लिए, तरीकों और उदाहरण चर के नाम एक अंडरस्कोर से शुरू होने चाहिए), लेकिन यह सिर्फ Tokenizer एपीआई का एक प्रोटोटाइप है।

Parser को भी एक वर्ग बनना चाहिए ताकि statement() , expr() , आदि। विधियों के रूप में लागू किया जा सकता है। टोकनधारक एक उदाहरण चर बन जाएगा, लेकिन मैं नहीं चाहता कि पार्सर विधियां सीधे get_token() को कॉल करें - इसके बजाय, हम Parser वर्ग में wait() विधि को लागू करते हैं, जो पार्सर विधि की तरह ही सफल या विफल हो सकती है। wait() फ़ंक्शन का तर्क अपेक्षित टोकन है: या तो एक स्ट्रिंग (उदाहरण के लिए, + ) या टोकन का एक प्रकार (उदाहरण के लिए, NAME )। वापसी मूल्य का प्रकार अभी तक महत्वपूर्ण नहीं है, मैं पार्सर के काम के परिणाम पर चर्चा करने के बाद वापस आऊंगा।

व्याकरण नियम कार्यों False केवल True या False लौटाएं। यह सैद्धांतिक कंप्यूटर विज्ञान के लिए अच्छा है (वहाँ तोता सवाल का जवाब देता है "क्या यह भाषा में एक वैध स्ट्रिंग है?"), लेकिन हमारे लिए नहीं। हमारा काम एएसटी बनाना है। तो, चलिए इस कोड को फिर से लिखते हैं ताकि प्रत्येक विश्लेषण विधि सफलता पर एक Node ऑब्जेक्ट लौटाए या विफलता पर None ।

Node वर्ग बहुत सरल हो सकता है:

 class Node: def __init__(self, type, children): self.type = type self.children = children 

यहां, type एएसटी नोड का type निर्धारित करता है (उदाहरण के लिए, add या if ), और वंश नोड्स और टोकन ( TokenInfo इंस्टेंस) की एक सूची है। यह कंपाइलर के लिए कोड उत्पन्न करने या अन्य विश्लेषण करने के लिए पर्याप्त है, जैसे कि लाइनिंग या स्टेटिक टाइप चेकिंग। हालांकि भविष्य में मैं एएसटी को प्रस्तुत करने के तरीके को बदलना चाहूंगा।

इस योजना में फिट होने के लिए, expect() विधि को सफलता पर एक TokenInfo ऑब्जेक्ट वापस करना चाहिए और विफलता पर None । पिछले टोकन में वापस रोल करने में सक्षम होने के लिए, मैं mark() और reset() टोकन के तरीकों (यहां एपीआई नहीं बदलता है) को कॉल लपेटता हूं। यहाँ क्या हुआ:

 class Parser: def __init__(self, tokenizer): self.tokenizer = tokenizer def mark(self): return self.tokenizer.mark() def reset(self, pos): self.tokenizer.reset(pos) def expect(self, arg): token = self.tokenizer.peek_token() if token.type == arg or token.string == arg: return self.tokenizer.get_token() return None 

एक बार फिर: मैंने कुछ विवरणों को छोड़ दिया है, लेकिन यह पहले से ही काम कर रहा है।

अब मुझे पार्सर विधियों के लिए एक महत्वपूर्ण आवश्यकता शुरू करने की आवश्यकता है। सभी को या तो Node वापस करना चाहिए, व्याकरण नियम के अंतिम टोकन के बाद एक टोकन रखने वाला जिसे उन्होंने मान्यता दी थी; या तो None और टोकनधारक की स्थिति को अपरिवर्तित न छोड़े। यदि पार्सर विधि कई टोकन पढ़ती है और फिर बंद हो जाती है, तो उसे टोकनधारक की स्थिति को पुनर्स्थापित करना होगा। ऐसा करने के लिए, mark() और reset() का इरादा है। ध्यान दें कि expect() भी इस नियम का पालन करती है।

तो, यहाँ वास्तविक पार्सर का एक स्केच है। यहाँ मैं पायथॉन 3.8 ( := ) से वालरस ऑपरेटर का उपयोग करता हूँ:

 class ToyParser(Parser): def statement(self): if a := self.assignment(): return a if e := self.expr(): return e if i := self.if_statement(): return i return None def expr(self): if t := self.term(): pos = self.mark() if op := self.expect("+"): if e := self.expr(): return Node("add", [t, e]) self.reset(pos) if op := self.expect("-"): if e := self.expr(): return Node("sub", [t, e]) self.reset(pos) return t return None def term(self): # Very similar... def atom(self): if token := self.expect(NAME): return token if token := self.expect(NUMBER): return token pos = self.mark() if self.expect("("): if e := self.expr(): if self.expect(")"): return e self.reset(pos) return None 

मैंने कुछ विधियों के कार्यान्वयन को छोड़ दिया ताकि पाठक को स्वयं अभ्यास करने का अवसर मिले। यह वास्तव में पढ़ने से बेहतर है कि इस तरह के पार्सर को कैसे लागू किया जाए। अंत में, हम व्याकरण से स्वचालित रूप से इस तरह के कोड को उत्पन्न करेंगे। NAME और NUMBER जैसे कॉन्स्टैंट मानक लाइब्रेरी के token मॉड्यूल से आयात किए जाते हैं। यह हमें पायथन टोकन के वर्तमान कार्यान्वयन के लिए प्रेरित करता है। यदि हम एक सामान्यीकृत खूंटी पार्सर बनाना चाहते हैं, तो हमें इससे बचने के तरीके खोजने होंगे।

यह भी ध्यान दें कि मैं थोड़ा धोखा खा गया। expr विधि को पुनरावर्ती छोड़ दिया जाना चाहिए, लेकिन मैंने पार्सर को सही पुनरावर्ती बना दिया क्योंकि पुनरावर्ती वंश पार्सर बाएं पुनरावर्ती व्याकरण नियमों के साथ काम नहीं करता है। यह तय किया जा सकता है, लेकिन यह अभी भी कुछ वैज्ञानिक अनुसंधान का विषय है, और मैं इसके बारे में अलग से बात करना चाहूंगा। बस ध्यान रखें कि यह कार्यान्वयन हमारे सरलीकृत व्याकरण के अनुरूप 100% नहीं है।

मुख्य बातें जो मैं आपको अब तक समझना चाहता हूं:

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

यदि सभी पार्सिंग तरीके इन नियमों का पालन करते हैं, तो प्रत्येक को mark() और reset() कॉल में लपेटने की आवश्यकता नहीं है। यह प्रेरण द्वारा सिद्ध किया जा सकता है।

इसके अलावा, संदर्भ प्रबंधक और स्टेटमेंट का उपयोग करके mark() और reset() लिए स्पष्ट कॉल से छुटकारा पाने की कोशिश करना आकर्षक है, लेकिन यह काम नहीं करेगा: यदि आप सफल नहीं हैं, तो reset() कॉल न करें! एक और तय के रूप में, आप नियंत्रण प्रवाह के अपवादों का उपयोग करने का प्रयास कर सकते हैं ताकि संदर्भ प्रबंधक को पता चल जाए कि क्या टोकन को रीसेट किया जाना चाहिए (मुझे लगता है कि TatSu कुछ ऐसा ही कर रहा है)। उदाहरण के लिए, कुछ इस तरह:

  def statement(self): with self.alt(): return self.assignment() with self.alt(): return self.expr() with self.alt(): return self.if_statement() raise ParsingFailure 

विशेष रूप से, if एक अभिव्यक्ति की पहचान के लिए atom() में कोष्ठक में if गए एक छोटे से सीढ़ी के रूप में लिखा जा सकता है:

  with self.alt(): self.expect("(") e = self.expr() self.expect(")") return e 

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

वैसे भी, यहाँ निम्नलिखित भागों के लिए कुछ विषय दिए गए हैं:

• व्याकरण से पारसर विधियों की पीढ़ी;
• packrat-parsing (संस्मरण);
• EBNF के फीचर्स जैसे (x | y) , [xy ...] , x* , x+ ;
• अनुरेखण (एक पार्सर या व्याकरण डिबगिंग के लिए);
• पीईजी फीचर्स जैसे लुकहेड और कट;
• बाएं पुनरावर्ती नियमों को कैसे संभालना है;
• सी कोड जनरेशन

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