Сегодня я расскажу, как из-за случайной встречи с ANTLR я создал RCParsing, библиотеку на C# для парсинга практически любого вида синтаксиса, поддерживающую парсинг отступов из коробки. Мы разберемся, как работают разные алгоритмы парсинга и чем отличается тот, что используется у меня. Также я закину пример кода для парсинга упрощенного YAML с использованием моей библиотеки.

Немного предыстории

Однажды я разрабатывал свой сайт для мультиплеерных текстовых квестов для игры с друзьями, а мастером был DeepSeek. Сайт делал на Blazor, а в бекенде было очень много интерполяций строк для промптов. Меня эти интерполяции взбесили так, что в итоге родилась идея шаблонного языка специально для LLM, похожего на Razor:

@messages template {
    @system message {
        You are text quest master, please respond based on players turns!
    }
    @foreach turn in game.turns {
        @message {
            @role turn.is_master ? 'assistant' : 'user'
            @turn.contents
        }
    }
}

У вас мог возникнуть вопрос: "Эй, у тебя же в синтаксисе скобочки, зачем тебе вообще отступы сдались?", а я отвечу: "Для еще одного языка и просто для личного интереса", но об этом попозже.

Различия в существующих подходах к парсингу

Из всех инструментов для парсинга я знал лишь ANTLR, поэтому в первую очередь решил попробовать его. Но после осознания принципа его работы я твёрдо понял: ANTLR не сможет обработать такой вид синтаксиса.

Так почему же? А потому, что он использует лексер, то есть сначала разбивает текст на токены (числа, идентификаторы, строки, ключевые слова и так далее), а затем сам парсер работает непосредственно с ними. Это самый быстрый способ парсинга (у него практически всегда стабильная линейная скорость, O(n)), хоть и достаточно неудобный и негибкий. Вот наглядный пример, как работает такой парсер:

В чем же заключается неудобство и слабость такого подхода? Суть в том, что настроить лексер — одно из сложнейших испытаний при создании такого парсера, так как там нужно расставлять приоритеты токенам, и, не дай бог, настраивать им режимы! Хотя в простых языках расставить токены по местам не так уж и сложно, а режимы вообще не нужны, например:

IF : 'if' ; // Ключевые слова первее, иначе они будут расцениваться как идентификатор!
ID : [_a-zA-Z][_a-zA-Z0-9]* ; // Более общие правила ставим позже

А что если в языке более 100 различных типов токенов, существуют интерполяции строк и прочая ересь? Гляньте этот код лексера для C# и ужаснитесь (кстати, интерполяция строк там реализована не полностью). А ещё советую представить полноценный лексер для HTML, где внутри есть CSS и JavaScript, внутри которого также может быть HTML. Даже страшно подумать про Razor, где есть и HTML, и C# вперемешку...

Но как настраивать токены, если текст и код смешаны, как в моем языке шаблонов? Краткий ответ: либо менять синтаксис языка, либо огромным кодом с логикой лексера, либо никак. Приведу пример, вот кусок кода из шаблона:

@role turn.is_master ? 'assistant' : 'user' Hello world!

В данном случае нам нужно ясно задать лексеру, где он должен захватывать код (идентификаторы, строки и всякие символы вроде :), а где текст (исключая символы @, {, }). И это попросту невозможно, так как явные токены‑терминалы для режимов отстутствуют, к примеру точка с запятой:

@role turn.is_master ? 'assistant' : 'user'; Hello world!

Проблема заключается в том, что лексер — это достаточно быстрая, но примитивная штука, и она вообще не в курсе, что у тебя творится в тексте. У нас закончилось выражение? Не знаю. У нас начался текст? Когда? У нас есть точка с запятой, теперь ты понимаешь, где заканчивается выражение? Так сразу бы и сказали!

Так как я не хотел создавать урода из своего языка шаблонов и добавлять эти точки с запятой, я решил по‑быстрому накидать свой, безлексерный парсер, который работает с текстом напрямую. Ну а что? Архитектуру я уже придумал, а уже существующие решения (вроде Sprache и Pidgin) показались мне неудобными.

Через неделю рабочий парсер был уже готов и он выполнял свою задачу на ура. Потом месяц ушел на доработку и оптимизации (первая версия была медленее, чем текущая, в 6 раз!). Кстати, вот как в общих чертах работает безлексерный парсер:

Безлексерный парсер работает с текстом напрямую, и это добавляет в разы больше возможностей для парсинга и убирает боль настройки лексера (так как его тупо нету). Однако, алгоритмическая сложность такого вида парсеров может доходить аж до экспоненциальной, но это решается мемоизацией, а в реальных системах скорость парсинга — не всегда проблема. В данном подходе те же ключевые слова легко могут интерпретироваться как идентификаторы, в отличие от лексерного подхода.

