खूंटी parser पीढ़ी

अब जब मैंने एक मालिकाना पार्सर की मूल बातें छोड़ दी हैं, तो चलिए व्याकरण से इसकी विधियाँ उत्पन्न करते हैं, जैसा कि मैंने वादा किया था। मैं यह भी दिखाऊंगा कि @memoize डेकोरेटर का उपयोग करके @memoize पार्सर को कैसे लागू किया @memoize ।

पिछली बार, हमने कुछ पार्सर विधियों को देखा। कुछ प्रतिबंधों के साथ जिन्हें हम बाद में थोड़ा हटा देंगे, वे व्याकरण से स्वचालित रूप से उत्पन्न करना आसान है।

हमें दो चीजों की आवश्यकता है: ऐसा कुछ जो व्याकरण को पढ़ता है और एक उपयुक्त डेटा संरचना बनाता है; और ऐसा कुछ जो इस डेटा संरचना को लेता है और एक पार्सर उत्पन्न करता है। हमें अन्य सहायक तरीकों की भी आवश्यकता है, लेकिन वे दिलचस्प नहीं हैं, इसलिए मैं उन्हें छोड़ दूंगा।

इसलिए, हम एक सरल संकलक संकलक बना रहे हैं। मैं व्याकरणिक संकेतन को इस हद तक सरल कर दूंगा कि हमारे पास केवल नियम और विकल्प हों; यह वास्तव में खिलौने के व्याकरण के लिए पर्याप्त है जिसे मैंने पिछले भागों में उपयोग किया था:

 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 

पूर्ण संकेतन का उपयोग करते हुए, हम व्याकरण का वर्णन इस प्रकार कर सकते हैं:

 grammar: rule+ ENDMARKER rule: NAME ':' alternative ('|' alternative)* NEWLINE alternative: item+ item: NAME | STRING 

यह हमारा पहला मेटा-व्याकरण (व्याकरण के लिए व्याकरण) है, और हमारा पार्सर जनरेटर मेटा-कंपाइलर होगा (एक कंपाइलर एक प्रोग्राम है जो एक भाषा से दूसरी भाषा में प्रोग्राम का अनुवाद करता है; एक मेटा-कंपाइलर एक कंपाइलर है जहां इनपुट एक व्याकरण है, और आउटपुट एक पार्सर है)।

मेटा-व्याकरण का वर्णन करने का एक आसान तरीका केवल अंतर्निहित डेटा प्रकारों का उपयोग करना है: नियम का सही हिस्सा तत्वों की सूची की एक सूची है, जिनमें से प्रत्येक सिर्फ एक स्ट्रिंग हो सकता है। (वैसे, यदि पहला वर्ण एक उद्धरण चिह्न है, तो हम जाँच करके NAME और STRING को अलग कर सकते हैं)

नियमों के लिए, मैं सरल Rule वर्ग का उपयोग करता हूं, और संपूर्ण व्याकरण ऐसी वस्तुओं की एक सूची है। यहाँ __eq__ और __eq__ को छोड़कर Rule वर्ग है:

 class Rule: def __init__(self, name, alts): self.name = name self.alts = alts 

और यहाँ GrammarParser क्लास है जो इसका उपयोग करता है:

 class GrammarParser(Parser): def grammar(self): pos = self.mark() if rule := self.rule(): rules = [rule] while rule := self.rule(): rules.append(rule) if self.expect(ENDMARKER): return rules # <------------- final result self.reset(pos) return None def rule(self): pos = self.mark() if name := self.expect(NAME): if self.expect(":"): if alt := self.alternative(): alts = [alt] apos = self.mark() while (self.expect("|") and (alt := self.alternative())): alts.append(alt) apos = self.mark() self.reset(apos) if self.expect(NEWLINE): return Rule(name.string, alts) self.reset(pos) return None def alternative(self): items = [] while item := self.item(): items.append(item) return items def item(self): if name := self.expect(NAME): return name.string if string := self.expect(STRING): return string.string return None 

