हम एक आदिम और बेकार संकलक लिखते हैं

मेरा मानना ​​है कि हर प्रोग्रामर को अपना कंपाइलर लिखना चाहिए।

मैं खुद लंबे समय से मानता हूं कि संकलक का निर्माण अभिजात वर्ग की नियति है, और एक साधारण नश्वर प्रोग्रामर इस विज्ञान को समझ नहीं सकता है। मैं यह साबित करने की कोशिश करूंगा कि ऐसा नहीं है।

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

संकलनकर्ता पायथन में लिखा जाएगा। मैं वास्तव में इस भाषा से प्यार करता हूं, लेकिन कोड स्थानों में अनाड़ी हो सकता है। अगर कुछ गलत है - एक व्यक्तिगत में लिखें।

हां, कंपाइलर पूरी तरह से ब्लंटली है जो टाइनी-सी पर आधारित है।

व्याकरण

शुरू करने से पहले, आइए तय करें कि वास्तव में हमारी भाषा क्या कर पाएगी।
वह बहुत कम कर पाएगी:

- केवल डेटा प्रकार इंट है
- सभी चर वैश्विक हैं। कुल में 26 चर हैं (az)
- गणितीय कार्यों के लिए, केवल "+" और "-" समर्थित हैं
- एकमात्र तुलना ऑपरेटर "<" है
- भाषा निर्माणों से - सशर्त कथन यदि, यदि / नहीं तो, जबकि, कब / करते हैं

वह सब है। कोई सरणियाँ, कार्य, संरचनाएं। यहाँ हमारी भाषा में प्राप्त व्याकरण है:

 <program> ::= <statement> <statement> ::= "if" <paren-expr> <statement> | "if" <paren-expr> <statement> "else" <statement> | "while" <paren-expr> <statement> | "do" <statement> "while" <paren-expr> | "{" { <statement> } "}" | <expr> ";" | ";" <paren-expr> ::= "(" <expr> ")" <expr> ::= <test> | <id> "=" <expr> <test> ::= <sum> | <sum> "<" <sum> <sum> ::= <term> | <sum> "+" <term> | <sum> "-" <term> <term> ::= <id> | <int> | <paren-expr> <id> ::= "a" | "b" | ... | "z" <int> ::= <digit>, { <digit> } <digit> ::= "0" | "1" | ... | "9" 

यह EBNF के रूप में एक व्याकरण प्रविष्टि है। यहाँ इस प्रविष्टि का मोटे तौर पर मतलब है।

एक कार्यक्रम एकल कथन है।
ऑपरेटर्स सशर्त हैं (यदि..बेल ...), चक्रीय (जबकि ...), और बस ऑपरेटर (जैसे, "a = 2 + 3")।
सशर्त और चक्रीय में एक स्थिति अभिव्यक्ति और एक शरीर (एक ऑपरेटर के रूप में) होता है। सामान्य ऑपरेटर अर्धविराम के साथ समाप्त होते हैं। आप ऑपरेटरों को ब्रेसिज़ में समूहित कर सकते हैं, फिर हम एक कंपाउंड ऑपरेटर प्राप्त कर सकते हैं।
भाव या तो योग हैं या किसी मान के लिए एक चर का असाइनमेंट।
यहाँ, योग शब्दों के जोड़-घटाव का एक क्रम है।
एक शब्द कोष्ठकों में एक संख्या, चर या अभिव्यक्ति है।
चर z के माध्यम से वर्ण हैं। संख्याएँ 0 से 9 तक की संख्याओं का एक समूह हैं।

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

लेक्सिकल विश्लेषक

