为什么我们必须对解析树使用深度优先遍历？
Why do we have to use depth-first traversal for a parse tree?
在我学习解析技术的过程中，似乎解析树总是以深度优先的方式遍历
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]
前序和post序遍历只是两种特定类型
深度优先树遍历[2].
我认为原因在于普通树和解析树之间的区别。普通树仅记录了节点间的拓扑结构，而解析树记录的不止于此。解析树进一步暗示父节点建立在[=34之上=] 子节点，因为父节点 导出 到子节点集合。如果我们想要计算解析树的根节点，这是创建解析树的最终目标，我们必须计算所有先决条件。所以深度优先遍历自然是必须的。
我的理解对吗？或者是否有任何其他场景，其中其他遍历解析树的方式是 necessary/mandatory?
您只考虑了两种可能的解析策略：top-down left-to-right 解析和 bottom-up left-to-right 解析。可以肯定的是，这是两种最受欢迎 的策略。但它们并不是唯一的可能性。
正如您引用的文本所示，这两种策略中的每一种都对应于一个解析树遍历。而两次遍历都是depth-first，实际上是因为两次解析策略都是left-to-right。 [注1]
还有许多其他的解析策略可用，它们将对应于其他树遍历。例如，您可以尝试通过从中间某处开始解析文本（例如，在您出于某种原因确定解析的某个点，可能是因为您在所有可能的括号分组中）并从那里向外工作某种方式由您的解析算法决定。这种策略当然是可行的，甚至有一定数量的文献（可能不是最新的）因为它在对不正确的文本进行部分解析的上下文中是有意义的，例如用于诊断目的或 syntax-highlighted 显示.
即使执行 left-to-right 解析，也不需要在 top-down 和 bottom-up 解析之间进行选择。在发现 LALR 算法之前，对“左角”(LC) 解析进行了大量研究，它在 top-down 和 bottom-up 解析之间切换，以便于这样做（角落”）。这样产生的推导既不是最左的也不是最右的，并且很难表征相应的遍历（根据我的脚注），尽管我认为合理的表征仍然会导致 depth-first 对应，因为算法仍然是 left-to-right.
在所有情况下，一旦构建了解析树（或抽象语法树），您就可以自由地以任何您喜欢的方式遍历它，并且不同的语义分析算法执行不同类型的遍历。在优化的 multi-pass 编译器中，您会期望找到大量不同的树遍历，一些 depth-first，一些 breadth-first，还有一些在必要时反弹。
备注：
不知道这里“穿越”这个词是不是真的准确。解析树并没有真正被遍历，因为它还不存在；它正在建造中。 top-down 策略可以看作是一棵树的 depth-first 预序遍历，它在遍历过程中神奇地出现了。
另一方面，bottom-up 策略从最左边的 leaf 节点开始，并继续推导到达该点的遍历，这就是为什么引用的文本称其为遍历的“反向”。这真的是一个有意义的概念吗？当然，它作为对最终结果的描述是有意义的，但它并不真正符合“遍历”一词的任何直觉意义。如果您前往伦敦旅行，则无法在 M40 的最后出口处开始您的旅行。
在我学习解析技术的过程中，似乎解析树总是以深度优先的方式遍历
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]
前序和post序遍历只是两种特定类型 深度优先树遍历[2].
我认为原因在于普通树和解析树之间的区别。普通树仅记录了节点间的拓扑结构，而解析树记录的不止于此。解析树进一步暗示父节点建立在[=34之上=] 子节点，因为父节点 导出 到子节点集合。如果我们想要计算解析树的根节点，这是创建解析树的最终目标，我们必须计算所有先决条件。所以深度优先遍历自然是必须的。
我的理解对吗？或者是否有任何其他场景，其中其他遍历解析树的方式是 necessary/mandatory?
您只考虑了两种可能的解析策略：top-down left-to-right 解析和 bottom-up left-to-right 解析。可以肯定的是，这是两种最受欢迎 的策略。但它们并不是唯一的可能性。
正如您引用的文本所示，这两种策略中的每一种都对应于一个解析树遍历。而两次遍历都是depth-first，实际上是因为两次解析策略都是left-to-right。 [注1]
还有许多其他的解析策略可用，它们将对应于其他树遍历。例如，您可以尝试通过从中间某处开始解析文本（例如，在您出于某种原因确定解析的某个点，可能是因为您在所有可能的括号分组中）并从那里向外工作某种方式由您的解析算法决定。这种策略当然是可行的，甚至有一定数量的文献（可能不是最新的）因为它在对不正确的文本进行部分解析的上下文中是有意义的，例如用于诊断目的或 syntax-highlighted 显示.
即使执行 left-to-right 解析，也不需要在 top-down 和 bottom-up 解析之间进行选择。在发现 LALR 算法之前，对“左角”(LC) 解析进行了大量研究，它在 top-down 和 bottom-up 解析之间切换，以便于这样做（角落”）。这样产生的推导既不是最左的也不是最右的，并且很难表征相应的遍历（根据我的脚注），尽管我认为合理的表征仍然会导致 depth-first 对应，因为算法仍然是 left-to-right.
在所有情况下，一旦构建了解析树（或抽象语法树），您就可以自由地以任何您喜欢的方式遍历它，并且不同的语义分析算法执行不同类型的遍历。在优化的 multi-pass 编译器中，您会期望找到大量不同的树遍历，一些 depth-first，一些 breadth-first，还有一些在必要时反弹。
备注：
不知道这里“穿越”这个词是不是真的准确。解析树并没有真正被遍历，因为它还不存在；它正在建造中。 top-down 策略可以看作是一棵树的 depth-first 预序遍历，它在遍历过程中神奇地出现了。
另一方面，bottom-up 策略从最左边的 leaf 节点开始，并继续推导到达该点的遍历，这就是为什么引用的文本称其为遍历的“反向”。这真的是一个有意义的概念吗？当然，它作为对最终结果的描述是有意义的，但它并不真正符合“遍历”一词的任何直觉意义。如果您前往伦敦旅行，则无法在 M40 的最后出口处开始您的旅行。