Як написати свою мову: основи парсерів та інтерпретаторів?

Навіщо створювати свою мову програмування?

Розробка власної мови програмування — це не просто цікавий виклик, а й можливість глибше зрозуміти, як працюють існуючі мови. Створення мови допомагає покращити навички в компіляторобудуванні, лексичному аналізі та AST (абстрактних синтаксичних деревах).

Курс з вивчення Python

Можете пройти наш безкоштовний курс з вивчення Python

Основні етапи створення мови

Перш ніж почати, розгляньмо ключові компоненти, які необхідні для розробки мови програмування:

• Лексичний аналізатор (Tokenizer, Lexer) — розбиває вхідний код на токени.
• Парсер (Parser) — будує синтаксичне дерево (AST).
• Інтерпретатор (Interpreter) або компілятор — виконує або компілює код.

Крок 1: Лексичний аналіз

Лексичний аналізатор (або токенізатор) приймає вихідний код і розбиває його на окремі елементи — токени. Розгляньмо простий лексер на Python:

import re # Імпортуємо модуль регулярних виразів

# Визначаємо специфікацію токенів: кожен токен має назву і відповідний йому шаблон
TOKEN_SPEC = [
	("NUMBER", r"\d+"), # Числа (одна або більше цифр)
	("PLUS", r"\+"), # Символ "+"
	("MINUS", r"-"), # Символ "-"
	("MULT", r"\*"), # Символ "*"
	("DIV", r"/"), # Символ "/"
	("LPAREN", r"\("), # Відкриваюча дужка "("
	("RPAREN", r"\)"), # Закриваюча дужка ")"
	("WHITESPACE", r"\s+"), # Пробіли та табуляції
]

def tokenize(code):
	"""Функція розбиває вхідний рядок коду на список токенів"""
	tokens = []
	while code:
		for name, pattern in TOKEN_SPEC:
			match = re.match(pattern, code) # Порівнюємо початок коду з шаблоном токена
			if match:
				value = match.group(0)
				if name != "WHITESPACE": # Пропускаємо пробіли
					tokens.append((name, value))
				code = code[len(value):] # Видаляємо розпізнану частину коду
				break
		else:
			raise SyntaxError(f"Невідомий символ: {code[0]}") # Якщо жоден шаблон не підійшов
	return tokens

# Перевіряємо лексичний аналізатор
print(tokenize("3 + 5 * (10 - 2)")) # Виведе список токенів

Крок 2: Створення парсера

Парсер приймає список токенів і будує з них абстрактне синтаксичне дерево (AST). Це дерево потім використовується інтерпретатором або компілятором для виконання коду.

Приклад простого парсера для арифметичних виразів:

class Node:
	"""Клас, що представляє вузол абстрактного синтаксичного дерева (AST)"""
	def __init__(self, type, value=None, left=None, right=None):
		self.type = type
		self.value = value
		self.left = left
		self.right = right

class Parser:
	"""Клас парсера для побудови AST"""
	def __init__(self, tokens):
		self.tokens = tokens # Список токенів
		self.pos = 0 # Поточна позиція у списку токенів

	def eat(self, token_type):
		"""Перевіряє, чи поточний токен має потрібний тип, і переходить до наступного"""
		if self.pos < len(self.tokens) and self.tokens[self.pos][0] == token_type:
			self.pos += 1
		else:
			raise SyntaxError(f"Очікувалося {token_type}, але отримано {self.tokens[self.pos][0]}")

	def factor(self):
		"""Обробляє числа або вирази в дужках"""
		token = self.tokens[self.pos]
		if token[0] == "NUMBER":
			self.pos += 1
			return Node("NUMBER", token[1])
		elif token[0] == "LPAREN":
			self.eat("LPAREN")
			node = self.expr()
			self.eat("RPAREN")
			return node

	def term(self):
		"""Обробляє множення та ділення"""
		node = self.factor()
		while self.pos < len(self.tokens) and self.tokens[self.pos][0] in ("MULT", "DIV"):
			token = self.tokens[self.pos]
			self.pos += 1
			node = Node(token[0], left=node, right=self.factor())
		return node

	def expr(self):
		"""Обробляє додавання та віднімання"""
		node = self.term()
		while self.pos < len(self.tokens) and self.tokens[self.pos][0] in ("PLUS", "MINUS"):
			token = self.tokens[self.pos]
			self.pos += 1
			node = Node(token[0], left=node, right=self.term())
		return node

	def parse(self):
		"""Запускає процес розбору і повертає AST"""
		return self.expr()

Крок 3: Інтерпретація коду

Інтерпретатор виконує AST, обчислюючи значення виразів. Приклад простого інтерпретатора:

def evaluate(node):
	"""Функція для обчислення значення AST"""
	if node.type == "NUMBER":
		return int(node.value) # Перетворюємо число в int
	elif node.type == "PLUS":
		return evaluate(node.left) + evaluate(node.right) # Додавання
	elif node.type == "MINUS":
		return evaluate(node.left) - evaluate(node.right) # Віднімання
	elif node.type == "MULT":
		return evaluate(node.left) * evaluate(node.right) # Множення
	elif node.type == "DIV":
		return evaluate(node.left) / evaluate(node.right) # Ділення

# Приклад використання
tokens = tokenize("3 + 5 * (10 - 2)") # Розбиваємо вхідний рядок на токени
parser = Parser(tokens) # Передаємо токени парсеру
ast = parser.parse() # Створюємо AST
print(evaluate(ast)) # Виведе 43

Курс з вивчення Python

Можете пройти наш безкоштовний курс з вивчення Python

Висновок

Ми розглянули базові принципи створення власної мови програмування, починаючи з лексичного аналізу, парсингу і закінчуючи інтерпретацією коду. Це лише основа, і далі можна розширювати мову, додаючи підтримку змінних, функцій і логіки.

Якщо вас зацікавила ця тема, спробуйте розвинути цю мову: додати підтримку умовних операторів, циклів або навіть створити повноцінний компілятор!