पायथन # 2 में खरोंच से एक साधारण दुभाषिया

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

पार्सर कॉम्बिनेटर क्या हैं?

पार्सर लिखने के बहुत सारे तरीके हैं। ऐसा करने का सबसे आसान और तेज़ तरीका कॉम्बिनेटरों के साथ है ।

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

हमारे छोटे से कंबाइनेटर

विश्लेषक कॉम्बिनेटर काफी सामान्य, सामान्य हैं , और किसी भी भाषा के लिए उपयोग किए जा सकते हैं। हम कॉम्बिनेटरों के एक अज्ञेय पुस्तकालय को लिखने से शुरू करते हैं, जैसा कि हमने लेक्सर के साथ किया था, और फिर इसका उपयोग एक पार्सर लिखने के लिए करते हैं।

आरंभ करने के लिए, एक परिणाम वर्ग बनाएं। प्रत्येक पार्सर परिणाम की श्रेणी (यदि सफल), या विफलता के मामले में कोई भी नहीं लौटाएगा। परिणाम में मान (मान, एएसटी का हिस्सा) और स्थिति (स्ट्रीम में अगले टोकन का सूचकांक) शामिल हैं।

class Result: def __init__(self, value, pos): self.value = value self.pos = pos def __repr__(self): return 'Result(%s, %d)' % (self.value, self.pos) 

आगे हम मुख्य पार्सर क्लास बनाएंगे। इससे पहले, मैंने कहा कि पार्सर्स ऐसे कार्य हैं जो टोकन की एक धारा को स्वीकार करते हैं। वास्तव में, हम पार्सर्स को __call__ विधि के साथ ऑब्जेक्ट के रूप में परिभाषित करेंगे । इसका मतलब यह है कि पार्सर ऑब्जेक्ट एक फ़ंक्शन के रूप में व्यवहार करेगा, लेकिन हम स्टेटमेंट बनाकर अतिरिक्त कार्यक्षमता भी प्रदान कर सकते हैं।

 class Parser: def __call__(self, tokens, pos): return None # subclasses will override this def __add__(self, other): return Concat(self, other) def __mul__(self, other): return Exp(self, other) def __or__(self, other): return Alternate(self, other) def __xor__(self, function): return Process(self, function) 

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

__Add__, __mul__, __or__ और __xor__ परिभाषित करने के तरीके , *, * | और ^ ऑपरेटरों, क्रमशः। प्रत्येक ऑपरेटर एक विशिष्ट कॉम्बीनेटर को कॉल करने के लिए एक शॉर्टकट प्रदान करता है। हम उनमें से प्रत्येक को संक्षेप में कवर करेंगे।

अब हम एक साधारण कॉम्बिनेटर को देखते हैं जिसे आरक्षित कहा जाता है । आरक्षित शब्दों और ऑपरेटरों को पार्स करने के लिए आरक्षित का उपयोग किया जाएगा; यह एक विशिष्ट मूल्य और टैग के साथ टोकन स्वीकार करेगा। याद रखें कि टोकन एक मूल्य-टैग जोड़ी है। टोकन [0] - मान, टोकन [1] - टैग।

 class Reserved(Parser): def __init__(self, value, tag): self.value = value self.tag = tag def __call__(self, tokens, pos): if pos < len(tokens) and \ tokens[pos][0] == self.value and \ tokens[pos][1] is self.tag: return Result(tokens[pos][0], pos + 1) else: return None 

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

हम आगे बढ़ते हैं। टैग कॉम्बिनेटर आरक्षित के समान है। यह एक विशिष्ट टैग से मेल खाते हुए टोकन ढूंढता है। मूल्य कुछ भी हो सकता है।

 class Tag(Parser): def __init__(self, tag): self.tag = tag def __call__(self, tokens, pos): if pos < len(tokens) and tokens[pos][1] is self.tag: return Result(tokens[pos][0], pos + 1) else: return None 

टैग और आरक्षित कॉम्बीनेटर हमारे आदिम हैं। अन्य सभी कॉम्बिनेटरों को सबसे बुनियादी स्तर पर उनसे बनाया जाएगा।

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

 class Concat(Parser): def __init__(self, left, right): self.left = left self.right = right def __call__(self, tokens, pos): left_result = self.left(tokens, pos) if left_result: right_result = self.right(tokens, left_result.pos) if right_result: combined_value = (left_result.value, right_result.value) return Result(combined_value, right_result.pos) return None 

कॉनकट टोकन के एक विशिष्ट अनुक्रम को पार्स करने के लिए उपयोगी है। उदाहरण के लिए, 1 + 2 को पार्स करने के लिए, आप लिख सकते हैं

 parser = Concat(Concat(Tag(INT), Reserved('+', RESERVED)), Tag(INT)) 

या संक्षेप में शॉर्टहैंड ऑपरेटर का उपयोग करना

 parser = Tag(INT) + Reserved('+', RESERVED) + Tag(INT) 

अल्टरनेटिव कॉम्बिनेटर भी पिछले वाले से काफी मिलता-जुलता है। यह बाएं- और दाएं-बाएं को भी स्वीकार करता है। यदि सफल होता है, तो परिणाम वापस आ जाता है, अन्यथा - यह एक सही-पार्सर लेता है और अपना परिणाम देता है।

 class Alternate(Parser): def __init__(self, left, right): self.left = left self.right = right def __call__(self, tokens, pos): left_result = self.left(tokens, pos) if left_result: return left_result else: right_result = self.right(tokens, pos) return right_result 

