(синтаксические деревья) рекурсивно перебирает деревья снизу вверх с текущим путем сверху вниз - PullRequest
2 голосов
/ 19 января 2010

У меня есть абстрактное синтаксическое дерево , которое мне нужно повторить.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 должен сначала перейти к хвосту дерева, чтобы выполнить итерацию в обратном направлении.На пути к хвосту он может кэшировать текущую позицию и просто извлекать элементы, когда возвращается из рекурсии.

Теперь это ключевое слово: caching .Вот почему я подозреваю, что это возможно с другим классом SPL: RecursiveCachingIterator.

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

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

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

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

1 Ответ

2 голосов
/ 03 февраля 2010

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

...