Как я за месяц написал интерпретируемый язык программирования на Python
Привет, Хабр! В этой статье я хотел бы поделиться опытом создания своего языка программирования.
Предыстория
Мне 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(ASSING, "=")
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 (делается это просто, расписал инструкцию в репозитории).
Выводы
В этой статье я постарался рассказать, как работают интерпретируемые языки программирования. Язык я завершил после добавления функций и многопоточных циклов. документацию, примеры и код к языку вы можете найти в моём репозитории. На написание данной статьи меня подтолкнуло малое количество информации на подобную тему. Буду рад комментариям и Вашим замечаниям. До скорых встреч!
