पायथन (अनुवाद) # 1 में खरोंच से एक साधारण दुभाषिया

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


लेखों की इस श्रृंखला में, मैं साधारण अनिवार्य भाषा IMP (IMperative Language) के लिए एक साधारण दुभाषिया लिखकर इस सरलता को पकड़ने की कोशिश करूँगा। इंटरप्रेटर को पायथन में लिखा जाएगा क्योंकि यह एक सरल और व्यापक रूप से ज्ञात भाषा है। इसके अलावा, अजगर कोड स्यूडोकोड के समान है, और यहां तक ​​कि अगर आप इसे [अजगर] नहीं जानते हैं, तो आप कोड को समझने में सक्षम होंगे। खरोंच से लिखे गए कॉम्बीनेटर के एक सरल सेट का उपयोग करके पार्सिंग किया जाएगा (मैं आपको अगले भाग में अधिक बताऊंगा)। Sys (I / O के लिए), re (lexer में नियमित भाव) और unittest (हमारे शिल्प के स्वास्थ्य का परीक्षण करने के लिए) को छोड़कर कोई अतिरिक्त पुस्तकालयों का उपयोग नहीं किया जाएगा।

छोटा सा सार

सबसे पहले, आइए चर्चा करें कि हम एक दुभाषिया क्यों लिखेंगे। छोटा सा भूत निम्नलिखित निर्माणों के साथ एक सरल भाषा है:

असाइनमेंट (सभी चर वैश्विक हैं और केवल पूर्णांक स्वीकार करते हैं):

x := 1 

नियम और शर्तें:

 if x = 1 then y := 2 else y := 3 end 

जबकि लूप:

 while x < 10 do x := x + 1 end 

यौगिक संचालक (अलग हो गए):

 x := 1; y := 2 

यह सिर्फ एक खिलौना भाषा है। लेकिन आप इसका विस्तार पाइथन या लुआ जैसे उपयोगिता स्तर तक कर सकते हैं। मैं बस इसे उतना ही सरल रखना चाहता था जितना मैं कर सकता था।

और यहाँ एक कार्यक्रम का एक उदाहरण है जो भाज्य की गणना करता है:

 n := 5; p := 1; while n > 0 do p := p * n; n := n - 1 end 

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

दुभाषिया संरचना

दुभाषिया का मूल एक मध्यवर्ती प्रतिनिधित्व (IR) से अधिक कुछ नहीं है। यह स्मृति में हमारे आईएमपी कार्यक्रमों का प्रतिनिधित्व करेगा। चूंकि आईएम 3 रूबल के रूप में सरल है, आईआर सीधे भाषा के सिंटैक्स के अनुरूप होगा; हम वाक्य रचना की प्रत्येक इकाई के लिए एक वर्ग बनाएंगे। बेशक, अधिक जटिल भाषा में, आप एक शब्दार्थ निरूपण का उपयोग करना चाहेंगे, जो विश्लेषण या निष्पादन के लिए बहुत आसान है।

व्याख्या के केवल तीन चरण:

• पार्स स्रोत कोड पात्रों को टोकन में।
• एक सार वाक्यविन्यास पेड़ (एएसटी) में सभी टोकन ले लीजिए। एएसटी हमारी आईआर है।
• एएसटी निष्पादित करें और परिणाम को अंत में प्रिंट करें।

पात्रों को टोकन में विभाजित करने की प्रक्रिया को लेक्सिंग कहा जाता है, और लेक्सर ऐसा करता है। टोकन किसी प्रोग्राम के सबसे बुनियादी हिस्सों जैसे संख्याओं, पहचानकर्ताओं, कीवर्ड्स और ऑपरेटर्स वाले छोटे, सुपाच्य तार हैं। लेक्सर रिक्त स्थान और टिप्पणियों को छोड़ देगा, क्योंकि उन्हें दुभाषिया द्वारा अनदेखा किया जाता है।

एएसटी टोकन विधानसभा प्रक्रिया को पार्सिंग कहा जाता है। पार्सर हमारे कार्यक्रम की संरचना को एक ऐसे रूप में निकालता है जिसे हम निष्पादित कर सकते हैं।


यह लेख पूरी तरह से लेक्सर पर केंद्रित होगा। सबसे पहले, हम एक आम lex पुस्तकालय और फिर एक छोटा सा भूत के लिए लिखेंगे। निम्नलिखित भाग पार्सर और निष्पादक पर केंद्रित होंगे।