ENDMARKER के उपयोग पर ध्यान ENDMARKER । वहां मैं यह सुनिश्चित करता हूं कि अंतिम नियम के बाद कुछ भी नहीं रहता (और अगर व्याकरण में कोई टाइपो है तो ऐसा हो सकता है)। मैंने उस स्थान को भी इंगित किया जहां grammar() विधि नियमों की एक सूची देता है। बाकी सब कुछ पिछले लेख के ToyParser वर्ग के समान है, इसलिए मैं उस पर ध्यान नहीं दूंगा। बस ध्यान दें कि item() एक स्ट्रिंग लौटाता है, alternative() स्ट्रिंग्स की एक सूची देता है, और rule() अंदर चर alts rule() स्ट्रिंग्स की सूची की एक सूची एकत्र करता है। फिर, rule() विधि नियम (स्ट्रिंग) के नाम को जोड़ती है और इसे Rule वस्तु में परिवर्तित करती है।

यदि हम इस एल्गोरिथ्म को अपने खिलौना व्याकरण पर लागू करते हैं, तो grammar() विधि नियमों की निम्नलिखित सूची वापस कर देगी:

 [ Rule('statement', [['assignment'], ['expr'], ['if_statement']]), Rule('expr', [['term', "'+'", 'expr'], ['term', "'-'", 'term'], ['term']]), Rule('term', [['atom', "'*'", 'term'], ['atom', "'/'", 'atom'], ['atom']]), Rule('atom', [['NAME'], ['NUMBER'], ["'('", 'expr', "')'"]]), Rule('assignment', [['target', "'='", 'expr']]), Rule('target', [['NAME']]), Rule('if_statement', [["'if'", 'expr', "':'", 'statement']]), ] 

अब जब हमारे पास हमारे मेटा संकलक का पार्सिंग हिस्सा है, तो हम एक कोड जनरेटर बनाते हैं। साथ में वे एक प्रारंभिक मेटा संकलक बनाते हैं:

 def generate_parser_class(rules): print(f"class ToyParser(Parser):") for rule in rules: print() print(f" @memoize") print(f" def {rule.name}(self):") print(f" pos = self.mark()") for alt in rule.alts: items = [] print(f" if (True") for item in alt: if item[0] in ('"', "'"): print(f" and self.expect({item})") else: var = item.lower() if var in items: var += str(len(items)) items.append(var) if item.isupper(): print(" " + f"and ({var} := self.expect({item}))") else: print(f" " + f"and ({var} := self.{item}())") print(f" ):") print(f" " + f"return Node({rule.name!r}, [{', '.join(items)}])") print(f" self.reset(pos)") print(f" return None") 

यह कोड बहुत बदसूरत है, लेकिन यह काम करता है (प्रकार), और भविष्य में मैं इसे फिर से लिखूंगा।

for alt in rule.alts को स्पष्टीकरण की आवश्यकता हो सकती है: विकल्प में प्रत्येक तत्व के लिए, हम 3 विकल्पों में से एक चुनते हैं:

• यदि तत्व एक स्ट्रिंग शाब्दिक है, उदाहरण के लिए '+' , तो हम self.expect('+') उत्पन्न करते हैं।
• यदि तत्व पूरी तरह से अपरकेस है, उदाहरण के लिए NAME , तो हम जनरेट करते हैं (name := self.expect(NAME))
• अन्यथा, उदाहरण के लिए, अगर यह expr , तो हम जनरेट करते हैं (expr := self.expr())

यदि एक संस्करण में एक ही नाम के साथ कई तत्व हैं (उदाहरण के लिए, term '-' term ), तो हम दूसरे में एक अंक जोड़ते हैं। यहां एक छोटी सी गलती भी है जिसे मैं अगले एपिसोड में सही करूंगा।

यहां उनके काम का थोड़ा सा परिणाम है (पूरी कक्षा बहुत उबाऊ होगी)। अनावश्यक के बारे में चिंता न करें if (True and ... ) कोड की आवश्यकता है ताकि प्रत्येक उत्पन्न स्थिति के साथ शुरू हो सके and । पायथन बाइट कंपाइलर इसका अनुकूलन करता है।

 class ToyParser(Parser): @memoize def statement(self): pos = self.mark() if (True and (assignment := self.assignment()) ): return Node('statement', [assignment]) self.reset(pos) if (True and (expr := self.expr()) ): return Node('statement', [expr]) self.reset(pos) if (True and (if_statement := self.if_statement()) ): return Node('statement', [if_statement]) self.reset(pos) return None ... 

@memoize डेकोरेटर पर ध्यान @memoize : मैंने इसे एक अन्य विषय पर आगे बढ़ने के लिए पेश किया: उत्पन्न पार्सर को तेजी से बनाने के लिए @memoize का उपयोग करना।

