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

发布于 2024-08-18 13:52:27 字数 1224 浏览 8 评论 0原文

我有一个需要迭代的抽象语法树。 AST 由 lemon 到 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（re）使用。我知道我可以使用自定义堆栈编写自己的递归函数，无需提醒我这一点。

原文

I have an abstract syntax tree which I need to iterate. The AST is generated by the lemon port to PHP.

Now "normally", I'd do it with the brand new and shiny (PHP 5.3.1) SPL classes, and it would look like this:

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

Actually, that's what I'm already doing in another part of the code which determinates a rough type of the entire tree (i.e it can be an assignment, a condition, etc). Now details aside, the only important thing is the iteration is done RecursiveIteratorIterator::SELF_FIRST, that is, top-down.

Going back to my problem, I need to iterate the AST bottom-up, that is, something like RecursiveIteratorIterator::CHILD_FIRST, in order to do some substitutions and optimizations in the tree.

The problem is, these operations need to be context-aware, i.e. I need the path down to the current node. And since I want to iterate bottom-up, I can't have that with RecursiveIteratorIterator.

Well think about it for a second. I want to iterate bottom-up and have the top-down context (a stack) of the current node, at each iteration. Technically it should be possible, since RecursiveIteratorIterator must first go to the tail of the tree, in order to iterate backwards. In its way to the tail, it could cache the current position, and simply pop out elements as it returns back from recursion.

Now this is a keyword: caching. This is why I suspect it should be possible with another SPL class: RecursiveCachingIterator.

The question is: is it really possible? If yes, how?

I've been trying to puzzle around with some code, without success, and the documentation is scarce. Really, really scarce.

Whoever finds the most elegant solution to this using SPL, hats off! You're a PHP guru!

PS: in case it's not clear, I'm looking for as much SPL (re)usage as possible. I know I could write my own recursive functions with a custom stack, no need to remind me about that.

分享到QQ

分享到微博