कंपाइलर एक टेक्स्ट फ़ाइल (स्रोत) प्राप्त करता है। इस फ़ाइल में टोकन निकालने के लिए एक शाब्दिक विश्लेषक की आवश्यकता होती है। यानी लाइन "a = 3 + 42;" लेक्सिकल विश्लेषक को "पहचानकर्ता: एक", "ऑपरेटर =", "नंबर 3", "ऑपरेटर +", "संख्या 42", "चरित्र" के रूप में मौजूद होना चाहिए। लेक्सिकल विश्लेषक केवल अक्षरों के अनुक्रम के साथ काम करता है, अर्थात्। उसके लिए, लाइन "अब अगर =" भी समझ में आता है और बिल्कुल सही है।

तो, हमारे शाब्दिक विश्लेषक को निम्नलिखित टोकन को पहचानना चाहिए:

- संख्या
- चर पहचानकर्ता
- कीवर्ड: यदि, और, जबकि, करते हैं
- वर्ण +, -, <, =, {,}, (,),;
- फाइल का अंत

यहाँ इसका स्रोत कोड कैसा दिखता है:

 class Lexer: NUM, ID, IF, ELSE, WHILE, DO, LBRA, RBRA, LPAR, RPAR, PLUS, MINUS, LESS, \ EQUAL, SEMICOLON, EOF = range(16) #    SYMBOLS = { '{': LBRA, '}': RBRA, '=': EQUAL, ';': SEMICOLON, '(': LPAR, ')': RPAR, '+': PLUS, '-': MINUS, '<': LESS } #   WORDS = { 'if': IF, 'else': ELSE, 'do': DO, 'while': WHILE } #  ,    ch = ' ' # ,   -   def error(self, msg): print 'Lexer error: ', msg sys.exit(1) def getc(self): self.ch = sys.stdin.read(1) def next_tok(self): self.value = None self.sym = None while self.sym == None: if len(self.ch) == 0: self.sym = Lexer.EOF elif self.ch.isspace(): self.getc() elif self.ch in Lexer.SYMBOLS: self.sym = Lexer.SYMBOLS[self.ch] self.getc() elif self.ch.isdigit(): intval = 0 while self.ch.isdigit(): intval = intval * 10 + int(self.ch) self.getc() self.value = intval self.sym = Lexer.NUM elif self.ch.isalpha(): ident = '' while self.ch.isalpha(): ident = ident + self.ch.lower() self.getc() if ident in Lexer.WORDS: self.sym = Lexer.WORDS[ident] elif len(ident) == 1: self.sym = Lexer.ID self.value = ord(ident) - ord('a') else: self.error('Unknown identifier: ' + ident) else: self.error('Unexpected symbol: ' + self.ch) 

अगले_टॉक () विधि में, विश्लेषक अगले टोकन को प्राप्त करता है। टोकन का प्रकार मान विशेषता से प्राप्त किया जा सकता है, और इसका मान (यदि यह एक चर या संख्या है) मान विशेषता से प्राप्त किया जा सकता है।

विश्लेषक रिक्त स्थान की अनदेखी करता है, यह जांचता है कि क्या वर्तमान चरित्र भाषा का एक विशेष चरित्र है, यदि नहीं, तो जांचता है कि यह संख्या या पहचानकर्ता है या नहीं। यानी अंक 1 से मुलाकात होने के बाद, विश्लेषक वर्णों को घटाना जारी रखेगा जब तक कि यह एक गैर-संख्यात्मक चरित्र का सामना नहीं करता है। पहचानकर्ताओं को उसी तरह से जांचा जाता है (अक्षर संख्या के बजाय)।

पार्सर

यह शायद हमारे संकलक का सबसे जटिल घटक है। लेक्सिकल एनालाइजर से प्राप्त टोकन का उपयोग करते हुए उनका कार्य एक प्रकार का वृक्ष बनाना है जिसमें पदानुक्रम और संबंध कोड की संरचना को दर्शाते हैं। उदाहरण के लिए:

 "if (a < 0) a = 5;" IF +-LESS | +-VAR(a) | +-NUM(0) +-SET +-VAR(a) +-NUM(5) 