И самое главное: безлексерный парсер может захватывать ровно столько текста, сколько нужно, без лишнего. К примеру, если нужно пропарсить текст до какого-то определенного символа, он пропарсит его, даже проглотив ключевые слова. А если нужно пропарсить арифметическое выражение, затем текст, то он сделает это с легкостью, оставив неподходящий для выражения контент тексту. Допустим у нас есть такая строка:

Here is expression: @50 + a * (b.c - d[0].e()) / 90.0. And here goes plain text...

Сначала захватится текст Here is expression: , затем парсер увидит символ @ и остановится, далее он постарается захватить как можно больше символов, подходящих под выражение, то есть 50 + a * (b.c - d[0].e()) / 90.0, затем он переключится к обычному тексту и захватит . And here goes plain text.... Из-за того, что парсер работает с текстом напрямую, без отдельных токенов, он может интерпретировать текст по-разному, что позволяет ставить такие вот неочевидные границы для правил, и без использования точек с запятой.

При помощи такого подхода я с легкостью реализовал парсер для своего языка шаблонов. Кстати, вот демонстрация подсветки синтаксиса:

Пусть мне этого и хватало для языка шаблонов, всё равно хотелось развить парсер дальше...

Гибридный алгоритм собственной персоной

Я как раз подумывал над созданием ещё одного языка для LLM агентов и пайплайнов (да‑да, очередной язык), в котором главную роль будут играть отступы (как в Python или YAML), плюсом мне было просто интересно создать алгоритм, который может элегантно их обрабатывать.

А в чем же проблема отступов? Дело в том, что обычно парсеры не поддерживают отступы из коробки (из библиотек для .NET я нашел только лексерный CSLY), а в случае ANTLR нужно писать кастомный код для лексера с отслеживанием состояния (примерно 80 строк, гляньте этот код), который будет создавать токены, необходимые для отступов, INDENT и DEDENT. А безлексерные парсеры в принципе не способны парсить такое без диких костылей, так как изменения отступов могут быть легко упущены. К примеру, возьмем этот кусок кода на Python:

def func(n):
  print(n)
print("Hello!")

Допустим, парсер успешно считал def func(n):, далее он попытается жадно считать как можно больше инструкций, по итогу захватив print(n) и print("Hello!"). Второй print попал в список из-за того, что парсер жадный, то есть пытается захватить как можно больше, к тому же, ему ничто не мешает захватывать лишние правила. Я задумался, как же решить эту проблему без костылей...

И тут ко мне �� голову пришла идея: "А что если поставить ограничители, которые будут мешать парсеру захватывать лишние инструкции?". Так и родилась концепция барьерных токенов. Суть этой концепции заключается в том, что парсер определяет позицию следующего барьерного токена, и ограничивает видимую область текста вплоть до этой позиции, а если же парсер натыкается на барьерный токен вплотную, то он должен ожидать данный токен, иначе он просто упадет. Вот как это работает наглядно:

Изначально дана такая упрощенная грамматика (для наглядности):

function_def : 'def' ID '(' args ')' ':' block ;
block : INDENT statement+ DEDENT ;
program : statement+ ;

Сначала парсер успешно захватывает объявление функции, затем пытается пропарсить её тело. Он успешно парсит токен INDENT, который означает увеличение отступа, затем пытается захватить как можно больше инструкций, но после захвата print(n) ему мешает барьерный токен DEDENT, поэтому он возвращает лишь одну захваченную инструкцию. Потом парсер успешно закрывает блок токеном DEDENT и заканчивает парсить функцию, затем проходится по остальным инструкциям в программе.

И получается такая схема работы гибридного парсера:

В гибридном подходе токенизириуется лишь значимая часть текста. Помимо отступов можно, например, токенизировать ключевые слова, чтобы они не распознавались как идентификаторы или что-то другое.

Итоговое сравнение алгоритмов

• Лексерный: Самый быстрый алгоритм, но требует тщательной настройки лексера. Не такой гибкий, как безлексерный. Различают LL(1), LL(*), LR, SLR, LALR и другие. Среди библиотек для C# используется в ANTLR, Irony, Superpower, CSLY.

• Безлексерный: Более мощный и гибкий подход, чем предыдущий. Позволяет реализовать на порядок больше грамматик. Производительность хуже, но не сильно, всё ещё в адекватном пределе. Различают PEG, Packrat и комбинаторы. Среди библиотек для C# используется в Sprache, Pidgin, Parakeet, Parlot и в моей.