यहाँ memoize() फ़ंक्शन है जो इस डेकोरेटर को लागू करता है:

 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 

अन्य सज्जाकारों की तरह, इसमें एक नेस्टेड फ़ंक्शन होता है जो एक सजाया गया फ़ंक्शन (या लपेटता है) एक सजाया गया फ़ंक्शन, उदाहरण के लिए, ToyParser क्लास का statement() विधि। चूंकि फ़ंक्शन को लपेटा जा रहा है, यह एक विधि है, आवरण भी वास्तव में एक विधि है: इसका पहला तर्क self को कहा जाता है और ToyParser इंस्टेंस को संदर्भित करता है जिसके लिए सजाया गया विधि कहा जाता है।

रैपर प्रत्येक इनपुट स्थिति के लिए विधि कॉल का परिणाम कैश करता है - यही कारण है कि इसे पैकरैट पार्सर कहा जाता है! [लगभग। प्रति। packrat एक "चोर" है, लेकिन यह शब्द रूसी भाषा के स्रोतों में अनुवादित नहीं है।] कैशे शब्दकोशों का एक शब्दकोश है, जो एक Parser उदाहरण में संग्रहीत है। बाहरी शब्दकोश की कुंजी इनपुट डेटा स्ट्रीम में स्थिति है; मैंने इसे प्रारंभ करने के लिए self.memos = {} को Parser .__ init__() भी जोड़ा। आंतरिक शब्दकोशों को आवश्यकतानुसार जोड़ा जाता है; उनकी कुंजियों में एक विधि और उसके तर्क होते हैं। (वर्तमान डिजाइन में कोई तर्क नहीं हैं, लेकिन हम expect() को याद कर expect() फ़ंक्शन जिसमें एक है, जो काफी महत्वपूर्ण है)

पार्सर विधि का परिणाम एक टपल के रूप में प्रस्तुत किया जाता है, क्योंकि वास्तव में दो मूल्य हैं: परिणाम स्वयं (हमारी उत्पन्न विधियों के लिए यह मिलान नियम के लिए Node ) और इनपुट स्ट्रीम में वर्तमान स्थिति के लिए एक संकेतक, जो self.mark() से मिलता है। इस प्रकार, हम ज्ञापन मूल्यों के साथ आंतरिक शब्दकोश में वापसी मूल्य ( res ) और नई स्थिति ( endpos ) दोनों को कैश करते हैं। एक ही इनपुट स्थिति में समान तर्कों के साथ एक ही पार्सिंग पद्धति के बाद के कॉल पर, हम उन्हें कैश से लेंगे। ऐसा करने के लिए, बस पॉइंटर को self.reset() स्थिति में self.reset() का उपयोग करके self.reset() और कैश में देखें।

नकारात्मक परिणामों को कैश करना भी महत्वपूर्ण है - वास्तव में, अधिकांश कॉल नकारात्मक होंगे। इस स्थिति में, वापसी मान None , और इनपुट स्थिति नहीं बदलती है। आप इसे जाँचने के लिए assert जोड़ सकते हैं।

नोट। पायथन में, memoize() फ़ंक्शन में स्थानीय चर में कैश को लागू करने के लिए प्रथागत है। हमारे मामले में, यह काम नहीं करेगा: जैसा कि मैंने डिबगिंग के बहुत अंत में पाया, प्रत्येक Parser उदाहरण का अपना कैश होना चाहिए। हालांकि, आप कुंजी के रूप में ( pos , func , args ) का उपयोग करके नेस्टेड शब्दकोशों से छुटकारा पा सकते हैं।

अगले हफ्ते मैं कोड और निशान तैयार करने के लिए दिखाऊंगा कि कैसे यह सब वास्तव में इकट्ठा किया जाता है और एक उदाहरण कार्यक्रम को पार्स करते समय निष्पादित किया जाता है। मैं अभी भी टोकन बफर, पार्सर और कैश के सहयोग की कल्पना करने के लिए एक बेहतर तरीके की तलाश में हूं। शायद मैं ASCII में केवल पाठ के रूप में ट्रेस लिस्टिंग प्रदर्शित करने के बजाय एक एनिमेटेड gif बनाने में सक्षम हो जाएगा।

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