Как написать интерпретатор языка запросов на C#

Написать интерпретатор языка запросов на C# — задача, которая пугает до тех пор, пока не разбить её на части. В этой статье разобрана архитектура и ключевые решения PdfQL — открытой C# библиотеки, реализующей конвейерный язык запросов для извлечения структурированных данных из PDF-документов.

PdfQL — концептуальный проект, не production-библиотека. Но в реализации есть рабочий сканер, парсер, AST и исполнитель конвейера, написанные на C# под .NET 10 — что делает его полезным справочным примером для тех, кто строит DSL или интерпретатор на .NET.


Язык	C#
Фреймворк	.NET 10
Тип проекта	Библиотека
Статус	Концепция
Лицензия	AGPL-3.0
NuGet
Загрузки
GitHub	Laraue.PdfQL
Демо-приложение	Laraue.Apps.PdfQL
Живое демо	PDF Extractor

Зачем вообще писать язык запросов?

Извлечение структурированных данных из PDF на C# — таблиц, строк, конкретных ячеек — обычно выглядит как набор повторяющегося, хрупкого императивного кода. Открыть документ, найти элементы по позиции, пройтись по строкам циклом, вручную применить условия. Каждая новая задача по извлечению — это снова бойлерплейт.

Идея PdfQL — выражать такие операции декларативно, как SQL выражает запросы к базе данных. Вместо того чтобы писать императивный C# для поиска таблиц, где в колонке 4 значение "Name", и возврата колонки 1, достаточно написать:

select(tables)
    ->filter((item) => item.GetCell(4).Text() == 'Name')
    ->selectMany(tableRows)
    ->map((item) => item.GetCell(1))

Библиотека парсит эту строку, строит план выполнения и запускает его на PDF-документе. Это и есть основной цикл любого интерпретатора — и именно о его построении эта статья.

Почему не SQL-синтаксис

Первый инстинкт при проектировании языка запросов — взять SQL-подобный синтаксис. Он знаком, широко понятен, и у него хорошая поддержка инструментами.

Но SQL оптимизирован под реляционные данные с джойнами. Документы не имеют такой структуры. PDF-файлы редко "джойнятся". Основные операции: выбрать тип элемента, отфильтровать по условию, преобразовать результат. Это не SELECT ... FROM ... WHERE — это конвейер стадий.

Ближайший аналог — агрегационный конвейер MongoDB: каждая стадия получает вывод предыдущей, применяет трансформацию и передаёт результат дальше. PdfQL напрямую принимает эту модель, используя -> как оператор пайпа между стадиями. Синтаксис намеренно ближе к функциональному method chaining, чем к SQL.

Если концепция выйдет за рамки PDF, язык будет переименован в DocQL — та же модель конвейера, применённая к любому формату документов.

Архитектура: три слоя

Интерпретатор языка запросов решает три отдельные задачи:

Сканер — превращает строку запроса в плоский список токенов
Парсер — превращает список токенов в структурированное дерево (AST)
Исполнитель — обходит AST и выполняет каждую операцию над данными

PdfQL добавляет четвёртый слой, специфичный для предметной области: DocumentObjectsExtractor, который конвертирует сырые байты PDF в типизированную последовательность объектов документа (таблицы, абзацы, изображения, формы) до запуска исполнителя запроса.

Слой 1: Сканер

Задача сканера — токенизация: разбить строку запроса на осмысленные единицы, отбросив пробелы и переносы строк.

Полный словарь токенов определён в TokenType.cs:

public enum TokenType
{
    Identifier, String, Integer,
    Comma, Dot,
    LessThan, GreaterThan, LessOrEqualThan, GreaterOrEqualThan,
    Assign, Equal, NotEqual, Not,
    Minus, Plus, Divide, Multiply,
    LeftParentheses, RightParentheses,
    LeftBracket, RightBracket,
    Lambda,       // =>
    NextPipeline, // ->
    False, True, Null,
    New, Eof,
}

Scanner обрабатывает входную строку посимвольно внутри приватного класса ScannerImplementation. Ключевой паттерн: отслеживаются и абсолютная позиция (смещение в сырой строке для нарезки лексем), и относительная позиция (столбец в текущей строке для сообщений об ошибках). Двухсимвольные операторы — ->, =>, ==, != — обрабатываются вспомогательным методом PopNextCharIf, который условно поглощает следующий символ, только если предикат совпадает:

case '-':
    AddToken(PopNextCharIf(c => c == '>') ? TokenType.NextPipeline : TokenType.Minus);
    break;
case '=':
    AddToken(PopNextCharIf(c => c == '>')
        ? TokenType.Lambda
        : PopNextCharIf(c => c == '=')
            ? TokenType.Equal
            : TokenType.Assign);
    break;

