Что такое рекурсивный спуск? Если говорить кратко, это один из вариантов синтаксического разбора сверху вниз. Он основан на ручном переводе в исполняемый код синтаксических правил, представленных, например, в БНФ. В теле каждого правила вхождение нетерминала заменяется вызовом соответствующей функции, а альтернатива моделируется с помощью конструкции ветвления.
Есть мнение, что времена рекурсивного спуска давно прошли. Существуют мощные программы-генераторы, позволяющие автоматизировать процесс разработки парсеров. Тем не менее, имеется большое число современных, промышленных компиляторов, использующих рекурсивных спуск. Вот лишь несколько примеров:
- GCC
- Clang
- rustc
- Swift
- Go
- Lua
- TypeScript
- V8
- Roslyn
- Elm
- javac
- Kotlin
Впечатляющий перечень, не правда ли? В чем же причина такой популярности древнего метода, требующего ручного труда разработчика компилятора?
Рекурсивный спуск не ограничивается классом граматик LL(1). В коде легко можно реализовать и предпросмотр на произвольное количество токенов, и запоминание промежуточных результатов разбора, и механизм отката.
Важно отметить, что в чистом виде рекурсивный спуск действительно используется нечасто. Таким образом обычно реализуют компиляторы языка Oberon. В основном же, разработчики компиляторов не в восторге от необходимости иметь дело с разбором выражений с приоритетами. Проблемы с необходимостью факторизации грамматики и с неважным быстродействием разбора выражений с большим числом приоритетов решаются, тем не менее, достаточно просто — с помощью техники, основанной на классическом алгоритме сортировочной станции Дейкстры (shunting yard), которая легко интегрируется в общую схему рекурсивного спуска. Речь о precedence climbing/Pratt parser. В результате разбор выражений легко представить в компактной табличной форме.
Ниже представлен перечень некоторых положительных качеств рекурсивного спуска в сравнении с генераторами синтаксических анализаторов.
- Простота интеграции с остальным кодом компилятора. Настройка и в целом попытка достичь взаимопонимания с программой-генератором иной раз обходится дороже, чем прямая реализация разбора в коде.
- Возможность оптимизации быстродействия и потребления памяти. От кода рекурсивного спуска обычно проще добиться необходимых характеристик, чем от программы-генератора, которая для пользователя выглядит, как черный ящик.
- Возможность детальной диагностики ошибок, а также восстановления после ошибок. В ручном режиме проще обработать сложные специальные случаи. Это одна из причин, по которой Rust и Elm, отличающиеся подробными сообщениями об ошибках, используют рекурсивный спуск.
- Простота отладки. Свой код отладить проще, чем "выхлоп" программы-генератора.
- Мощность разбора. В ручном режиме, теоретически, возможен разбор для неограниченных или, иначе, Тьюринг-полных грамматик. Это необходимо для полной поддержки языков со свободно переопределяемым синтаксисом, таких, как Forth или Lisp (reader macro), а также для разбора шаблонов в C++.
- Простота описания разбора. В случае с программами-генераторами приходится изучать дополнительный и не всегда гибкий формализм описания грамматики языка. При этом читаемость и декларативность формализма зачастую не выдерживают столкновения с реальностью в виде контекстно-зависимых грамматик сложных языков программирования и необходимости совершения дополнительных семантических действий на стадии разбора.
- Легкость добавления дополнительных возможностей: инкрементальный разбор, устойчивость к ошибкам в синтаксисе (resilient parsing) и так далее.
Здесь необходимо отметить, что не все современные генераторы парсеров однозначно уступают рекурсивному разбору с точки зрения перечисленных выше пунктов. Весьма гибкими, к примеру, являются Menhir (Ocaml) и SDF3 (Java), но и в их случае п.1 зачастую оказывается серьезным препятствием на пути к использованию. Вот несколько случаев, когда использование генератора синтаксического анализатора представляется вполне оправданным:
- Прототипирование языка программирования, синтаксис которого еще не до конца сформирован.
- Разработка инструмента статического анализа, использующего несколько входных языков с различным синтаксисом.
- Подсветка синтаксиса. В этой задаче грамматику входного языка часто можно упростить для удобства ее представления на языке программы-генератора.
- Некоторые варианты фаззинг-тестирования. Удобно, когда одно и то же описание грамматики языка используется и для разбора, и для порождения случайных фраз на этом языке.
Разумеется, рекурсивный спуск неидеален. Особенные проблемы вызывает тот факт, что в коде "за деревьями не видно леса", то есть восстановить грамматику языка по программной реализации бывает очень тяжело. То же касается и сложности внесения изменений в разбор. Все это является следствием императивного, низкоуровневого подхода к реализации парсера. Можно ли описать разбор кодом, но в декларативно-функциональном духе, в виде eDSL? Можно. В этом случае мы приходим к идее использования комбинаторов синтаксического разбора, но о них лучше поговорить отдельно.