Привет, Хабр! В этой статье я хотел бы поделиться опытом создания своего языка программирования.

Предыстория

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

Выводы

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