Если ты когда-либо открывал файл грамматики Yacc и задавался вопросом, почему для создания языка нужно учить второй язык, ты не одинок. Генераторы парсеров мощны, но для небольших DSL, которые естественным образом возникают внутри ограниченных контекстов, они почти всегда избыточны.
Можно написать парсер на том же языке, что и остальное приложение. Никаких шагов сборки, никаких файлов грамматики, никакого генерируемого кода, который невозможно отлаживать.
Генераторы парсеров решают проблему, которой у тебя, скорее всего, нет
Генераторы парсеров вроде ANTLR, Bison или PEG.js заставляют выражать грамматику в предметно-ориентированном метаязыке. Пишешь файл .g4 или .y, запускаешь инструмент, получаешь сгенерированный исходный код, импортируешь его и надеешься, что сообщения об ошибках будут понятны, когда что-то сломается.
Для полноценного языка программирования этот компромисс оправдан. Сгенерированные LR-парсеры быстры, а разделение грамматики и реализации чистое.
Но большинство из нас не строит языки программирования. Мы строим фильтры запросов, форматы конфигурации, rule engines или крошечные expression languages, которые живут внутри одного ограниченного контекста. Накладные расходы генератора парсеров, отдельный шаг сборки и необходимость учить второй синтаксис — чистое трение.
Парсер-комбинаторы превращают парсинг в обычный код
Парсер-комбинаторы — это функции, возвращающие парсеры, а парсеры — это функции, потребляющие входные данные и возвращающие либо разобранное значение, либо ошибку. Маленькие парсеры составляются в большие с помощью функций высшего порядка.
Парсер для строки "hello" — это функция. Парсер для "hello" OR "world" — это функция, которая пробует первый, и если он не срабатывает, пробует второй. Парсер для "hello" THEN "world" выполняет их последовательно и объединяет результаты.
Это означает, что твоя грамматика — это просто код. Отлаживаешь его точкой останова, а не инструментом визуализации грамматики.
Работающий арифметический парсер на 40 строках TypeScript
Вот полный парсер для крошечного языка выражений. Он обрабатывает целые числа и сложение в скобках. Никаких зависимостей, никаких сгенерированных файлов.
type Result<T> =
| { ok: true; value: T; pos: number }
| { ok: false; error: string; pos: number };
type Parser<T> = (input: string, pos: number) => Result<T>;
// Primitives: match a literal string or a regex
const str = (expected: string): Parser<string> => (input, pos) => {
const end = pos + expected.length;
return input.slice(pos, end) === expected
? { ok: true, value: expected, pos: end }
: { ok: false, error: `expected "${expected}"`, pos };
};
const regex = (re: RegExp): Parser<string> => (input, pos) => {
const m = input.slice(pos).match(new RegExp(`^(?:${re.source})`));
return m
? { ok: true, value: m[0], pos: pos + m[0].length }
: { ok: false, error: `expected /${re.source}/`, pos };
};
// Combinators: sequence, choice, map, lazy
const map = <A, B>(p: Parser<A>, f: (a: A) => B): Parser<B> => (input, pos) => {
const r = p(input, pos);
return r.ok ? { ...r, value: f(r.value) } : r;
};
const seq = <T extends Parser<unknown>[]>(...ps: T): Parser<any[]> => (input, pos) => {
const values: unknown[] = [];
let curr = pos;
for (const p of ps) {
const r = p(input, curr);
if (!r.ok) return r;
values.push(r.value);
curr = r.pos;
}
return { ok: true, value: values, pos: curr };
};
const or = <A, B>(a: Parser<A>, b: Parser<B>): Parser<A | B> => (input, pos) => {
const r = a(input, pos);
return r.ok ? r : b(input, pos);
};
const lazy = <T>(fn: () => Parser<T>): Parser<T> => (input, pos) => fn()(input, pos);
// Grammar: expr := number | "(" expr "+" expr ")"
const ws = regex(/\s*/);
const number = map(regex(/\d+/), n => parseInt(n, 10));
let expr: Parser<{ val: number }>;
expr = or(
map(
seq(str("("), ws, lazy(() => expr), ws, str("+"), ws, lazy(() => expr), str(")")),
([, , left, , , , right]) => ({ val: left.val + right.val })
),
map(number, val => ({ val }))
);
// Run it
const result = expr("(1 + (2 + 3))", 0);
console.log(result.ok ? result.value : result.error);
// Output: { val: 6 }Разберём, что на самом деле происходит. str, regex и number — примитивные парсеры. seq выполняет парсеры по порядку. or пробует альтернативы. map преобразует результат. lazy — единственная тонкая деталь. Он откладывает вычисление, чтобы рекурсивные грамматики не взорвались во время определения.
Система типов отслеживает, что производит каждый парсер. Когда парсинг не удаётся, получаешь точную позицию и ожидаемый токен. Это уже лучшая отчётность об ошибках, чем предлагают большинство сгенерированных парсеров из коробки.
Почему это особенно хорошо подходит для ограниченных контекстов
Ограниченные контексты в предметно-ориентированном проектировании намеренно малы. DSL, живущий внутри одного из них, тоже должен быть мал. Ему нужны ровно те конструкции, которые важны для этого контекста, и ничего больше.
Парсер-комбинаторы прекрасно масштабируются вниз. Пишешь парсер для единственного фильтра запросов, который нужен твоему домену, а не для языка запросов общего назначения. Добавляешь новую конструкцию, добавляя новую функцию, а не перегенерируя тысячи строк на C.
Парсер живёт в том же репозитории, на том же языке и в той же ментальной модели, что и остальная часть ограниченного контекста. Когда меняется доменная модель, парсер меняется вместе с ней. Нет файла грамматики, который отстаёт от синхронизации в другом каталоге.
Где комбинаторы не справляются
Они не бесплатны. Парсеры с рекурсивным спуском, которые комбинаторы строят под капотом, испытывают трудности с леворекурсивными правилами. Если написать expr := expr + number | number, парсер будет вызывать себя вечно.
Исправляется это переписыванием леворекурсивных правил в циклы или использованием библиотеки, которая обрабатывает левую рекурсию за тебя. Для небольших DSL это редко бывает практической проблемой.
Производительность — другой нюанс. Ручной оптимизированный парсер с рекурсивным спуском или сгенерированный LR-парсер обгонят комбинаторы по чистой пропускной способности. Для файла конфигурации, считываемого один раз при запуске, или правила, вычисляемого на запрос, разница измеряется микросекундами. Измеряй, прежде чем предполагать, что это важно.
Как начать строить свой
Начни с минимально возможной грамматики. Разбери одну конструкцию, протестируй, затем скомпонуй.
Если пишешь на TypeScript, библиотеки вроде parsimmon, arcsecond или chevrotain дают готовые к продакшену комбинаторы с лучшими сообщениями об ошибках и обработкой левой рекурсии, чем приведённая выше самодельная реализация. У Rust есть nom. У Haskell — Parsec. У Python — parsy.
Паттерн везде одинаков: примитивы, последовательность, выбор, повторение, преобразование. Выучи один раз — применяй на любом языке.
FAQ
Что такое парсер-комбинатор?
Парсер-комбинатор — это функция высшего порядка, которая принимает один или несколько парсеров и возвращает новый парсер. Они позволяют строить сложные парсеры, компонуя простые, используя обычный код вместо отдельного языка грамматик.
Когда мне всё же стоит использовать генератор парсеров?
Обращайся к генератору, когда разбираешь полноценный язык программирования, когда нужна максимальная пропускная способность парсинга, или когда в твоей команде уже есть глубокая экспертиза в конкретной экосистеме генератора. Для небольших DSL оверхед обычно не стоит того.
Парсер-комбинаторы медленные?
Они медленнее ручных или сгенерированных LR-парсеров, но разрыв несущественен для большинства сценариев использования DSL. Типичный комбинаторный парсер обрабатывает тысячи токенов за миллисекунду. Это достаточно быстро для файлов конфигурации, query strings и rule engines.
Можно ли использовать парсер-комбинаторы в языках, отличных от TypeScript?
Безусловно. Паттерн не зависит от языка. nom в Rust, Parsec в Haskell, parsy в Python и attoparsec в Haskell — все это зрелые и широко используемые библиотеки.
В следующий раз, когда тебе понадобится крошечный язык внутри ограниченного контекста, спроси себя, действительно ли тебе нужен файл грамматики и шаг генерации кода. Для большинства DSL ответ — нет. Сотня строк комбинаторного кода даст тебе парсер, по которому можно пройтись в дебаггере, расширить без перегенерации и реально понять через полгода.