Формальные языки
Parser Combinators
GNU Bison генерирует 5000 строк C для простой грамматики. Parser combinators: та же грамматика - 50 строк Haskell или Rust, которые можно тестировать по одной функции. Rustls разбирает TLS 1.3 handshake nom-ом - 300 строк, ноль небезопасного кода.
- nom используется в rustls (TLS-стек), git2-rs, парсере PDF у pdfium
- pest (PEG для Rust) используется в TOML-парсере cargo, языке Dhall
- chumsky используется в языке Pika и в Roc programming language
- tree-sitter - GLR parser, сгенерированный из grammar.js - используется в Neovim, GitHub Linguist
Parsec и монадические парсеры
Parser combinator - функция высшего порядка, принимающая парсеры и возвращающая парсер. Parsec (Haskell) - первая популярная библиотека этого стиля. Парсер: функция от входной строки к (результат, остаток) или ошибка.
Parsec реализует monadic interface: парсеры объединяются через >>= (bind) и >> (then). Это позволяет строить сложные парсеры из простых без явного управления позицией в строке.
Чем parser combinator отличается от написания парсера вручную (recursive descent)?
nom: zero-copy parsing в Rust
nom - Rust-библиотека parser combinators с нулевым копированием. Работает со срезами байт (&[u8]) или строк (&str). Используется в: rustls (TLS), git2-rs, номинальном парсере Rust компилятора для proc macros.
- nom работает с &[u8]: подходит для бинарных форматов (MQTT, DNS, PNG, HTTP/2)
- zero-copy: парсер возвращает срез исходного буфера, не аллоцирует новые строки
- IResult<Input, Output> = Result<(Input, Output), Error> - стандартный интерфейс
- nom используется в ripgrep для парсинга regex паттернов
- chumsky - альтернатива с лучшими error recovery и арбитражным backtracking
Почему nom возвращает (остаток, значение) вместо (значение, остаток)?
Monadic parsing и PEG
PEG (Parsing Expression Grammar) - формализм, который точно соответствует parser combinators. PEG детерминирован: choice (/) всегда пробует левый альтернатив первым, нет ambiguity.
Монадическая структура Parsec (Haskell): Parser a = Parser { runParser :: String -> [(a, String)] }. Монадный bind >>= позволяет зависимые парсеры: второй парсер может зависеть от результата первого. Это мощнее, чем applicative-стиль, но сложнее для статического анализа.
Почему PEG всегда детерминирован, а CFG может быть неоднозначной?
Error recovery и качество сообщений
Главный недостаток naive parser combinators - плохие сообщения об ошибках. При откате (backtracking) теряется информация где именно произошла ошибка. Rustc, GCC, clang - все вложили огромные усилия в качество диагностики.
- Longest match: при backtracking сохранять самую дальнюю позицию ошибки
- Error recovery: после ошибки пропустить до следующего sync-токена (';', '}') и продолжить
- Labels: именовать парсеры для понятных сообщений ("expected expression" вместо "expected '('")
- chumsky поддерживает multiple errors за один проход благодаря error recovery
- tree-sitter использует recovery для incremental re-parsing при редактировании кода
Что такое longest match эвристика в parser combinators?
Итоги
- Parser combinator - функция высшего порядка, парсеры - значения первого класса
- PEG точно соответствует combinators: ordered choice, нет ambiguity
- nom: zero-copy Rust, IResult<&[u8], T>, работает с бинарными форматами
- Error recovery: longest match + sync tokens = качественная диагностика
Связанные темы
Parser combinators стоят на пересечении формальных языков и функционального программирования:
- LL и LR парсеры — Combinators реализуют LL(*) - те же ограничения: левую рекурсию нужно устранять
- Монады (Haskell) — Monadic bind >>= - механизм композиции зависимых парсеров в Parsec
- Tree-sitter — GLR-парсер генерирует инкрементальный парсер для редакторов из PEG-подобной грамматики
- Регулярные выражения — many(char('a')) в combinators соответствует a* в regex, но мощнее за счёт рекурсии
Вопросы для размышления
- Почему parser combinators плохо справляются с левой рекурсией без специальных техник?
- В каких случаях стоит использовать генератор парсеров (ANTLR, bison) вместо combinators?
- Как error recovery в chumsky влияет на производительность в happy-path случае?