Сканер возвращает ScanResult, содержащий и массив токенов, и объекты ScanError — так вызывающий код получает структурированную информацию об ошибках вместо исключений на некорректный ввод.

Слой 2: Парсер и AST

Парсер берёт плоский поток токенов и строит Abstract Syntax Tree (AST) — иерархическую структуру, отражающую грамматику запроса.

Базовый узел AST намеренно минимален — Expr.cs — это просто пустой базовый record:

public record Expr
{
}

Все типы выражений наследуют от него. Использование C# record даёт структурное равенство бесплатно, что делает юнит-тесты парсера чистыми — ожидаемые и фактические деревья корректно сравниваются без кастомной логики равенства.

Конкретный пример — BinaryExpr.cs, представляющий любое двуоперандное выражение (==, !=, <, >, + и т.д.):

public record BinaryExpr : Expr
{
    public BinaryExpr(Expr left, Token @operator, Expr right)
    {
        Left = left;
        Operator = @operator;
        Right = right;
    }

    public Expr Left { get; init; }
    public Token Operator { get; init; }  // хранит TokenType и фактический lexeme
    public Expr Right { get; init; }

    public override string ToString() => $"{Left} {Operator.Lexeme} {Right}";
}

Поле Operator хранит полный Token — не только тип оператора — чтобы сообщения об ошибках могли указывать точный текст источника и позицию. Рекурсивный ToString() делает всё дерево распечатываемым для отладки, что бесценно при тестировании парсера в изоляции.

Parser использует рекурсивный спуск — каждое грамматическое правило становится методом, вызывающим другие методы для подправил. Это наиболее читаемый подход для написанных вручную парсеров и хорошо ложится на C# без инструментов генерации парсеров вроде ANTLR.

Слой 3: Исполнитель

Исполнитель обходит AST и выполняет его. Для конвейерной модели PdfQL это означает:

Начать с полной последовательности объектов документа, извлечённых из PDF
Для каждой стадии конвейера применить операцию стадии к текущей последовательности
Вернуть финальную последовательность

Каждый тип стадии соответствует известной операции над последовательностью:

Стадия	Операция	Эквивалент в LINQ
`select(tables)`	Фильтр по типу	`OfType<Table>()`
`filter((x) => ...)`	Применение предиката	`Where(x => ...)`
`selectMany(tableRows)`	Разворачивание вложенной коллекции	`SelectMany(x => x.Rows)`
`map((x) => ...)`	Проекция в новое значение	`Select(x => ...)`

Узлы лямбда-выражений в AST компилируются в C# делегаты Func<> во время выполнения. Имя параметра маппится на аргумент делегата, а тело выражения — которое может включать BinaryExpr, вызовы методов, доступ к свойствам и литералы — вычисляется рекурсивно.

Генерация анонимных типов в рантайме через Reflection.Emit

Одна из наиболее нестандартных частей реализации — AnonymousTypeRegistry.cs. Когда стадия map проецирует объекты документа в новые формы — например, возвращает только текстовое содержимое ячейки, а не весь объект ячейки — исполнителю нужно конструировать результирующие типы, структура которых не известна до парсинга запроса в рантайме.

Стандартный анонимный тип C# (new { Name = "x" }) здесь не подходит — он требует, чтобы форма была известна на этапе компиляции. Вместо этого AnonymousTypeRegistry генерирует настоящие CLR-типы динамически с помощью System.Reflection.Emit:

public class AnonymousTypeRegistry
{
    private readonly string _moduleName;
    private readonly HashSet<AnonymousTypeProperties> _declaredProperties = new();
    private readonly Dictionary<AnonymousTypeProperties, Type> _anonymousClassNames = new();

    public Type GetAnonymousType(AnonymousTypeProperties anonymousTypeProperties)
    {
        if (_declaredProperties.Add(anonymousTypeProperties))
        {
            var typeName = $"PdfQLAnonymousType_{_declaredProperties.Count}";
            var type = AnonymousTypeBuilder.CreateType(_moduleName, typeName, anonymousTypeProperties);
            _anonymousClassNames.Add(anonymousTypeProperties, type);
        }

        return _anonymousClassNames[anonymousTypeProperties];
    }
}

AnonymousTypeProperties расширяет ReadOnlyDictionary<string, Type> — ключи это имена свойств, значения — их CLR-типы. Реализации GetHashCode и Equals используют XOR-хэширование по всем парам имя/тип, чтобы реестр корректно дедуплицировал запросы к идентичным формам: два запроса, оба проецирующие в { Text: string }, будут переиспользовать один сгенерированный тип, а не эмитировать его дважды.

