Зачем строить AST Walker вместо того, чтобы узлы отвечали за свой вывод?

Question

Учитывая AST, что может быть причиной создания Walker класса, который проходит по дереву и выводит результат, в отличие от предоставления каждому Node классу compile() метода и ответственности за его собственный выход

Вот несколько примеров:
Doctrine 2 (ORM) использует SQLWalker для обхода AST и генерации SQL из узлов.
Twig (язык шаблонов) заставляет узлы выводить свой собственный код (это узел оператора if).

Answer 1

Использование отдельного Walker для генерации кода позволяет избежать комбинаторного взрыва числа классов узлов AST по мере увеличения числа целевых представлений. Когда Walker отвечает за генерацию кода, вы можете перенастроить его на другое представление, просто изменив класс Walker. Но когда за компиляцию отвечают сами узлы AST, вам нужна отдельная версия каждого узла для каждого отдельного целевого представления.

Answer 2

В основном из-за старой литературы и доступных инструментов.Экспериментируя с обоими методами, вы легко обнаружите, что обход AST создает очень медленный и запутанный код.Более того, код, отделенный от непосредственного синтаксиса, больше не похож на него.Это очень похоже на поддержку двух синхронизированных баз кода, что всегда является плохой идеей.Отладка, обслуживание становятся трудными.

Конечно, также может быть трудно обрабатывать семантику на узлах, если у вас нет хорошо спроектированного конечного автомата.На самом деле вы никогда не бывает хуже, чем обходить AST после факта, потому что это только один частный случай обработки семантики на узлах.

Часто можно услышать, что обход AST позволяет реализовать несколько семантик для одного и того же синтаксиса,На самом деле вы этого никогда не захотите, не только потому, что это требуется редко, но и по соображениям производительности.И, честно говоря, нетрудно написать отдельный синтаксис для другой семантики.Результаты всегда были лучше, когда оба спроектированы вместе.

И, наконец, в каждой нетривиальной задаче синтаксический синтаксический анализ - это самая легкая часть, правильная семантика и быстрое выполнение действий - сложная задача.Сосредоточение внимания на AST приближает задачу назад.

Answer 3

Для поддержки функции, которой не обладает "внутренний AST Walker".

Например, есть несколько способов обойти «иерархическую» или «древовидную» структуру, как «сначала пройдитесь по листьям» или «сначала пройдитесь по ветвям».

Или, если узлы-братья и сестры имеют индекс сортировки, и вы хотите "ходить" / "посещать" их по порядку, а не по возрастанию.

Если класс или структура AST, которые у вас есть, работает только с одним методом, вы можете использовать другой метод, используя свой пользовательский "walker" / "посетитель".