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

Question

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

最左边的派生对应于解析树的前序遍历，而最右边的派生对应于解析树的后序遍历的相反^[1]

而预序和后序遍历只是深度优先树遍历的两种特定类型^[2]。

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

我的理解正确吗？或者是否存在其他需要/必须使用其他方式遍历解析树的场景？

Answer 1

您只考虑两种可能的解析策略：自顶向下的从左到右解析和自底向上的从左到右解析。当然，这是两种最流行的策略。但这并不是唯一的可能性。

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

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

即使执行从左到右的解析，也不需要在自上而下和自下而上的解析之间进行选择。在LALR算法被发现之前，有相当多的关于“左角”（LC）解析的研究，它在方便的地方（“角落”）在自上而下和自下而上解析之间切换。这样产生的推导既不是最左边也不是最右边，并且很难描述相应的遍历（如我的脚注所示），尽管我认为合理的描述仍然会导致深度优先的对应，因为算法仍然是从左到右的。

在所有情况下，一旦构建了解析树（或抽象语法树），您就可以自由地以任何您喜欢的方式遍历它，并且不同的语义分析算法执行不同类型的遍历。在优化多程编译器中，您可能会发现各种各样不同的树遍历，一些是深度优先，一些是广度优先，还有一些是根据需要弹跳的。

>

另一方面，自底向上策略从最左边的叶节点开始，并继续推导到达该点的遍历，这就是为什么引用的文本称其为遍历的“反向”。这真的是一个有意义的概念吗？当然，作为对最终结果的描述，它是有意义的，但它实际上并不符合“遍历”一词的任何直观意义。如果你要去伦敦，你不能从M40的最后一个出口出发。