पेड़ जो पार्सर द्वारा बनाया गया है उसमें नोड्स होते हैं। एक नोड में एक प्रकार (IF, LESS, SET, VAR ...), एक मान (यदि यह एक संख्या या एक चर है), और कई बाल ऑपरेंड नोड्स (कोड में - op1, op2, op3) हैं। यदि के लिए, स्थिति और फिर / अन्य शाखाएं उनमें संग्रहीत की जाती हैं, तो लूप के लिए, लूप की स्थिति और शरीर संग्रहीत होते हैं।

नोड्स का वर्णन करने के लिए, हम वर्ग नोड का परिचय देते हैं। यहाँ पार्सर वर्ग और नोड वर्ग के लिए कोड है:

 class Node: def __init__(self, kind, value = None, op1 = None, op2 = None, op3 = None): self.kind = kind self.value = value self.op1 = op1 self.op2 = op2 self.op3 = op3 class Parser: VAR, CONST, ADD, SUB, LT, SET, IF1, IF2, WHILE, DO, EMPTY, SEQ, EXPR, PROG = range(14) def __init__(self, lexer): self.lexer = lexer def error(self, msg): print 'Parser error:', msg sys.exit(1) def term(self): if self.lexer.sym == Lexer.ID: n = Node(Parser.VAR, self.lexer.value) self.lexer.next_tok() return n elif self.lexer.sym == Lexer.NUM: n = Node(Parser.CONST, self.lexer.value) self.lexer.next_tok() return n else: return self.paren_expr() def summa(self): n = self.term() while self.lexer.sym == Lexer.PLUS or self.lexer.sym == Lexer.MINUS: if self.lexer.sym == Lexer.PLUS: kind = Parser.ADD else: kind = Parser.SUB self.lexer.next_tok() n = Node(kind, op1 = n, op2 = self.term()) return n def test(self): n = self.summa() if self.lexer.sym == Lexer.LESS: self.lexer.next_tok() n = Node(Parser.LT, op1 = n, op2 = self.summa()) return n def expr(self): if self.lexer.sym != Lexer.ID: return self.test() n = self.test() if n.kind == Parser.VAR and self.lexer.sym == Lexer.EQUAL: self.lexer.next_tok() n = Node(Parser.SET, op1 = n, op2 = self.expr()) return n def paren_expr(self): if self.lexer.sym != Lexer.LPAR: self.error('"(" expected') self.lexer.next_tok() n = self.expr() if self.lexer.sym != Lexer.RPAR: self.error('")" expected') self.lexer.next_tok() return n def statement(self): if self.lexer.sym == Lexer.IF: n = Node(Parser.IF1) self.lexer.next_tok() n.op1 = self.paren_expr() n.op2 = self.statement() if self.lexer.sym == Lexer.ELSE: n.kind = Parser.IF2 self.lexer.next_tok() n.op3 = self.statement() elif self.lexer.sym == Lexer.WHILE: n = Node(Parser.WHILE) self.lexer.next_tok() n.op1 = self.paren_expr() n.op2 = self.statement(); elif self.lexer.sym == Lexer.DO: n = Node(Parser.DO) self.lexer.next_tok() n.op1 = self.statement() if self.lexer.sym != Lexer.WHILE: self.error('"while" expected') self.lexer.next_tok() n.op2 = self.paren_expr() if self.lexer.sym != Lexer.SEMICOLON: self.error('";" expected') elif self.lexer.sym == Lexer.SEMICOLON: n = Node(Parser.EMPTY) self.lexer.next_tok() elif self.lexer.sym == Lexer.LBRA: n = Node(Parser.EMPTY) self.lexer.next_tok() while self.lexer.sym != Lexer.RBRA: n = Node(Parser.SEQ, op1 = n, op2 = self.statement()) self.lexer.next_tok() else: n = Node(Parser.EXPR, op1 = self.expr()) if self.lexer.sym != Lexer.SEMICOLON: self.error('";" expected') self.lexer.next_tok() return n def parse(self): self.lexer.next_tok() node = Node(Parser.PROG, op1 = self.statement()) if (self.lexer.sym != Lexer.EOF): self.error("Invalid statement syntax") return node 