• Гибридный: Ещё более мощный подход, позволяющий парсить языки, которые нельзя реализовать в предыдущих. Модификация безлексерного алгоритма с частичной токенизацией. Скорость может быть чуть меньше из-за проверок на барьерные токены.

Реализация упрощенного YAML с использованием RCParsing

И вот подъехала практическая реализация парсера с использованием барьерных токенов:

var builder = new ParserBuilder();

// Пропускаем пробелы
builder.Settings.SkipWhitespaces();

// Добавляем барьерный токенизатор
builder.BarrierTokenizers.AddIndent(indentSize: 2, "INDENT", "DEDENT", "NEWLINE");

// Токены для значений
builder.CreateToken("boolean")
    // Создаем токен и при парсинге строим булевое значение на основе захваченного текста
	.LiteralChoice(["true", "false"], factory: v => v.Text == "true");

builder.CreateToken("number")
    // Этот числовой токен автоматически выдает значение типа 'double'
	.Number<double>();

builder.CreateToken("string")
	.Literal("\"")                       // 0
	.EscapedTextPrefix('\\', '\\', '\"') // 1
	.Literal("\"")                       // 2
    // Пропускаем экранированную строку в значение токена
    // Эта функция свойственна только для токенов
	.Pass(index: 1);

builder.CreateToken("identifier")
	.UnicodeIdentifier();

// Правила
builder.CreateRule("value")
	.Choice(
		b => b.Token("boolean"),
		b => b.Token("number"),
		b => b.Token("string")
	);

builder.CreateRule("object_pair")
	.Token("identifier")
	.Literal(":")
	.Rule("value")
	.Token("NEWLINE") // Ссылка на барьерный токен
    // Задаем функцию трансформации, которая будет вызываться после успешного парсинга
	.Transform(v =>
	{
		var key = v[0].Text; // Берем текст из токена 'identifier'
		var value = v[2].GetValue(); // Берем значение из правила 'value'
		return new KeyValuePair<string, object>(key, value);
	});

builder.CreateRule("object_child")
	.Choice(
		b => b.Rule("object_pair"),
		b => b.Rule("object")
	);

builder.CreateRule("object")
	.Token("identifier")
	.Literal(":")
	.Token("NEWLINE")
	.Token("INDENT")
	.OneOrMore(b => b.Rule("object_child"))
        // Задаем функцию трансформации для элемента 'OneOrMore(...)'
		.TransformLast(v => v.SelectValues<KeyValuePair<string, object>>().ToDictionary())
	.Token("DEDENT")
	.Transform(v =>
	{
		var key = v[0].Text; // Текст идентификатора
		var value = v[4].GetValue(); // Значение из дочерних элементов
		return new KeyValuePair<string, object>(key, value);
	});

// Основное правило
builder.CreateMainRule()
	.ZeroOrMore(b => b.Rule("object_child"))
		.TransformLast(v => v.SelectValues<KeyValuePair<string, object>>().ToDictionary())
	.EOF()
	.TransformSelect(index: 0);

// Получаем парсер
var parser = builder.Build();

string input =
"""
a_nested_map:
  key: true
  another_key: 0.9
  another_nested_map:
    hello: "Hello world!"
  key_after: 999
""";

// И парсим значение!
var value = parser.Parse<Dictionary<string, object>>(input);

var a_nested_map = value["a_nested_map"] as Dictionary<string, object>;
var key_after = (double)a_nested_map!["key_after"];
Console.WriteLine(key_after); // 999

Некоторые пояснения по коду: вы могли заметить то, что я в коде объявляю токены, но на самом деле они просто используются как более быстрые примитивы для парсинга и отличаются от реальных токенов, которые выдает обычный лексер. Токены отличаются от правил тем, что не могут иметь дочерние элементы, поэтому мы применяем функцию Pass(index: 1), чтобы пробросить при парсинге промежуточное значение дочернего токена наверх. Промежуточные значения бывают разные для каждого типа токена (у EscapedTextPrefix это строка с применённым экранированием). На самом деле таких "магических" нюансов в моей библиотеке не так уж и много, если научиться, то можно легко и лаконично писать собственные парсеры.

Итоги

Ну что тут можно сказать? Я был удивлен, что существующие решения для парсинга в C# не такие гибкие и удобные (на мой взгляд), поэтому сделал за месяц своё. А самое главное - оно меня очень даже устраивает!

Надеюсь, и вам понравится - вот ссылка на репозиторий. Там вы сможете найти более подробное описание фич библиотеки, бенчмарки (к сожалению пока без ANTLR, но скоро он там будет), сравнения с аналогами, примеры и документацию. Буду рад увидеть ваши комментарии и активность на репозитории!