Парсер-комбинаторы на TypeScript: разбираем реальный вывод команды ping
Регулярные выражения плохо читаются на вложенных форматах, а tree-sitter тяжеловесен. Короткая серия постов строит типизированный средний путь из обычных функций.
Парсер здесь — это функция, которая принимает строку и возвращает значение и непрочитанный остаток. Маленькие парсеры объединяются в большие с помощью pSeq, pMap и pRepeat, а типизированный результат — это кортеж или объект, а не массив совпадений.
Готовый пример разбирает заголовок, строки по каждому пакету и сводку реального запуска ping в один типизированный объект.
Парсер — это функция, которая возвращает остаток
В статье Parser<T> определён как функция, которая принимает строку и возвращает [T, rest]. pInteger распознаёт цифры регулярным выражением, pHello проверяет литеральный префикс. Цепочка строится так: каждый парсер получает остаток строки от предыдущего.
Общие блоки небольшие:
pSeqобъединяет любое число парсеров и собирает результаты в типизированный кортеж, используя дженерики TypeScript и вариативные типы.pMapпреобразует результат, например превращает кортеж в именованный объект.pRepeatприменяет парсер, пока тот не упадёт, как*в регулярных выражениях.
Поскольку каждый комбинатор принимает парсеры и возвращает парсер, грамматики собираются из вложенных функций. Рабочий пример разбирает реальный вывод ping: заголовок, строки по каждому пакету и итоговую статистику в один типизированный объект. По мнению автора, так это проще читать, тестировать и поддерживать, чем большое регулярное выражение для вложенных форматов.
Сигнатура скрывает сбои, а об ограничениях не упомянули
Участник, который в другой ветке доказывает, что парсеры должны возвращать EitherT для каждого входа:
«…функция не определена на всех входах.»
Автор статьи, ответивший в ветке, и в профиле которого указан t3.at, подтвердил этот пробел:
«Поскольку мы работаем в TypeScript, частичный парсер всегда может выбросить исключение (насколько я помню, так делает и библиотека parsimmon). Я решил не вдаваться в эти подробности слишком глубоко!»
Постоянный участник с кармой 52 000 хотел, чтобы издержки назвали сразу:
«Им стоило бы хотя бы указать ограничения подхода. Например, что он не справляется с леворекурсивными грамматиками и что на неоднозначных грамматиках он часто откатывается назад, что даёт экспоненциально плохую производительность.»
contificate, в профиле которого указан compiler.club, назвал достоинство, которое серия пропустила: парсеры в стиле continuation-passing получают потоковую обработку бесплатно.
«Поэтому многие из этих парсеров хорошо работают с потоками (например, TCP-сокетами) без ручного ведения машины состояний, как может понадобиться в C.»
Вывод ping плоский и построчный, поэтому подход подходит безопасно. Прежде чем применять его к рекурсивной или неоднозначной грамматике, решите, как будут проявляться ошибки (статья выбрасывает исключение), и проверьте стоимость откатов. Если регулярное выражение на плоском формате перевалило за 100 символов, пробуйте именно этот подход.
Получайте такие разборы каждый день
Главные истории Hacker News — на email, в Telegram или RSS.
Любительский 3D-принтер с точностью 1 микрон и каплями смолы 4 микрона
Проект µRepRap хочет, чтобы микромасштабное производство стало таким же доступным, каким RepRap сделал настольную 3D-печать: на обычных деталях и с UV-светодиодом под столом.