यह पार्सर पार्स () पद्धति से शुरू होकर पुनरावर्ती कार्य करता है।
सबसे पहले, वह "प्रोग्राम" नोड बनाता है, जिसका बच्चा प्रोग्राम का मुख्य ऑपरेटर बन जाता है।

ऑपरेटर कथन () विधि में उत्पन्न होते हैं। इस विधि में, पहले टोकन की जाँच की जाती है और यदि, अगर / और, जबकि, करते / करते समय, एक यौगिक कथन (यदि यह एक घुंघराले ब्रेस के साथ शुरू होता है), या अर्धविराम के साथ समाप्त होने वाला सिर्फ एक बयान बनता है।

ऑपरेटरों का निर्माण करते समय, एक्सप्रेशन () विधियों का उपयोग किया जाता है - अभिव्यक्ति और paren_expr () - ब्रैकेट में अभिव्यक्ति प्राप्त करने के लिए।

अभिव्यक्तियों को उन चेक से बनाया जाता है जो उन शब्दों से निर्मित होते हैं जो शब्दों से युक्त होते हैं। और, बदले में, कोष्ठकों में संख्याओं, चर और भावों से मिलकर बनता है। उस घर में जिसे जैक ने बनवाया था।

ऐसी पुनरावृत्ति। जैसा कि आप देख सकते हैं, विधियाँ ऊपर वर्णित व्याकरण की अवधारणाओं के अनुरूप हैं।

पार्स () विधि के आउटपुट में, हमें कक्षा नोड की एक वस्तु मिलती है जिसमें हमारे कार्यक्रम का पेड़ होता है। इस पेड़ को अब मशीन कोड में बदला जा सकता है।

मशीन कोड

हम अपने विशेष वर्चुअल मशीन के एक साधारण बायोटेक में संकलित करेंगे। वर्चुअल मशीन को स्टैक किया जाएगा क्योंकि वे रजिस्टर की तुलना में बहुत सरल हैं। यहाँ उसके संभावित निर्देश हैं:

 FETCH x -      x STORE x -    x     PUSH n -   n    POP -      ADD -       SUB -       LT -       (a < b).  - 0  1 JZ a -     0 -    a. JNZ a -      0 -    a. JMP a -    a HALT -   

उदाहरण के लिए, ऑपरेटर "ए = 2; b = 5; "निर्देशों के निम्नलिखित अनुक्रम में परिवर्तित किया गया है:

 PUSH 2 STORE 0 PUSH 5 STORE 1 

वर्चुअल मशीन कोड बहुत सरल है। यह सभी रन विधि में वर्णित है:

 IFETCH, ISTORE, IPUSH, IPOP, IADD, ISUB, ILT, JZ, JNZ, JMP, HALT = range(11) class VirtualMachine: def run(self, program): var = [0 for i in xrange(26)] stack = [] pc = 0 while True: op = program[pc] if pc < len(program) - 1: arg = program[pc+1] if op == IFETCH: stack.append(var[arg]); pc += 2 elif op == ISTORE: var[arg] = stack.pop(); pc += 2 elif op == IPUSH: stack.append(arg); pc += 2 elif op == IPOP: stack.append(arg); stack.pop(); pc += 1 elif op == IADD: stack[-2] += stack[-1]; stack.pop(); pc += 1 elif op == ISUB: stack[-2] -= stack[-1]; stack.pop(); pc += 1 elif op == ILT: if stack[-2] < stack[-1]: stack[-2] = 1 else: stack[-2] = 0 stack.pop(); pc += 1 elif op == JZ: if stack.pop() == 0: pc = arg else: pc += 2 elif op == JNZ: if stack.pop() != 0: pc = arg else: pc += 2 elif op == JMP: pc = arg; elif op == HALT: break print 'Execution finished.' for i in xrange(26): if var[i] != 0: print '%c = %d' % (chr(i+ord('a')), var[i]) 

