Как я за месяц написал интерпретируемый язык программирования на 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 (делается это просто, расписал инструкцию в репозитории).

Выводы

В этой статье я постарался рассказать, как работают интерпретируемые языки программирования. Язык я завершил после добавления функций и многопоточных циклов. документацию, примеры и код к языку вы можете найти в моём репозитории. На написание данной статьи меня подтолкнуло малое количество информации на подобную тему. Буду рад комментариям и Вашим замечаниям. До скорых встреч!

© Habrahabr.ru