वाम पुनरावर्ती खूंटी व्याकरण

मैंने कई बार एक ठोकर के रूप में बाईं पुनरावृत्ति का उल्लेख किया, और यह पता लगाने का समय है। मुख्य समस्या यह है कि एक बाईं पुनरावर्ती वंश के साथ एक पार्सर एक स्टैक अतिप्रवाह के कारण तुरंत दुर्घटनाग्रस्त हो जाता है।

इस काल्पनिक व्याकरण नियम पर विचार करें:

expr: expr '+' term | term 

अगर हमने व्याकरण के इस टुकड़े को वाम-पुनरावर्ती पार्सर पद्धति में लागू किया, तो हमें निम्नलिखित में से कुछ मिलेगा:

 def expr(): if expr() and expect('+') and term(): return True if term(): return True return False 

इस प्रकार, expr() के लिए एक कॉल के साथ शुरू होता है, जो expr() के लिए एक कॉल के साथ शुरू होता है, जो एक कॉल के साथ शुरू होता है ... यह केवल एक रेक ओवरफ्लो के साथ समाप्त हो सकता है, एक RecursionError अपवाद के रूप में व्यक्त किया जा सकता है।

पारंपरिक समाधान व्याकरण को फिर से लिखना है। पिछले भागों में, मैंने ऐसा ही किया। वास्तव में, ऊपर दिए गए व्याकरण नियम को निम्नानुसार फिर से लिखा जा सकता है:

 expr: term '+' expr | term 

हालांकि, पार्स ट्री के निर्माण के चरण में, इसका आकार अलग होगा। यह स्थिति को बर्बाद कर सकता है अगर हमने व्याकरण में '-' ऑपरेटर को जोड़ा है (चूंकि a - (b - c) समान (a - b) - c ) के समान नहीं है। यह आमतौर पर समूह और पुनरावृत्ति जैसे अधिक शक्तिशाली पीईजी कार्यों के साथ हल किया जाता है, और हम उपरोक्त नियम को फिर से लिख सकते हैं:

 expr: term ('+' term)* 

वास्तव में, यह है कि वर्तमान पायथन व्याकरण को पैजन पार्सर के लिए लिखा गया है (जिसमें पुनरावर्ती नियमों के साथ समान समस्याएं हैं)।