यह वास्तविक संकलक - कोड जनरेटर लिखने के लिए रहता है।

संकलक

हमारी रचना का ताज। यहाँ इसका स्रोत कोड है:

 class Compiler: program = [] pc = 0 def gen(self, command): self.program.append(command) self.pc = self.pc + 1 def compile(self, node): if node.kind == Parser.VAR: self.gen(IFETCH) self.gen(node.value) elif node.kind == Parser.CONST: self.gen(IPUSH) self.gen(node.value) elif node.kind == Parser.ADD: self.compile(node.op1) self.compile(node.op2) self.gen(IADD) elif node.kind == Parser.SUB: self.compile(node.op1) self.compile(node.op2) self.gen(ISUB) elif node.kind == Parser.LT: self.compile(node.op1) self.compile(node.op2) self.gen(ILT) elif node.kind == Parser.SET: self.compile(node.op2) self.gen(ISTORE) self.gen(node.op1.value) elif node.kind == Parser.IF1: self.compile(node.op1) self.gen(JZ); addr = self.pc; self.gen(0); self.compile(node.op2) self.program[addr] = self.pc elif node.kind == Parser.IF2: self.compile(node.op1) self.gen(JZ); addr1 = self.pc; self.gen(0) self.compile(node.op2) self.gen(JMP); addr2 = self.pc; self.gen(0) self.program[addr1] = self.pc self.compile(node.op3) self.program[addr2] = self.pc elif node.kind == Parser.WHILE: addr1 = self.pc self.compile(node.op1) self.gen(JZ); addr2 = self.pc; self.gen(0) self.compile(node.op2) self.gen(JMP); self.gen(addr1); self.program[addr2] = self.pc elif node.kind == Parser.DO: addr = self.pc self.compile(node.op1) self.compile(node.op2) self.gen(JNZ); self.gen(addr); elif node.kind == Parser.SEQ: self.compile(node.op1) self.compile(node.op2) elif node.kind == Parser.EXPR: self.compile(node.op1); self.gen(IPOP) elif node.kind == Parser.PROG: self.compile(node.op1); self.gen(HALT) return self.program 

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

सशर्त बयानों और छोरों में चाल पर ध्यान दें। JMP / JZ के बाद, हम पहले 0 लिखते हैं, और जब शाखा स्वयं संकलित होती है और जिस पते पर हमें जाने की आवश्यकता होती है, उसे जाना जाता है, इसलिए इस शाखा को निष्पादित नहीं करने के लिए - मान 0 को वास्तविक पते में बदल दिया जाता है।

परीक्षण

यहाँ पूरा संकलक स्रोत निहित है। मैंने चलाने और जांच करने के लिए एक स्क्रिप्ट का उपयोग किया (मेरे पास स्टैडर से पढ़े गए लेक्सर हैं):

 echo " i = 3;" | ./cc.py echo " { a=3; b=5; }" | ./cc.py echo " { a = 1; b = 2; c = a + b; }" | ./cc.py echo " { a = 5; b = 2; c = a - b; }" | ./cc.py echo " { a = 5; b = 2; c = b < a; }" | ./cc.py echo " { a = 5; if (a < 10) a = 33; }" | ./cc.py echo " { a = 5; if (10 < a) a = 33; else { a = 1; b = 2; } }" | ./cc.py echo " { a = 10; do { a = a - 2;} while (3 < a); }" | ./cc.py echo " { a = 1; b = 5; while (a < b) { a = a + 3; }}" | ./cc.py 

कार सही जवाब देने के लिए लग रहा था।

आगे क्या है?

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