lexer

सच में, लेक्सिकल ऑपरेशन बहुत सरल हैं और नियमित अभिव्यक्तियों पर आधारित हैं। यदि आप उनसे परिचित नहीं हैं, तो आप आधिकारिक दस्तावेज पढ़ सकते हैं।

लेक्सर के लिए इनपुट अक्षरों की एक सरल धारा होगी। सरलता के लिए, हम इनपुट को मेमोरी में पढ़ेंगे। लेकिन आउटपुट टोकन की एक सूची होगी। प्रत्येक टोकन में एक मान और एक लेबल शामिल होता है (टैग, टोकन के प्रकार की पहचान करने के लिए)। पार्सर पेड़ (एएसटी) के निर्माण के लिए इसका उपयोग करेगा।

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

यहाँ lexer पुस्तकालय से कोड है:

 import sys import re def lex(characters, token_exprs): pos = 0 tokens = [] while pos < len(characters): match = None for token_expr in token_exprs: pattern, tag = token_expr regex = re.compile(pattern) match = regex.match(characters, pos) if match: text = match.group(0) if tag: token = (text, tag) tokens.append(token) break if not match: sys.stderr.write('Illegal character: %s\n' % characters[pos]) sys.exit(1) else: pos = match.end(0) return tokens 

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

लेक्सर छोटा सा भूत

ऊपर दिए गए कोड को देखते हुए, हमारी भाषा के लिए एक अक्षर बनाना बहुत सरल हो जाता है। सबसे पहले, आइए टोकन के लिए टैग की एक श्रृंखला को परिभाषित करें। एक भाषा के लिए आपको केवल 3 टैग चाहिए। आरक्षित शब्दों या ऑपरेटरों के लिए आरक्षित, संख्याओं के लिए INT , पहचानकर्ताओं के लिए आईडी ।

 import lexer RESERVED = 'RESERVED' INT = 'INT' ID = 'ID' 

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

 token_exprs = [ (r'[ \n\t]+', None), (r'#[^\n]*', None), 

उसके बाद हमारे सभी ऑपरेटर और आरक्षित शब्द अनुसरण करते हैं।

  (r'\:=', RESERVED), (r'\(', RESERVED), (r'\)', RESERVED), (r';', RESERVED), (r'\+', RESERVED), (r'-', RESERVED), (r'\*', RESERVED), (r'/', RESERVED), (r'<=', RESERVED), (r'<', RESERVED), (r'>=', RESERVED), (r'>', RESERVED), (r'=', RESERVED), (r'!=', RESERVED), (r'and', RESERVED), (r'or', RESERVED), (r'not', RESERVED), (r'if', RESERVED), (r'then', RESERVED), (r'else', RESERVED), (r'while', RESERVED), (r'do', RESERVED), (r'end', RESERVED), 

अंत में, हमें संख्याओं और पहचानकर्ताओं के लिए भाव चाहिए। कृपया ध्यान दें कि पहचानकर्ताओं के लिए नियमित अभिव्यक्ति उपरोक्त सभी आरक्षित शब्दों के अनुरूप होगी, इसलिए यह बहुत महत्वपूर्ण है कि ये दो पंक्तियाँ अंतिम हों।

  (r'[0-9]+', INT), (r'[A-Za-z][A-Za-z0-9_]*', ID), ] 

जब हमारे regexps को परिभाषित किया जाता है, तो हम lex फ़ंक्शन पर एक आवरण बना सकते हैं :

 def imp_lex(characters): return lexer.lex(characters, token_exprs) 

यदि आप इन शब्दों को पढ़ते हैं, तो आप सबसे अधिक रुचि रखते हैं कि हमारे चमत्कार कैसे काम करते हैं। यहाँ परीक्षण के लिए कोड है:

 import sys from imp_lexer import * if __name__ == '__main__': filename = sys.argv[1] file = open(filename) characters = file.read() file.close() tokens = imp_lex(characters) for token in tokens: print token 

 $ python imp.py hello.imp 

पूर्ण स्रोत डाउनलोड करें: imp-interpreter.tar.gz
मूल लेख के लेखक जे कॉनरोड हैं ।

UPD: टेम्प्लेट परिभाषित किए गए क्रम से संबंधित बग को ठीक करने के लिए उपयोगकर्ता zeLark का धन्यवाद।