(синтаксические деревья) рекурсивно перебирают деревья снизу вверх по текущему пути сверху вниз

Question

у меня есть абстрактное синтаксическое дерево который мне нужно повторить.AST генерируется порт лимона на PHP.

Теперь «обычно» я бы сделал это с совершенно новыми и блестящими (PHP 5.3.1) классами SPL, и это выглядело бы так:

$it = new \RecursiveIteratorIterator(
  new \RecursiveArrayIterator($ast['rule']),
  \RecursiveIteratorIterator::SELF_FIRST);

Собственно, это я уже делаю в другой части кода, которая грубо определяет тип всего дерева (т. е. это может быть присваивание, условие и т. д.).Теперь о деталях, единственное, что важно, это то, что итерация выполняется RecursiveIteratorIterator::SELF_FIRST, то есть сверху вниз.

Возвращаясь к моей проблеме, мне нужно перебрать AST снизу вверх, то есть что-то вроде RecursiveIteratorIterator::CHILD_FIRST, чтобы выполнить некоторые замены и оптимизации в дереве.

Проблема в том, что эти операции должны быть контекстно-зависимыми, т.е.Мне нужен путь до текущего узла.А поскольку я хочу выполнить итерацию снизу вверх, я не могу этого сделать с помощью RecursiveIteratorIterator.

Ну, подумай об этом на секунду.Я хочу выполнить итерацию снизу вверх и иметь нисходящий контекст (стек) текущего узла на каждой итерации.Технически это должно быть возможно, поскольку RecursiveIteratorIterator должен сначала перейти к хвосту дерева, чтобы выполнить итерацию в обратном направлении.На пути к хвосту он может кэшировать текущую позицию и просто вытаскивать элементы по мере возврата из рекурсии.

Теперь это ключевое слово: кэширование.Вот почему я подозреваю, что это должно быть возможно с другим классом SPL:РекурсивныйКэширующийИтератор.

Вопрос в том:это действительно возможно?Если да, то как?

Я пытался разобраться с некоторым кодом, но безуспешно, а документации недостаточно.Действительно, очень мало.

Тот, кто найдет наиболее элегантное решение этой проблемы с помощью SPL, снимаю шляпу!Вы гуру PHP!

ПС:если что не ясно, я ищу столько же звукового давления (ре) использование по возможности.Я знаю, что могу написать свои собственные рекурсивные функции с собственным стеком, не нужно мне об этом напоминать.

Answer 1

Мне удалось заставить его работать, унаследовав RecursiveIteratorIterator и управляя стеком в ::endChildren() и ::callGetChildren соответственно.Возможно, это поможет кому-то.Снимаю шляпу перед собой :-)