हालांकि, एक छोटी सी समस्या है: चूंकि '+' और '-' (जैसे पायथन) में ऑपरेटर ज्यादातर बाइनरी होते हैं, जब हम a + b + c जैसी a + b + c चीज़ का विश्लेषण करते हैं, तो हमें पार्सिंग के परिणाम से गुजरना पड़ता है (जो मूल रूप से एक वामपंथी-पुनरावर्ती पेड़ बनाने के लिए ['a', '+', 'b', '+', 'c'] (जो कुछ इस तरह दिखेगी [['a', '+', 'b'] , '+', 'c'] )।

मूल बाईं पुनरावर्ती व्याकरण वांछित संगति में पहले से ही संकेत देता है, इसलिए इस रूप में सीधे पार्सर उत्पन्न करना अच्छा होगा। और हम कर सकते हैं! एक पाठक ने गणितीय प्रमाण के साथ एक अच्छी चाल बताई जिसे लागू करना आसान था। अब मैं समझाने की कोशिश करूंगा।

आइए इनपुट foo + bar + baz एक उदाहरण को देखें। जिस पेड़ को हम प्राप्त करना चाहते हैं, वह (foo + bar) + baz से मेल खाता है। यह expr() फ़ंक्शन के लिए तीन बाईं-पुनरावर्ती कॉल की आवश्यकता है: एक शीर्ष-स्तरीय ऑपरेटर '+' (जो कि, दूसरा) से मेल खाती है; एक और - आंतरिक ऑपरेटर '+' (यानी पहला); और तीसरा दूसरा विकल्प (यानी, term ) का विकल्प है।

चूंकि मैं विशेष उपकरणों का उपयोग करके वास्तविक आरेखों को आकर्षित करने में अच्छा नहीं हूं, इसलिए मैं ASCII कला का उपयोग करके यहां दिखाऊंगा:

 expr------------+------+ | \ \ expr--+------+ '+' term | \ \ | expr '+' term | | | | term | | | | | 'foo' 'bar' 'baz' 

विचार यह है कि expr() फ़ंक्शन में, हमें एक "ओरेकल" की आवश्यकता होती है जो हमें बताता है कि क्या पहला विकल्प चुनना है (अर्थात, exprive call to expr() ) या दूसरा (वह है, term() कॉल)। expr() के पहले कॉल पर expr() ऑरेकल को हमें पहले विकल्प ( expr() ) का पालन करने के लिए कहना चाहिए; दूसरे (पुनरावर्ती) कॉल में - इसी तरह, लेकिन तीसरे में हमें term() कॉल करने के लिए संकेत देना चाहिए। कोड में, यह इस तरह दिखेगा:

 def expr(): if oracle() and expr() and expect('+') and term(): return True if term(): return True return False 

इस तरह के एक ओरेकल को कैसे लिखना है? आइए देखें ... हम कॉल स्टैक में (बाएं-पुनरावर्ती) expr() कॉल की संख्या को ट्रैक करने की कोशिश कर सकते हैं और निम्न अभिव्यक्ति में '+' ऑपरेटरों की संख्या के साथ तुलना कर सकते हैं। यदि कॉल स्टैक स्टेटमेंट की संख्या से अधिक गहरा है, तो ओरेकल को गलत (हमें चुनने के लिए मजबूर करना) वापस करना चाहिए। मैं sys._getframe() साथ sys._getframe() लागू करने के लिए इंतजार नहीं कर सकता, लेकिन एक बेहतर तरीका है: चलो कॉल स्टैक फ्लिप करें!

विचार यह है कि हम एक कॉल के साथ शुरू करते हैं, जहां ओरेकल गलत हो जाता है, और परिणाम को बचाता है। यह हमें अनुक्रम expr() -> term() -> 'foo' । (इसे प्रारंभिक term लिए एक पार्स ट्री को वापस करना चाहिए, 'foo' , 'foo' । उपरोक्त कोड केवल True , लेकिन लेखों की श्रृंखला के दूसरे भाग में मैंने पहले ही दिखाया कि पार्स ट्री को कैसे वापस किया जाए।) इस तरह के एक ऑरेकल को लागू करना आसान है, क्योंकि इसे करना चाहिए। बस पहली कॉल पर False लौटें - भविष्य में कोई स्टैक चेकिंग या पीयरिंग की आवश्यकता नहीं है।

फिर हम expr() फिर से कॉल करते हैं, और इस बार oracle True लौटाता है, लेकिन expr() के लिए बाईं पुनरावर्ती कॉल के बजाय हम पिछले कॉल से सहेजे गए परिणाम को प्रतिस्थापित करते हैं। और चूंकि अपेक्षित ऑपरेटर '+' और अगला उपयुक्त टोकन भी मौजूद हैं, इससे हमें foo + bar लिए एक पार्स ट्री मिलेगा।

एक बार फिर हम एल्गोरिथ्म को दोहराते हैं, और फिर से सब कुछ बदल जाता है: इस बार हमें पूर्ण अभिव्यक्ति के लिए एक पार्सिंग ट्री मिलता है, और यह वास्तव में बाएं-पुनरावर्ती ( (foo + bar) + baz ) है।

फिर हम एल्गोरिथ्म को फिर से दोहराते हैं। लेकिन इस बार, हालांकि ओरेकल True , और पिछली कॉल का सहेजा गया परिणाम भी उपलब्ध है, और कोई '+' ऑपरेटर नहीं है, और पहला वैकल्पिक विफल रहता है। इस प्रकार, हम दूसरे विकल्प का प्रयास करते हैं, जो सफल होता है, और केवल प्रारंभिक शब्द ( 'foo' ) पाता है। यह परिणाम पहले विकल्प से प्राप्त की तुलना में खराब है, इसलिए इस स्तर पर हम सबसे लंबे विश्लेषण (यानी (foo + bar) + baz ) को रोकते हैं और बचाते हैं।

इसे काम करने के कोड में बदलने के लिए, मैंने पहली बार एल्गोरिथ्म को संशोधित किया ताकि expr() कॉल को expr() करने के लिए लेफ्ट-रिकर्सिव कॉल के साथ मिलाया जा सके। चलो इसे oracle_expr() । कोड:

 def expr(): if oracle_expr() and expect('+') and term(): return True if term(): return True return False 

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

 saved_result = None def oracle_expr(): if saved_result is None: return False return saved_result def expr_wrapper(): global saved_result saved_result = None parsed_length = 0 while True: new_result = expr() if not new_result: break new_parsed_length = <calculate size of new_result> if new_parsed_length <= parsed_length: break saved_result = new_result parsed_length = new_parsed_length return saved_result 

कोड, ज़ाहिर है, भयानक है, लेकिन कम से कम यह एल्गोरिथ्म का सार बताता है। आइए इसे रिफलेक्टर करें ताकि हम इस पर गर्व कर सकें।

सबसे महत्वपूर्ण समझ (जो मेरा है, हालांकि मैं शायद यह नोटिस करने वाला पहला व्यक्ति नहीं हूं) यह है कि हम एक वैश्विक चर के बजाय संस्मरण कैश का उपयोग कर सकते हैं। इसमें हम कॉल से कॉल पर रिजल्ट स्टोर करेंगे। तो हम एक अलग फ़ंक्शन oracle_expr() छुटकारा oracle_expr() , क्योंकि हम यह पता लगाने के लिए एक मानक कॉल उत्पन्न कर सकते हैं expr() कि क्या यह बाईं ओर या दाईं ओर एक पुनरावर्ती स्थिति में है।

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

प्रोटोटाइप का एक और लाभ जो मैंने तीसरे भाग में बनाया है, वह यह जांचना आसान बनाता है कि क्या नया परिणाम पुराने की तुलना में लंबा है: mark() विधि इनपुट टोकन की सरणी में सूचकांक को वापस लौटाती है, इसलिए हम बस parsed_length बजाय इसका उपयोग कर सकते हैं।

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

चलो युद्ध कोड लिखते हैं।

सबसे पहले, पार्सर जनरेटर को यह निर्धारित करना होगा कि कौन से नियम पुनरावर्ती हैं। यह ग्राफ सिद्धांत में एक हल समस्या है। मैं यहाँ एल्गोरिथ्म नहीं दिखाने जा रहा हूँ, और वास्तव में मैं इसे और भी सरल बनाना चाहता हूँ। मेरा मानना ​​है कि व्याकरण में केवल बाएं-पुनरावर्ती नियम सीधे बाएं-पुनरावर्ती होते हैं, जैसे हमारे खिलौना व्याकरण में expr । फिर, बाईं पुनरावृत्ति की जांच करने के लिए, आपको बस एक विकल्प की तलाश करने की आवश्यकता है जो वर्तमान नियम के नाम से शुरू होगा:

 def is_left_recursive(rule): for alt in rule.alts: if alt[0] == rule.name: return True return False 

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

संदर्भ के लिए, यहाँ मूल @memoize डेकोरेटर @memoize , भाग 3 से कॉपी किया गया है। याद रखें कि self एक Parser उदाहरण है जिसमें एक memo विशेषता है (एक खाली शब्दकोश के साथ आरंभीकृत) और mark() और reset() तरीके जो वर्तमान स्थिति को प्राप्त करते हैं और सेट करते हैं। tokenizer:

 def memoize(func): def memoize_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else: res = func(self, *args) endpos = self.mark() memo[key] = res, endpos return res return memoize_wrapper 

इनपुट स्ट्रीम में प्रत्येक स्थिति के लिए @memoize डेकोरेटर पिछले कॉल को याद करता है - इनपुट टोकन के (आलसी) सरणी में प्रत्येक स्थिति के लिए एक अलग memo शब्दकोश है। memoize_wrapper की पहली चार पंक्तियाँ सही memo शब्दकोश प्राप्त करने के लिए समर्पित memoize_wrapper ।

और यहाँ @memoize_left_rec । केवल else शाखा ऊपर @memoize में कार्यान्वयन से थोड़ी भिन्न है:

 def memoize_left_rec(func): def memoize_left_rec_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else: # Prime the cache with a failure. memo[key] = lastres, lastpos = None, pos # Loop until no longer parse is obtained. while True: self.reset(pos) res = func(self, *args) endpos = self.mark() if endpos <= lastpos: break memo[key] = lastres, lastpos = res, endpos res = lastres self.reset(lastpos) return res return memoize_left_rec_wrapper 

यह शायद दिलचस्प है कि यह expr() विधि के लिए कैसे काम करता है। आइए देखें कि निम्नलिखित कोड कैसे निष्पादित करेगा:

  @memoize_left_rec def expr(self): pos = self.mark() if ((expr := self.expr()) and self.expect('+') and (term := self.term())): return Node('expr', [expr, term]) self.reset(pos) if term := self.term(): return Node('term', [term]) self.reset(pos) return None 

पार्सिंग foo + bar + baz के उदाहरण पर।

जब भी आप expr() फ़ंक्शन को कॉल करते हैं, तो कॉल डेकोरेटर द्वारा "हुक" किया जाता है जो वर्तमान स्थिति में पिछले कॉल की तलाश कर रहा है। पहली कॉल पर, हम else शाखा में पहुँचते हैं, जहाँ हम बार-बार सजाए गए फंक्शन expr() कॉल करते हैं। जाहिर है, हम फिर से डेकोरेटर के पास पहुंचेंगे, लेकिन इस बार कैश में पहले से ही कुछ मूल्य है, इसलिए पुनरावृत्ति बाधित है।

आगे क्या होता है? प्रारंभिक कैश मान की गणना इस लाइन पर की जाती है:

  # Prime the cache with a failure. memo[key] = lastres, lastpos = None, pos 

यह इस तथ्य की ओर जाता है कि सजाया गया expr() None देता है, जिसके बाद पहला if expr() गिरता है (जब expr: = self.expr() )। यही है, हम दूसरे पर आगे बढ़ते हैं if , जो सफलतापूर्वक (हमारे उदाहरण में, 'foo' ) term पहचानता है और Node का एक उदाहरण देता है। हम कहाँ से वापस आ रहे हैं? डेकोरेटर में while करने के लिए। हम एक नए परिणाम ( Node उदाहरण) के साथ संस्मरण कैश को अपडेट करते हैं, और फिर अगला पुनरावृत्ति चलाते हैं।

expr() फिर से कहा जाता है, और इस समय इंटरसेप्टेड पुनरावर्ती कॉल Node (शब्द) का कैश्ड उदाहरण लौटाता है, और फिर कॉल करने की expect('+') । सब कुछ क्रम में है, क्योंकि अब हम पहले '+' ऑपरेटर पर हैं। उसके बाद, हम एक शब्द खोजते हैं जो सफल भी होता है ( 'bar' पाया जाता है)।

तो अब expr() , पहले से ही पहचाने जाने वाले foo + bar , while लौटता है, जो एक ही क्रिया करता है: यह संस्मरण कैश को एक नए (लंबे) परिणाम के साथ अपडेट करता है और अगला पुनरावृत्ति शुरू करता है।

यह खेल फिर दोहराया जाता है। फिर से, इंटरसेप्टेड पुनरावर्ती कॉल expr() कैश से एक नया परिणाम (इस बार foo + bar ) प्राप्त करता है, और हम एक और '+' (दूसरा) और दूसरा term ( 'baz' ) देखने की उम्मीद करते हैं। हम एक Node (foo + bar) + baz प्रतिनिधित्व करते हैं, और इसे while लौटाते हैं, जो इसे कैश में डालता है और फिर से दोहराता है।

लेकिन अब हम एल्गोरिथ्म की एक और शाखा के साथ जाएंगे। हम एक और '+' से मिलने की उम्मीद करते हैं, लेकिन इसे नहीं पाते हैं! इस प्रकार, यह कॉल expr() अपने दूसरे विकल्प पर लौटता है, और केवल term देता है। जब यह while से पहले पॉप अप while , तो यह पता चलता है कि यह परिणाम अंतिम से कम है। तो यह बाधित होता है और एक लंबा परिणाम देता है ( (foo + bar) + baz ) जिसने expr() कॉल शुरू किया है (उदाहरण के लिए, statement() कॉल यहाँ नहीं दिखाया गया है)।

तो, यह वह जगह है जहां आज की कहानी समाप्त होती है: हमने पीईजी पार्सर में सफलतापूर्वक बाईं पुनरावृत्ति को लागू किया। अगले हफ्ते मैं व्याकरण में "कार्यों" को जोड़ने पर चर्चा करने की योजना बना रहा हूं, जो हमें इस विकल्प के लिए पार्सर विधि द्वारा लौटाए गए परिणाम को अनुकूलित करने की अनुमति देगा (बजाय हमेशा एक Node उदाहरण वापस करने के लिए)।

यदि आप कोड के साथ खेलना चाहते हैं, तो GitHub रिपॉजिटरी देखें । (मैंने बाईं पुनरावृत्ति के लिए एक विज़ुअलाइज़ेशन कोड भी जोड़ा है, लेकिन मैं इससे बहुत खुश नहीं हूं, इसलिए मैंने इसे यहां लिंक प्रदान नहीं किया है।)

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