（语法树）以当前自上而下的路径自下而上递归迭代树

Question

我有一个abstract syntax tree，我需要迭代。 AST由lemon port to 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类：RecursiveCachingIterator。

问题是：它真的有可能吗？如果是，如何？

我一直在试图绕过一些代码，没有成功，而且文档很少。真的，真的很稀缺。

无论谁发现最优雅的解决方案，这使用SPL，关闭！你是一位PHP大师！

PS：如果现在还不清楚，我正在寻找尽可能多的SPL（重新）使用尽可能。我知道我可以用自定义堆栈编写我自己的递归函数，不需要提醒我这些。

Answer 1

我已经设法通过继承RecursiveIteratorIterator并分别在:: endChildren（）和:: callGetChildren中管理堆栈来实现它。也许这会帮助别人。帽子给我自己:-)