algorithm - 为什么我们必须对解析树使用深度优先遍历？

Question

在我学习解析技术的过程中，似乎总是以深度优先的方式遍历解析树。

The leftmost derivation corresponds to a preorder traversal of the parse tree, while the rightmost derivation corresponds to the reverse of a postorder traversal of the parse tree. ^[1]

前序遍历和后序遍历只是两种特定类型 深度优先树遍历 ^[2] .

我认为原因在于普通树 和解析树 之间的区别。普通树仅记录了节点间的拓扑结构，而解析树记录的不止于此。解析树进一步暗示父节点建立在子节点之上，因为父节点 派生到子节点的集合中。如果我们想要计算解析树的根节点，这是创建解析树的最终目标，我们必须计算所有先决条件。所以深度优先遍历自然是必须的。

我的理解对吗？或者是否有任何其他场景需要/强制使用其他遍历解析树的方式？

Answer 1

您只考虑了两种可能的解析策略:自上而下的从左到右解析和自下而上的从左到右解析。可以肯定的是，这是两种最受欢迎​​ 的策略。但它们并不是唯一的可能性。

正如您引用的文本所示，这两种策略中的每一种都对应于一个解析树遍历。并且这两个遍历都是深度优先的，实际上是因为这两个解析策略都是从左到右的。 [注1]

还有许多其他解析策略可用，它们将对应于其他树遍历。例如，您可以尝试通过从中间某处开始解析文本(例如，在您出于某种原因确定解析的某个点，可能是因为您在所有可能的括号分组中)并从那里向外工作某种方式由您的解析算法决定。这种策略当然是可行的，甚至有一定数量的文献(可能不是最新的)因为它在对不正确的文本进行部分解析的上下文中是有意义的，例如用于诊断目的或语法高亮显示。

即使执行从左到右的解析，也不需要在自上而下和自下而上的解析之间做出选择。在发现 LALR 算法之前，对“左角”(LC) 解析进行了大量研究，它在方便的时候在自上而下和自下而上的解析之间切换(“角” ).这样产生的推导既不是最左的也不是最右的，并且很难表征相应的遍历(根据我的脚注)，尽管我认为合理的表征仍然会导致深度优先对应，因为该算法仍然是左到-对。

在所有情况下，一旦解析树(或抽象语法树)被构建，您就可以自由地以任何您喜欢的方式遍历它，并且不同的语义分析算法执行不同类型的遍历。在优化的多 channel 编译器中，您会期望找到大量不同的树遍历，一些是深度优先的，一些是广度优先的，还有一些会根据需要反弹。

---

注意事项:

1. 我不确定“遍历”这个词在这里是否真的准确。解析树并没有真正被遍历，因为它还不存在；它正在 build 中。自上而下的策略可以看作是树的深度优先预序遍历，树在遍历过程中神奇地出现。

   另一方面，自下而上的策略从最左边的叶节点开始，并继续推导到达该点的遍历，这就是为什么引用的文本将其称为“反向” ”的穿越。这真的是一个有意义的概念吗？当然，它作为对最终结果的描述是有意义的，但它并不真正符合“遍历”一词的任何直觉意义。如果您要去伦敦旅行，则无法在 M40 的最后一个导出开始您的旅程。