Этот паттерн — генерация типов в рантайме и их кэширование по структурному равенству — плохо задокументирован в экосистеме .NET. Большинство статей о Reflection.Emit покрывают генерацию методов; генерация полноценных именованных типов со свойствами, их регистрация в модуле и дедупликация по форме встречается крайне редко. Реализация в PdfQL — рабочий, читаемый справочный пример этой техники.

Демо-приложение

Живое демо на laraue.com/pdf-extractor позволяет тестировать PdfQL-запросы прямо в браузере — загрузите PDF, напишите запрос и получите JSON-вывод. Готовые пресеты (извлечь все таблицы, извлечь все изображения) компилируются в PdfQL внутри.

Веб-API, лежащий в основе демо, находится в отдельном репозитории: github.com/win7user10/Laraue.Apps.PdfQL. Это тонкая ASP.NET Core обёртка над библиотекой — полезная как референс для хостинга PdfQL в веб-контексте.

Исходный код

Полная реализация на github.com/win7user10/Laraue.PdfQL. Ключевые файлы:

Interpreter/Scanning/TokenType.cs — полный словарь токенов
Interpreter/Scanning/Scanner.cs — реализация сканера
Interpreter/Parsing/Expressions/Expr.cs — базовый узел AST
Interpreter/Parsing/Expressions/BinaryExpr.cs — узел бинарного выражения
Interpreter/Parsing/Parser.cs — рекурсивно-спускающий парсер
Interpreter/DelegateCompiling/AnonymousTypeRegistry.cs — генерация типов в рантайме

Проект распространяется под лицензией AGPL-3.0.

Что дальше

Текущая реализация покрывает извлечение таблиц с фильтрацией. Запланированные расширения:

Поддержка обычного текста — select(textRows), select(words), select(sentences)
Поддержка изображений — возврат изображений по условиям; функции вроде resize(600, 400)
Рефакторинг — отвязать исполнитель от PDF-специфичных типов для полноценной реализации концепции DocQL
Пользовательские функции — регистрация собственных функций, вызываемых из лямбд запроса

Часто задаваемые вопросы

Как работает рекурсивно-спускающий парсер на C#?

Рекурсивно-спускающий парсер отображает каждое правило грамматики на C#-метод. Для парсинга бинарного выражения вроде a == b парсер вызывает ParseExpression(), который вызывает ParseEquality(), который вызывает ParseComparison() и так далее по иерархии приоритетов. Каждый метод поглощает токены, которые он распознаёт, и делегирует подвыражения правилам с более низким приоритетом. В результате стек вызовов естественным образом отражает структуру строящегося AST — код легко читать, а грамматику легко расширять.

Можно ли использовать PdfQL в production?

Нет — это концептуальный проект. Конвейер извлечения таблиц работает и покрыт тестами, но библиотека не поддерживается с прицелом на production-надёжность. Для production-извлечения данных из PDF на C# стоит смотреть на PdfPig или iTextSharp. PdfQL наиболее ценен как справочная реализация для построения интерпретаторов и DSL на C#.

Почему не ANTLR или другой генератор парсеров?

Генераторы парсеров — хороший выбор для сложных грамматик. Грамматика PdfQL достаточно проста, чтобы написанный вручную рекурсивно-спускающий парсер было легче читать, отлаживать и изменять — и написание его вручную само по себе является образовательной целью. Весь парсер умещается в несколько сотен строк C#.

В чём разница между транспилером и интерпретатором?

Интерпретатор выполняет AST напрямую в рантайме — именно так работает PdfQL. Транспилер переводит AST в исходный код другого языка (например, компилирует PdfQL в LINQ-выражения или C# код). Слои сканера и парсера идентичны для обоих — отличается только бэкенд. Архитектура PdfQL может быть расширена до транспилера заменой исполнителя на эмиттер кода.

Зачем генерировать анонимные типы динамически вместо Dictionary<string, object>?

Словарь сработал бы, но теряет информацию о типах — нельзя использовать рефлексию или expression trees против него осмысленным образом, а сериализация даёт менее полезный вывод. Генерация настоящего CLR-типа с именованными, типизированными свойствами означает, что результат ведёт себя как любой другой .NET объект: корректно сериализуется в JSON, поддерживает доступ к свойствам через рефлексию и может участвовать в дальнейших LINQ-операциях.

Работает ли этот подход для форматов, отличных от PDF?

Да — и именно в этом долгосрочный замысел дизайна. Исполнитель конвейера уже отвязан от PDF-экстрактора. Добавление поддержки нового формата документов означает реализацию нового DocumentObjectsExtractor для этого формата; язык запросов и исполнитель переиспользуются без изменений.

Как написать интерпретатор языка запросов на C# — разбор на реальном примере