वैकल्पिक संभव है जब संभव पार्सर का चयन। उदाहरण के लिए, यदि हमें एक बाइनरी ऑपरेटर को पार्स करने की आवश्यकता है:

 parser = Reserved('+', RESERVED) | Reserved('-', RESERVED) | Reserved('*', RESERVED) | Reserved('/', RESERVED) 

ऑप्ट क्लास अतिरिक्त पाठ के लिए उपयोगी है, जैसे कि अन्य। इसमें एक पार्सर लगता है। यदि यह पार्सर सफल होता है, तो परिणाम सामान्य रूप से लौटता है। यदि नहीं, तो एक सफल परिणाम वैसे भी वापस आ जाता है, लेकिन इसका मूल्य कोई नहीं है। विफलता के मामले में टोकन का सेवन नहीं किया जाता है; परिणाम की स्थिति इनपुट स्थिति के समान है।

 class Opt(Parser): def __init__(self, parser): self.parser = parser def __call__(self, tokens, pos): result = self.parser(tokens, pos) if result: return result else: return Result(None, pos) 

प्रतिनिधि पार्सर को तब तक स्वीकार करता है जब तक कि यह क्रैश (विफल) न हो जाए। यह सूची बनाने के लिए उपयोगी है। याद रखें कि रेप सफलतापूर्वक एक खाली सूची से मेल खाएगा और यदि पार्सर पहली बार विफल होता है तो टोकन को अवशोषित नहीं करेगा।

 class Rep(Parser): def __init__(self, parser): self.parser = parser def __call__(self, tokens, pos): results = [] result = self.parser(tokens, pos) while result: results.append(result.value) pos = result.pos result = self.parser(tokens, pos) return Result(results, pos) 

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

 class Process(Parser): def __init__(self, parser, function): self.parser = parser self.function = function def __call__(self, tokens, pos): result = self.parser(tokens, pos) if result: result.value = self.function(result.value) return result 

एक उदाहरण के रूप में, उस पार्सर पर विचार करें जिसे हमने कॉनैट का उपयोग करके बनाया था। जब यह 1 + 1 को पार्स करता है, तो परिणाम (('1', '+'), '2') होगा , जो बहुत सुविधाजनक नहीं है। प्रक्रिया के साथ, हम परिणाम बदल सकते हैं। निम्न कोड उदाहरण के लिए, इन दोनों संख्याओं का योग लौटाएगा।

 def process_func(parsed): ((l, _), r) = parsed return int(l) + int(r) better_parser = parser ^ process_func 

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

 class Lazy(Parser): def __init__(self, parser_func): self.parser = None self.parser_func = parser_func def __call__(self, tokens, pos): if not self.parser: self.parser = self.parser_func() return self.parser(tokens, pos) 

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

 class Phrase(Parser): def __init__(self, parser): self.parser = parser def __call__(self, tokens, pos): result = self.parser(tokens, pos) if result and result.pos == len(tokens): return result else: return None 

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

 a := 10; b := 20; c := 30 

इस मामले में, हमारे पास उन बयानों की एक सूची है जो एक अर्धविराम द्वारा अलग किए गए हैं। आप सोच सकते हैं कि हमें एक्सप की जरूरत नहीं है, क्योंकि हम अन्य कॉम्बिनेटरों के साथ भी ऐसा कर सकते हैं। आप इस तरह के भाव के लिए एक पार्सर लिख सकते हैं:

 def compound_stmt(): return stmt() + Reserved(';', RESERVED) + stmt() 

Stmt बनाना:

 def stmt(): return Lazy(compound_stmt) | assign_stmt() 

तो stmt कॉम्प्लेक्स_stmt कॉल करता है, जो stmt कहता है। जब तक हमें एक बफर ओवरफ़्लो नहीं मिलेगा, वे एक दूसरे को कॉल करेंगे। यह समस्या यौगिक कथनों के लिए अद्वितीय नहीं है, और इसे बाईं पुनरावृत्ति कहा जाता है।

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

आइए कोड को देखें:

 class Exp(Parser): def __init__(self, parser, separator): self.parser = parser self.separator = separator def __call__(self, tokens, pos): result = self.parser(tokens, pos) def process_next(parsed): (sepfunc, right) = parsed return sepfunc(result.value, right) next_parser = self.separator + self.parser ^ process_next next_result = result while next_result: next_result = next_parser(tokens, result.pos) if next_result: result = next_result return result 

परिणाम में वह सब कुछ होगा जो पूरे समय के लिए पार्स किया गया है। Process_next फ़ंक्शन का उपयोग प्रोसेस कॉम्बिनेटर के साथ किया जा सकता है। अगली सूची आइटम प्राप्त करने के लिए next_parser एक विभाजक और फिर पार्सर लेता है। process_next वर्तमान परिणाम पर और हौसले से बने तत्व पर एक विभाजक फ़ंक्शन को स्वीकार करके एक नया परिणाम तैयार करेगा। next_parser को एक लूप में लिया जाता है जबकि यह तत्वों को स्वीकार करने में सक्षम होगा।

आइए देखें कि Exp कैसे कंपाउंड_स्टेम समस्या को हल करने के लिए इस्तेमाल किया जा सकता है:

 def assign_stmt(): ... def compound_sep(): def process_sep(parsed): return lambda l, r: CompoundStmt(l, r) return Reserved(';', RESERVED) ^ process_sep def compound_stmt(): return Exp(assign_stmt(), compound_sep()) 

हम भी लिख सकते हैं:

 def compound_stmt(): return assign_stmt() * compound_sep() 

जब हम अगले लेख में अंकगणित के भावों को देखेंगे तो हम इस पर ध्यान देंगे।

पूर्ण स्रोत डाउनलोड करें: imp-interpreter.tar.gz