language-agnostic - 抽象语法树的构建与遍历

Question

我不清楚抽象语法树的结构。要在 AST 所代表的程序的源代码中“向下(向前)”，您是在最顶部的节点上还是向下？例如，示例程序

a = 1
b = 2
c = 3
d = 4
e = 5

结果是一个看起来像这样的 AST:


或这个:


在第一个位置，在 main node 上“正确”将推进您完成该程序，但在第二个中只需遵循 next每个节点上的指针都会做同样的事情。

似乎第二个会更正确，因为您不需要像第一个节点可能具有极长指针数组的特殊节点类型之类的东西。虽然，当你进入 for 时，我可以看到第二个变得比第一个更复杂。循环和 if分支和更复杂的东西。

Answer 1

第一种表示是更典型的表示，尽管第二种表示与作为递归数据结构的树的构造兼容，当实现平台是功能性的而不是命令性的时可以使用。

考虑:



这是您的第一个示例，除了缩短和使用“主”节点(概念上的稻草人)更恰本地命名为“块”之外，以反射(reflect)包含命令式编程语言中的语句序列的“块”的常见构造。不同种类的节点有不同种类的子节点，有时这些子节点包括顺序很重要的辅助节点的集合，就像“块”的情况一样。例如，数组初始化可能会出现同样的情况:

int[] arr = {1, 2}

考虑如何在语法树中表示:



这里，array-literal-type 节点也有多个相同类型的子节点，其顺序很重要。