Всем привет, сегодня мы с вами напишем компилятор на 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

Должно работать.

Заключение

Мы с вами написали примитивный компилятор и он будет вам не нужен потому что вы уже получили опыт написания компиляторов с собственной виртуальной машиной. И, только виртуальная машина может вам понадобится.

UPD: Это первая статья которую я зачем то отправил в черновик (она хорошая).

Пишем самый примитивный компилятор на Python