Всем привет, сегодня мы с вами напишем компилятор на Python. Мало чего он будет уметь, но для начала сойдёт.
Структура компилятора
Всего 4 этапа:
-
Лексер со своими токенами
-
Парсер со своим AST
-
Сам компилятор со своими байткодом
-
И напоследок виртуальная машина
Лексер токенизирует часть строки (к примеру a = 5)
Парсер делает АСД а поток токенов создает он сам
Компилятор превращает АСД в байт код (PUSH 5 STORE a HALT)
А виртуальная машина выполняет байткод.
Правила нашего компилятора
Вот набор правил для компилятора:
-
Цикл while, условие if-else. Никакого for
-
Переменные делаются так: a = 5 если объявление последнее в строке, иначе a = 5; …
-
Максимум выражения 2+2 но не как не 2+2==4 и они разделены пробелами (2 + 2)
-
RelOp (Relation operation, реляционные операция): <, >, !=, ==
-
BinOp (Binary operation, бинарная операция): +, -, *, /
-
В цикле while и условие if-else максимум присваивание и одну
-
Переменные с любым названием
-
Команда для игнорирования («pass») и для выхода во время выполнения («exit»)
-
Один тип данных: int
Да, никаких списков, функций, словарей и другого. Вот такая BNF получилась:
<program> ::= <statement> <statement> ::= <while> | <if> | <assign> <while> ::= "while " <paren_expr> " " <statement> <if> ::= "if " <paren_expr> " " <statement> | "if " <paren_expr> " " <statement> " else " <statement> <paren_expr> ::= "(" <exp> ")" <assign> ::= <indent> " = " <exp> "; " | <indent> " = " <exp> <indent> ::= [a-z] | [A-Z] <digit> ::= [0-9] <exit> = "exit" <pass> = "pass" <exp> ::= <term> | <bexp> | <aexp> <term> ::= <digit> | <indent> <bexp> ::= <term> " > " <term> | <term> " < " <term> | <term> " == " <term> | <term> " != " <term> <aexp> ::= <term> " + " <term> | <term> " - " <term> | <term> " * " <term> | <term> " / " <term>(если что-то не так то скажите, я мало BNF понимаю) пример программы:
a = 5; if (a < 10) a = 10; else a = 5Пишем лексер
Как я говорил ранее, лексер токенизирует лишь один токен но из-за парсера получается поток токенов. Вот код самого лексера:
#для регулярок import re #лексер class Lexer: def __init__(self): pass #распознать терм (в нашем случае это переменная или число) def lexterm(self, term): #регулярка для переменной if re.match(r'[a-zA-Z][a-zA-Z0-9_]*', term): return ('id', term) #регулярка для чисел elif re.match(r'[0-9]+', term): return ('num', term) #возращает два терма и операцию по середине (индекс 1) def lex_expr(self, exp): res = exp.split(' ') if len(res) == 1: return (self.lexterm(res[0]), res[0]) first = self.lexterm(res[0]) second = self.lexterm(res[2]) return [first, res[1], second] def lex_token(self, string): #здесь результат self.sum = None d = string.split(' ') #проверка if d[0] == 'while': d = string.split(')') try: cond = d[0][d[0].index('while') + 6:] + ')' except: raise SyntaxError('Invalid paren expression') try: stmt = d[1][1:] except: raise SyntaxError('Invalid "while" statement') self.sum = ("while", cond, stmt) return None elif d[0] == 'if': d = string.split(')') try: cond = d[0][d[0].index('if') + 3:] + ')' except: raise SyntaxError('Invalid paren expression') try: stmt = d[1][1:] except: raise SyntaxError('Invalid "if" statement') self.sum = ("if", cond, stmt) return None #остальные операторы или необязательные стэйтменты elif d[0] == 'pass': self.sum = ("pass", None) return None #иначе elif d[0] == 'else': stmt = string.replace('else ', '') if stmt == '': raise SyntaxError('Invalid "else" statement') self.sum = ("else", stmt) return None elif d[0] == 'exit': self.sum = ('exit', None) return None try: #присвание if d[1] == '=': name = d[0] valu = d[2:] pos = 0 value = '' while pos < len(valu): if pos + 1 == len(valu): value += valu[pos] else: value += valu[pos] + ' ' pos += 1 self.sum = ("assign", name, value) return None except: pass #иначе raise SyntaxError('Invalid syntax: '+str(string))Почему я поместил оператор присваивания в try-except? Потому-что если его нету то будет неправильный индекс в списке «d».
Извините за такие отвратительные названия, нормального не могу придумаю.
Как использовать:
#в PyShell >>> lexer = Lexer() >>> lexer.lex_token('a = 5') >>> token = lexer.sum >>> token ('assign', 'a', '5')Написать лексер мне было проще всего, а сложнее всего было написать парсер и компилятор (логично)
Парсер
Как работает:
На вход подается однострочная программа (и возможно не только однострочная, я не пробывал) пример:
a = 5; while (a < 10) a = a + 1Парсер получает эти токены:
('assign', 'a', '5') ('while', '(a < 10)', 'a = a + 1')И преобразует их в это AST:
Node('ASSIGN', 'a', op2=Node('INT', '5') ) Node('WHILE', Node('<', Node('ID', 'a'), op2=Node('INT', '10')), op2=Node('ASSIGN', 'a', op2=Node('+', Node('ID', 'a'), Node('INT', '1')) ) )AST очень запутанный но просто скопируйте эту часть кода и кайфуйте. AST — это предпоследняя часть компиляции.
Для начало код для класса узла AST:
class Node: def __init__(self, name, op1, op2=None, op3=None): self.name = name self.op1 = op1 self.op2 = op2 self.op3 = op3 def __repr__(self): return f'Node("{self.name}"\n {self.op1}\n {self.op2}\n {self.op3})'Параметр op3 нужен для таких условий как else.
Давайте я покажу вам код парсера:
class Parser: def __init__(self, lexer): self.pos = 0 self.lexer = lexer #терм def term(self, value): if value[0] == 'id': return 'ID' elif value[0] == 'num': return 'INT' #выражения def parse_expr(self, token): try: left = token[0] right = token[2] op = token[1] result = Node(op, Node(self.term(left), left[1]), Node(self.term(right), right[1])) return result except: try: return Node(self.term(left), left[1]) except: raise SyntaxError('Invalid expression') #выражения в скобках def paren_expr(self, expr): d = expr[expr.index('(') + 1:expr.index(')')] return self.parse_expr(self.lexer.lex_expr(d)) #парсинг def parse(self, program): try: self.prog = program.split('; ') except: self.prog = program astpos = 0 ast = [] while self.pos < len(self.prog): if self.prog[self.pos] == '': self.pos += 1 continue d = self.prog[len(self.prog) - 1] r = len(d) - 1 if d[r] == ';': raise SyntaxError('The ";" sign is not needed at the end') self.lexer.next_token(self.prog[self.pos]) token = self.lexer.sum if token[0] == 'assign': ast.append(Node('ASSIGN', token[1], op2=self.parse_expr(self.lexer.lex_expr(token[2])))) elif token[0] == 'if': d = Lexer() r = Parser(d) ast.append(Node('IF', self.paren_expr(token[1]), op2=r.parse(token[2])[0])) elif token[0] == 'while': d = Lexer() r = Parser(d) ast.append(Node('WHILE', self.paren_expr(token[1]), op2=r.parse(token[2])[0])) elif token[0] == 'else': d = Lexer() r = Parser(d) if ast[astpos - 1].name == 'IF': ast[astpos - 1].name = 'ELSE' ast[astpos - 1].op3 = r.parse(token[1])[0] else: raise SyntaxError('Invalid "else" statement') elif token[0] == 'exit': ast.append(Node('EXIT', None)) elif token[0] == 'pass': ast.append(Node('PASS', None)) self.pos += 1 astpos += 1 self.pos = 0 return astМетод term возвращает ‘ID’ если он увидел то что лексер распознал имя переменной или ‘INT’ если это число.
parse_expr — возвращает узел AST где имя это оператор а op1 это term первого токена а op2 это term второго токена. Если неудача: вернёт term первого токена
paren_expr — находить выражение в скобках и возвращает parse_expr
parse — сам парсер, находит все части программы и парсит их. А точнее наша программа с циклом while (a = 5; while (a < 10) a = a + 1) он находит в ней не «;» а «;» с пробелом. И наша программа становится такой:
['a = 5', 'while (a < 10) a = a + 1']Дальше если парсер узнает что в последнем элементе, в последнем индексе не «;» то он проходится по каждой части и получает результат лексера для каждой части. Иначе: говорить что-то по типу этого: «зачем тебе «;» в конце?».
Дальше по этим токенам он находит подходящий узел. Если это «else» то он будет обязан найти if в прошлом узле (для этого нужна переменная astpos). Потом обновляем позицию и возвращаем список с AST.
Компилятор
Эта часть главная ведь это компилятор. Вот инструкции:
FETCH переменная - положить на стек значение переменной PUSH число - положить на стек число POP - я не помню зачем это ведь это не нужно будет нам ADD, SUB, MUL, DIV - бинарные операции NOTEQ, EQ, LT, GT - реляционные операции JMP адрес - перейти по адресу JNZ адрес - перейти по адресу если на вершине стека не 0 JZ адрес - перейти по адресу если на вершине стека 0 PASS - игнорировать STORE имя - сделать переменную HALT - конец программыТеперь определим опкоды для инструкций:
FETCH, STORE, PUSH, POP, ADD, SUB, MUL, DIV, LT, GT, EQ, NOTEQ, JZ, JNZ, JMP, PASS, HALT = range(17)Вот допустим у нас выражение «a = 1 + 2», и компилятор создаёт эти инструкции:
PUSH 1 PUSH 2 ADD STORE aНо. Это только визуально. По нашем опкодам это будет так:
[2, 1, 2, 2, 4, 1, 'a']2 это PUSH
4 это ADD
1 это STORE.
И вот код компилятора:
class Compiler: def __init__(self): self.program = [] self.pc = 0 def gen(self, command): self.program.append(command) self.pc = self.pc + 1 def compilenode(self, node): name = node.name if name == 'INT': self.gen(PUSH) self.gen(int(node.op1)) elif name == 'ID': self.gen(FETCH) self.gen(node.op1) elif name == '+': self.compilenode(node.op1) self.compilenode(node.op2) self.gen(ADD) elif name == '-': self.compilenode(node.op1) self.compilenode(node.op2) self.gen(SUB) elif name == '/': self.compilenode(node.op1) self.compilenode(node.op2) self.gen(DIV) elif name == '*': self.compilenode(node.op1) self.compilenode(node.op2) self.gen(MUL) elif name == '<': self.compilenode(node.op1) self.compilenode(node.op2) self.gen(LT) elif name == '>': self.compilenode(node.op1) self.compilenode(node.op2) self.gen(GT) elif name == '!=': self.compilenode(node.op1) self.compilenode(node.op2) self.gen(NOTEQ) elif name == '==': self.compilenode(node.op1) self.compilenode(node.op2) self.gen(EQ) elif name == 'ASSIGN': self.compilenode(node.op2) self.gen(STORE) self.gen(node.op1) elif name == 'IF': self.compilenode(node.op1) self.gen(JZ) addr = self.pc self.gen(0) self.compilenode(node.op2) self.program[addr] = self.pc elif name == 'ELSE': self.compilenode(node.op1) self.gen(JZ) addr1 = self.pc self.gen(0) self.compilenode(node.op2) self.gen(JMP) addr2 = self.pc self.gen(0) self.program[addr1] = self.pc self.compilenode(node.op3) self.program[addr2] = self.pc elif name == 'WHILE': if node.op1.op2: try: r = node.op1.op2 d = str(int(r.op1) - 1) r.op1 = d except: r = node.op1.op1 d = str(int(r.op1) - 1) r.op1 = d addr1 = self.pc self.compilenode(node.op1) self.gen(JZ) addr2 = self.pc self.gen(1) self.compilenode(node.op2) self.gen(JMP) self.gen(addr1) self.program[addr2] = self.pc elif name == 'EXIT': self.gen(HALT) elif name == 'PASS': self.gen(PASS) def compileast(self, ast): for i in ast: self.compilenode(i) self.gen(HALT) return self.programКак вы можете заместить в обработке WHILE, для чисел я отнимаю одно число у этого числа, почему? Потому что когда я делал это то while делал не 5 а 6 раз. И, спасибо статье Пишем примитивный и никому не нужный компилятор / Хабр (не реклама) за то что она дала мне понятие написания if, while, else. Весь компилятор находится в compileast. gen добавляет опкод. А compilenode это главная функция для компиляции.
Теперь мы можем побаловаться с выводом. К примеру:
#в PyShell >>> lexer = Lexer() >>> parser = Parser(lexer) >>> compiler = Compiler() >>> >>> ast = parser.parse('a = 5; b = 5') >>> print(compiler.compileast(ast)) [2, 5, 1, 'a', 2, 5, 1, 'b'] >>> Но теперь перейдём к концу.
Виртуальная машина
И конец нашей поделки, виртуальная машина!
Все мы знаем то что байткод сам себя не выполнит. Для этого нужна виртуальная машина. Вот код виртуальной машины:
class VirtualMachine: def __init__(self): pass def run(self, program): env = {} stack = [] pc = 0 while True: op = program[pc] if pc < len(program) - 1: arg = program[pc + 1] if op == FETCH: try: stack.append(env[arg]) except: stack.append(0) pc += 2 elif op == STORE: env[arg] = stack.pop() pc += 2 elif op == PUSH: stack.append(arg) pc += 2 elif op == ADD: stack[-2] += stack[-1] stack.pop() pc += 1 elif op == SUB: stack[-2] -= stack[-1] stack.pop() pc += 1 elif op == MUL: stack[-2] *= stack[-1] stack.pop() pc += 1 elif op == DIV: stack[-2] /= stack[-1] stack.pop() pc += 1 elif op == LT: if stack[-2] <= stack[-1]: stack[-2] = 1 else: stack[-2] = 0 stack.pop() pc += 1 elif op == GT: if stack[-2] >= stack[-1]: stack[-2] = 1 else: stack[-2] = 0 stack.pop() pc += 1 elif op == EQ: if stack[-2] == stack[-1]: stack[-2] = 1 else: stack[-2] = 0 stack.pop() pc += 1 elif op == NOTEQ: if stack[-2] != stack[-1]: stack[-2] = 1 else: stack[-2] = 0 stack.pop() pc += 1 elif op == POP: stack.append(arg) 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 == PASS: pc += 1 elif op == HALT: break print('Execution finished') for i in env.keys(): print(i+': '+str(env[i])) Описываю этот код:
Переменная stack это сам стек ведь наша машина стековая.
Переменная env это словарь переменных.
Получаем аргумент если он есть. И выполняем опкод. В конце порадуем пользователя что всё работает и радостно выводим ключ и значение в env.
Теперь когда мы баловались с выводом в компиляторе то мы можем выполнить этот код:
>>> bytecode = compiler.compileast(ast) >>> vm = VirtualMachine() >>> vm.run(bytecode) Execution finished a: 5 b: 5 >>> Теперь давайте в бонус сделаем командную строку.
import sys def run_compiler(prog): lexer = Lexer() parser = Parser(lexer) ast = parser.parse(prog) compiler = Compiler() bytecode = compiler.compileast(ast) vm = VirtualMachine() vm.run(bytecode) def cli(): while True: com = input('>>> ') try: run_compiler(com) except Exception as err: print('Error: ', end="") sys.stderr.write(str(err)+'\n') if __name__ == '__main__': cli()Тут объяснений не надо ведь тут и так понятно.
Весь код
import re import sys FETCH, STORE, PUSH, POP, ADD, SUB, MUL, DIV, LT, GT, EQ, NOTEQ, JZ, JNZ, JMP, PASS, HALT = range(17) class Lexer: def __init__(self): pass def lexterm(self, term): if re.match(r'[a-zA-Z][a-zA-Z0-9_]*', term): return ('id', term) elif re.match(r'[0-9]+', term): return ('num', term) def lex_expr(self, exp): res = exp.split(' ') if len(res) == 1: return (self.lexterm(res[0]), res[0]) first = self.lexterm(res[0]) second = self.lexterm(res[2]) return [first, res[1], second] def next_token(self, string): self.sum = None d = string.split(' ') if d[0] == 'while': d = string.split(')') try: cond = d[0][d[0].index('while') + 6:] + ')' except: raise SyntaxError('Invalid paren expression') try: stmt = d[1][1:] except: raise SyntaxError('Invalid "while" statement') self.sum = ("while", cond, stmt) return None elif d[0] == 'if': d = string.split(')') try: cond = d[0][d[0].index('if') + 3:] + ')' except: raise SyntaxError('Invalid paren expression') try: stmt = d[1][1:] except: raise SyntaxError('Invalid "if" statement') self.sum = ("if", cond, stmt) return None elif d[0] == 'pass': self.sum = ("pass", None) return None elif d[0] == 'else': stmt = string.replace('else ', '') if stmt == '': raise SyntaxError('Invalid "else" statement') self.sum = ("else", stmt) return None elif d[0] == 'exit': self.sum = ('exit', None) return None try: if d[1] == '=': name = d[0] valu = d[2:] pos = 0 value = '' while pos < len(valu): if pos + 1 == len(valu): value += valu[pos] else: value += valu[pos] + ' ' pos += 1 self.sum = ("assign", name, value) return None except: pass raise SyntaxError('Invalid syntax: '+str(string)) class Node: def __init__(self, name, op1, op2=None, op3=None): self.name = name self.op1 = op1 self.op2 = op2 self.op3 = op3 def __repr__(self): return f"Node(\n name='{self.name}',\n op1={self.op1},\n op2={self.op2},\n op3={self.op3}\n)" class Parser: def __init__(self, lexer): self.pos = 0 self.lexer = lexer def term(self, value): if value[0] == 'id': return 'ID' elif value[0] == 'num': return 'INT' def parse_expr(self, token): try: left = token[0] right = token[2] op = token[1] result = Node(op, Node(self.term(left), left[1]), Node(self.term(right), right[1])) return result except: try: return Node(self.term(left), left[1]) except: raise SyntaxError('Invalid expression') def paren_expr(self, expr): d = expr[expr.index('(') + 1:expr.index(')')] return self.parse_expr(self.lexer.lex_expr(d)) def parse(self, program): try: self.prog = program.split('; ') except: self.prog = program astpos = 0 ast = [] while self.pos < len(self.prog): if self.prog[self.pos] == '': self.pos += 1 continue d = self.prog[len(self.prog) - 1] r = len(d) - 1 if d[r] == ';': raise SyntaxError('The ";" sign is not needed at the end') self.lexer.next_token(self.prog[self.pos]) token = self.lexer.sum if token[0] == 'assign': ast.append(Node('ASSIGN', token[1], op2=self.parse_expr(self.lexer.lex_expr(token[2])))) elif token[0] == 'if': d = Lexer() r = Parser(d) ast.append(Node('IF', self.paren_expr(token[1]), op2=r.parse(token[2])[0])) elif token[0] == 'while': d = Lexer() r = Parser(d) ast.append(Node('WHILE', self.paren_expr(token[1]), op2=r.parse(token[2])[0])) elif token[0] == 'else': d = Lexer() r = Parser(d) if ast[astpos - 1].name == 'IF': ast[astpos - 1].name = 'ELSE' ast[astpos - 1].op3 = r.parse(token[1])[0] else: raise SyntaxError('Invalid "else" statement') elif token[0] == 'exit': ast.append(Node('EXIT', None)) elif token[0] == 'pass': ast.append(Node('PASS', None)) self.pos += 1 astpos += 1 self.pos = 0 return ast class Compiler: def __init__(self): self.program = [] self.pc = 0 def gen(self, command): self.program.append(command) self.pc = self.pc + 1 def compilenode(self, node): name = node.name if name == 'INT': self.gen(PUSH) self.gen(int(node.op1)) elif name == 'ID': self.gen(FETCH) self.gen(node.op1) elif name == '+': self.compilenode(node.op1) self.compilenode(node.op2) self.gen(ADD) elif name == '-': self.compilenode(node.op1) self.compilenode(node.op2) self.gen(SUB) elif name == '/': self.compilenode(node.op1) self.compilenode(node.op2) self.gen(DIV) elif name == '*': self.compilenode(node.op1) self.compilenode(node.op2) self.gen(MUL) elif name == '<': self.compilenode(node.op1) self.compilenode(node.op2) self.gen(LT) elif name == '>': self.compilenode(node.op1) self.compilenode(node.op2) self.gen(GT) elif name == '!=': self.compilenode(node.op1) self.compilenode(node.op2) self.gen(NOTEQ) elif name == '==': self.compilenode(node.op1) self.compilenode(node.op2) self.gen(EQ) elif name == 'ASSIGN': self.compilenode(node.op2) self.gen(STORE) self.gen(node.op1) elif name == 'IF': self.compilenode(node.op1) self.gen(JZ) addr = self.pc self.gen(0) self.compilenode(node.op2) self.program[addr] = self.pc elif name == 'ELSE': self.compilenode(node.op1) self.gen(JZ) addr1 = self.pc self.gen(0) self.compilenode(node.op2) self.gen(JMP) addr2 = self.pc self.gen(0) self.program[addr1] = self.pc self.compilenode(node.op3) self.program[addr2] = self.pc elif name == 'WHILE': if node.op1.op2: try: r = node.op1.op2 d = str(int(r.op1) - 1) r.op1 = d except: r = node.op1.op1 d = str(int(r.op1) - 1) r.op1 = d addr1 = self.pc self.compilenode(node.op1) self.gen(JZ) addr2 = self.pc self.gen(1) self.compilenode(node.op2) self.gen(JMP) self.gen(addr1) self.program[addr2] = self.pc elif name == 'EXIT': self.gen(HALT) elif name == 'PASS': self.gen(PASS) def compileast(self, ast): for i in ast: self.compilenode(i) self.gen(HALT) return self.program class VirtualMachine: def run(self, program): env = {} stack = [] pc = 0 while True: op = program[pc] if pc < len(program) - 1: arg = program[pc + 1] if op == FETCH: try: stack.append(env[arg]) except: stack.append(0) pc += 2 elif op == STORE: env[arg] = stack.pop() pc += 2 elif op == PUSH: stack.append(arg) pc += 2 elif op == ADD: stack[-2] += stack[-1] stack.pop() pc += 1 elif op == SUB: stack[-2] -= stack[-1] stack.pop() pc += 1 elif op == MUL: stack[-2] *= stack[-1] stack.pop() pc += 1 elif op == DIV: stack[-2] /= stack[-1] stack.pop() pc += 1 elif op == LT: if stack[-2] <= stack[-1]: stack[-2] = 1 else: stack[-2] = 0 stack.pop() pc += 1 elif op == GT: if stack[-2] >= stack[-1]: stack[-2] = 1 else: stack[-2] = 0 stack.pop() pc += 1 elif op == EQ: if stack[-2] == stack[-1]: stack[-2] = 1 else: stack[-2] = 0 stack.pop() pc += 1 elif op == NOTEQ: if stack[-2] != stack[-1]: stack[-2] = 1 else: stack[-2] = 0 stack.pop() pc += 1 elif op == POP: stack.append(arg) 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 == PASS: pc += 1 elif op == HALT: break print('Execution finished') for i in env.keys(): print(i+': '+str(env[i])) def run_compiler(prog): lexer = Lexer() parser = Parser(lexer) ast = parser.parse(prog) compiler = Compiler() bytecode = compiler.compileast(ast) vm = VirtualMachine() vm.run(bytecode) def cli(): while True: com = input('>>> ') try: run_compiler(com) except Exception as err: print('Error: ', end="") sys.stderr.write(str(err)+'\n') if __name__ == '__main__': cli()Всего 379 строчек кода. Но работает и правильно.
И вот вам примеры:
a = 5; if (a < 10) a = 10; else a = 5 a = 5; b = 5; c = a + b x = 0; while (x < 10) x = x + 1Должно работать.
Заключение
Мы с вами написали примитивный компилятор и он будет вам не нужен потому что вы уже получили опыт написания компиляторов с собственной виртуальной машиной. И, только виртуальная машина может вам понадобится.
ссылка на оригинал статьи https://habr.com/ru/articles/901324/
Добавить комментарий