Привет, Хабр! В этой статье я хотел бы поделиться опытом создания своего языка программирования.
Предыстория
Мне 14. Обучаясь на втором году Яндекс Лицея, нужно было написать несколько проектов. Первым из них стал проект на PyQT5. Я долго думал над идеей и вспомнил, что летом я хотел создать свой язык, но у меня этого не получилось (Тогда я не понимал как работает парсер и абстрактное синтаксическое дерево, поэтому забросил). И вот, мне пришла идея — сделать свой язык программирования и написать для него IDLE (т.к. тема проекта все-таки QT). Ещё полгода назад я изучал асинхронность и многопоточность, поэтому именно одну из этих идей я хотел воплотить в своём языке. В данной статье я хотел рассказать устройство интерпретируемых языков и как их создать.
Чем отличается интерпретируемый язык от компилируемого
Вся разница в исполнении кода. Интерпретируемые языки работают по следующей схеме:
Lexer.py ---> Parser.py ---> AbstractSyntaxTree.py ---> resultНиже я более подробно рассказываю про работу всех компонентов кроме AST, потому что на момент написания языка я не понимал как это работает.
Компилируемые языки программирования исполняют код не построчно (как интерпретируемые). Процесс компиляции включает препроцессинг исходного кода, где удаляются комментарии и вставляются содержимое файлов, компиляцию кода в ассемблерный или промежуточный код, а затем ассемблирование этого кода в машинный код, который линкуется в исполняемый файл с разрешением внешних ссылок. Проще говоря, написанный код переводится либо на ассемблер, либо на другие компилируемые языки, которые его исполняют.
Устройство языка
Я решил, что мой язык будет состоять только из Лексера и Парсера (окончательное понимание синтаксического дерева пришло ко мне под конец). Я сразу отказался использовать такие библиотеки, как PLY и RPLY, поэтому мой проект написан на чистом Python. Про компоненты языка я буду объяснять неформально, то-есть так, как понял это я.
Лексер
В каждом языке программирования есть Лексер и Парсер. Лексер — класс, который принимает строку кода и разбивает её на токены. Токены нужны для проверки грамматики на этапе парсинга.
Токены, которые представлены на картинке, являются объектами класса Token, Данный класс принимает в __init__: тип токена и его значение.
NUMBER = "NUMBER" STRING = "STRING" class Token: def __init__(self, type, value): self.type = type self.value = value def __str__(self): return f'Token({self.type}, {self.value})' def __repr__(self): return self.__str__()Помимо класса Token, есть вышеупомянутый класс Lexer, который посимвольно проходит строку циклом и возвращает объекты класса Token:
class Lexer: def __init__(self, text): self.text = text self.pos = 0 self.current_char = self.text[self.pos] def advance(self): self.pos += 1 if self.pos < len(self.text): self.current_char = self.text[self.pos] else: self.current_char = None def return_pos(self, pos): self.pos = pos if self.pos < len(self.text): self.current_char = self.text[self.pos] else: self.current_char = None def skip_whitespace(self): while self.current_char is not None and self.current_char.isspace(): self.advance() def get_next_token(self): while self.current_char is not None: if self.current_char.isspace(): self.skip_whitespace() continue if self.current_char.isdigit() or self.current_char == "-": token_value = "" while self.current_char is not None and (self.current_char.isdigit() or self.current_char == "." or self.current_char == "-"): token_value += self.current_char self.advance() try: return Token(NUMBER, int(token_value)) except: try: return Token(NUMBER, float(token_value)) except: return Token(MINUS, "-") if self.current_char == '"' or self.current_char == "'": self.advance() string_value = "" while self.current_char is not None and self.current_char != '"' and self.current_char != "'": string_value += self.current_char self.advance() if self.current_char == '"' or self.current_char == "'": self.advance() return Token(STRING, '"' + string_value + '"') else: print(f"Некорректный символ: {self.current_char}") sys.exit() if self.current_char == '=': self.advance() return Token(ASSIGN, '=') if self.current_char == '+': self.advance() return Token(PLUS, '+') if self.current_char == '-': self.advance() return Token(MINUS, '-') if self.current_char == '*': self.advance() return Token(MULTIPLY, '*') if self.current_char == '/': self.advance() return Token(DIVIDE, '/') if self.current_char == '%': self.advance() return Token(PR, '%') if self.current_char == '(': self.advance() return Token(LPAREN, '(') if self.current_char == ')': self.advance() return Token(RPAREN, ')') if self.current_char == '^': self.advance() return Token(DEG, '^') if self.current_char == ',': self.advance() return Token(COMMA, ',') if self.current_char.isalpha(): token_value = "" while self.current_char is not None and (self.current_char.isalpha() or self.current_char.isdigit() or self.current_char == "_"): token_value += self.current_char self.advance() if token_value == "int": return Token(INT, "int") elif token_value == "float": return Token(FLOAT, "float") elif token_value == "str": return Token(STR, "str") elif token_value == "None": return Token(NONE, "None") elif token_value == "print": return Token(PRINT, "print") elif token_value == "input": return Token(INPUT, "input") elif token_value == "True" or token_value == "False": return Token(BOOL, token_value) else: return Token(VAR, token_value) print(f"Неверный синтаксис: {self.text}") sys.exit() return Token(EOF, None)Это лишь половина класса Лексера. Он проходится по каждому символу и проверяет его существование. Если Лексер нашёл символ, то возвращает объект класса Token с переданными типом символа и самим символом. Помимо этого существуют ещё три класса, которые хранят значения локальных переменных и код функций:
Парсер
Парсер, по моему мнению, является сложнейшей частью языка. В моём случае он выполняет задачу проверки синтаксиса и исполнения кода. Вот частичный код получившегося класса:
import math from lexer import * # Определение парсера для вычисления выражений class Parser(): def __init__(self, lexer, symbol_table): """ Конструктор класса Parser. Параметры: - lexer: экземпляр класса Lexer для токенизации входного текста. - symbol_table: экземпляр класса SymbolTable для отслеживания переменных. symbol_table - объект класса SymbolTable, используется для хранения и управления переменными. """ self.lexer = lexer self.current_token = self.lexer.get_next_token() self.symbol_table = symbol_table def eat(self, token_type): """ Функция проверяет текущий токен и токен, с которого мы хотим перейти на другой токен. То есть у нас не получиться будучи на Token(VAR, "x") перейти на следущий токен с того, которого мы передаём в функцию: Текущий токен: VAR, мы передали в функцию токен PRINT - получаем ошибку, потому что мы находимся на токене VAR, а хотим перейти на следующий токен с токена PRINT. """ if self.current_token.type == token_type: self.current_token = self.lexer.get_next_token() else: raise Exception(f"Error eating {self.current_token.type} token!") def factor(self): """ Функция отвечает за использование встроенных функций языка или других токенов которые возвращают значения: ... = input() ... = int(x) ... = True """ token = self.current_token if token.type == NUMBER: self.eat(NUMBER) return token.value elif token.type == STRING: string_value = token.value self.eat(STRING) return string_value elif token.type == NONE: self.eat(NONE) return None elif token.type == BOOL: result = token.value if result == "True": result = True else: result = False self.eat(BOOL) return result elif token.type == VAR: var_name = token.value self.eat(VAR) return self.symbol_table.lookup(var_name) elif token.type == INT: self.eat(INT) self.eat(LPAREN) result = int(self.expr()) self.eat(RPAREN) return result elif token.type == FLOAT: self.eat(FLOAT) self.eat(LPAREN) result = float(self.expr()) self.eat(RPAREN) return result elif token.type == STR: self.eat(STR) self.eat(LPAREN) result = str(self.expr()) self.eat(RPAREN) return result elif token.type == LPAREN: self.eat(LPAREN) result = self.expr() self.eat(RPAREN) return result def term(self): """ Обработка терма (произведения или частного). Возвращает: - Результат вычисления терма. """ result = self.factor() while self.current_token.type in (MULTIPLY, DIVIDE, PR, DEG): token = self.current_token if token.type == MULTIPLY: self.eat(MULTIPLY) result *= self.factor() elif token.type == DIVIDE: self.eat(DIVIDE) result /= self.factor() elif token.type == PR: self.eat(PR) result %= self.factor() elif token.type == DEG: self.eat(DEG) num = self.factor() result = math.pow(result, num) return result def expr(self): """ Обработка выражения (суммы или разности). Возвращает: - Результат вычисления выражения. """ result = self.term() while self.current_token.type in (PLUS, MINUS): token = self.current_token if token.type == PLUS: self.eat(PLUS) result += self.term() elif token.type == MINUS: self.eat(MINUS) result -= self.term() return result def statement(self): """ Функция отвечает за встроенные функции и конструкции, которые не возвращают значения: print() var = ... if ... """ if self.current_token.type == VAR: var_name = self.current_token.value self.eat(VAR) if self.current_token.type == ASSIGN: self.eat(ASSIGN) value = self.expr() self.symbol_table.define(var_name, value) else: sys.exit() elif self.current_token.type == PRINT: self.eat(PRINT) self.eat(LPAREN) values = [] while self.current_token.type != EOF and self.current_token.type != RPAREN: values.append(self.expr()) if self.current_token.type == COMMA: self.eat(COMMA) self.eat(RPAREN) print(*values) else: self.current_token = self.lexer.get_next_token() def parse(self): """ Парсинг входного текста и выполнение выражений. Эта функция запускает парсинг входного текста и последовательно выполняет выражения, включая присваивание переменных и вывод значений. """ while self.current_token.type != EOF: self.statement()Теперь рассмотрим на примере, как работает класс. На вход подаётся строка:
x = 5Она проходит через лексер:
Token(VAR, "x") Token(ASSIGN, "=") Token(NUMBER, 5) Token(EOF, None)После токены используются в парсере:
Token(VAR, "x") ---> self.parse() ---> self.statement() ---> self.expr() ---> self.term() ---> self.factor() | | x = <--- self.expr() <--- self.term() <--- 5 | self.symbol_table.define("x", 5)На вход поступает первый токен — Token(VAR, «x»). Класс запускается при использовании функции self.parse(). Функция self.parse() вызывает функцию self.statement(), которая вызывает функцию self.expr() и ждет от неё возвращаемое значение. Функция self.expr() вызывает self.term() и тоже ждёт возвращаемое значение и т.д.
Возникшие проблемы
Основными проблемами стали GIL и низкая скорость Python. Язык работал слишком медленно (Был вариант переписать на C++, но приближалась сдача проекта), а параллельные циклы, реализованные с помощью asyncio, не работали вовсе (т.к. в моём случае корутины не работали из-за блокируемых операций). Asyncio пришлось заменить библиотекой multiprocessing, которая запускает несколько Python интерпретаторов. Проблему с низкой скоростью я решил с помощью Cython. Он помог разогнать язык в 90 раз! Поэтому, если вы захотите написать что-нибудь на моём языке, Вам придётся установить Cython и выполнить компиляцию файлов .pyx (делается это просто, расписал инструкцию в репозитории).
Выводы
В этой статье я постарался рассказать, как работают интерпретируемые языки программирования. Язык я завершил после добавления функций и многопоточных циклов. документацию, примеры и код к языку вы можете найти в моём репозитории. На написание данной статьи меня подтолкнуло малое количество информации на подобную тему. Буду рад комментариям и Вашим замечаниям. До скорых встреч!
ссылка на оригинал статьи https://habr.com/ru/articles/776438/
Добавить комментарий