Как написать свой язык: основы парсеров и интерпретаторов?

Зачем создавать свой язык программирования?

Разработка собственного языка программирования — это не просто интересный вызов, но и возможность глубже понять, как работают существующие языки. Создание языка помогает улучшить навыки в компиляторостроении, лексическом анализе и 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

Заключение

Мы разобрали базовые принципы создания собственного языка программирования, начиная с лексического анализа, парсинга и заканчивая интерпретацией кода. Это лишь основа, и дальше можно расширять язык, добавляя поддержку переменных, функций и логики.

Если вас заинтересовала тема, попробуйте развить этот язык: добавить поддержку условных операторов, циклов или даже создать полноценный компилятор!