在我学习解析技术的过程中,似乎解析树总是以深度优先的方式遍历.
最左边的派生对应于解析树的前序遍历,而最右边的派生对应于解析树的后序遍历的逆序. [1]
预订和后序遍历只是2种特定类型的深度优先树遍历[2].
我认为原因在于普通树和解析树之间的区别.普通树仅在节点之间记录拓扑结构,而解析树记录的不止于此.解析树还意味着父节点构建在子节点上,因为父节点导出到子节点的集合中.如果我们想要计算解析树的根节点,这是创建解析树的最终目标,我们必须计算所有先决条件.所以深度优先遍历是必然的.
我的理解是否正确？或者是否有其他方案需要/强制执行其他遍历解析树的方法？
您只考虑两种可能的解析策略:自上而下的从左到右的解析,以及从下到上的从左到右的解析.这是最受欢迎的两种策略,可以肯定.但它们不是唯一的可能性.
这两个策略中的每一个都对应于一个解析树遍历,正如您引用的文本所示.并且这两个遍历都是深度优先的,实际上是因为两个解析策略都是从左到右.[注1]
许多其他解析策略是可用的,它们将对应于其他树遍历.例如,您可以尝试通过从某个地方的中间开始来解析文本(例如,在某些情况下,由于某种原因某些解析,可能是因为您处于所有可能的括号内),并从那里开始向外工作某种方式由您的解析算法决定.这种策略当然是可能的,甚至有一些关于它的文献(可能不是最新的),因为它在对不正确文本进行部分解析的情况下是有意义的,例如用于诊断目的或语法突出显示.
即使您执行从左到右的解析,您也无需在自上而下和自下而上解析之间进行选择.在发现LALR算法之前,对"左角"(LC)解析进行了相当多的研究,它在自上而下和自下而上解析之间进行切换("角落") ).这样产生的推导既不是最左边也不是最右边,并且很难描述相应的遍历(根据我的脚注),尽管我认为合理的表征仍然会导致深度优先对应,因为算法仍然是 - -对.
在所有情况下,一旦构造了解析树(或抽象语法树),您就可以以任何您喜欢的方式自由遍历它,并且不同的语义分析算法执行不同类型的遍历.在优化的多遍编译器中,您可能会发现各种不同的树遍历,一些深度优先,一些广度优先,一些在必要时反弹.
我不确定"traverse"这个词在这里是否真的准确.解析树并没有真正被遍历,因为它还不存在; 它正在建设中.自上而下的策略可以被视为树的深度优先前序遍历,在遍历期间神奇地存在.
另一方面,自下而上策略从最左边的叶节点开始,并继续推导到达该点的遍历,这就是引用文本称之为遍历的"反向"的原因.这真的是一个有意义的概念吗？当然,它对于最终结果的描述是有意义的,但它并不真正对应于任何直观的"遍历"一词.如果您前往伦敦,则无法在从M40最终出口的地方开始您的行程.
京公网安备 11010802040832号 | 京ICP备19059560号-6 