1. 为什么不直接在tree中放NodeImpl*指针，NodeImpl指向自己的其他结点，而要用smallvector记录索引的方式，两者相比后者有什么好处？

    使用 NodeImpl* 指针直接连接节点之间的关系是一种常见的方式来构建解析树，这被称为 “树的引用链接”。虽然这是一种有效的方法，但使用 llvm::SmallVector 记录索引的方式有一些优势：

    • 内存连续性: 当使用 NodeImpl* 指针直接链接节点时，每个节点都需要一个额外的指针字段来引用其子节点。这可能导致节点的内存分布不连续，因为子节点可以位于内存中的任何位置。相比之下，使用索引的方式可以保持节点在内存中的连续性，这可以提高内存访问的效率。

    • 内存效率: 使用索引可以显著降低每个节点的内存开销。指针通常需要占用4字节（32位系统）或8字节（64位系统）的内存，而索引通常可以用较少的字节来表示。这对于大型解析树来说是一个重要的考虑因素，因为可以减少内存占用。

    • 数据的一致性和稳定性: 使用索引的方式可以使解析树的节点保持更加一致和稳定的状态。如果使用 NodeImpl* 直接链接节点，当解析树进行动态修改时，可能需要频繁地调整指针以反映新的结构。这可能会引入潜在的 bug 和不稳定性。使用索引，解析树的结构更容易维护，因为节点之间的链接不会频繁更改。

    总之，使用 llvm::SmallVector 记录索引的方式可以提高内存和性能效率，同时保持解析树的数据一致性和稳定性。

  2. 深度优先后序遍历是什么，反向后序（reverse postorder即RPO）遍历是什么，举例详细解释：

    • 深度优先后序遍历：深度优先后序遍历是一种树或图遍历算法，它首先从根节点开始，深度优先地遍历树的每个分支，然后在返回根节点之前，遍历子节点。具体来说，遍历顺序如下：
      1. 从根节点开始，递归地遍历第一个子节点。
      2. 在子节点的子树上递归地执行相同的步骤，直到达到叶子节点。
      3. 然后返回父节点，继续递归到下一个兄弟节点（如果存在）。
      4. 最终，回到根节点，遍历完成。

    深度优先后序遍历的一个关键特点是，在访问任何节点之前，它会首先访问该节点的所有子节点。这使得该遍历方式特别适用于树结构的处理，例如解析树。

    • 反向后序（RPO）遍历：反向后序遍历是深度优先后序遍历的一种变体，它的遍历顺序是相反的，即从根节点开始，首先遍历兄弟节点，然后递归到子节点。具体来说，遍历顺序如下：
      1. 从根节点开始，遍历所有兄弟节点。
      2. 对于每个兄弟节点，递归地执行相同的步骤，首先遍历其兄弟节点，然后递归到子节点。
      3. 最终，回到根节点，遍历完成。

    反向后序遍历与深度优先后序遍历相比，更注重在兄弟节点之间的顺序，而不是子节点的顺序。这种遍历方式通常用于图的拓扑排序或执行后续遍历算法的情况。

    举例详细解释：

    假设有以下简单的树结构表示数学表达式：

    1
2
3
4
5
6

    +
├── 2
├── *
│   ├── 3
│   └── 4
└── 5

    • 深度优先后序遍历：遍历顺序是 2, 3, 4, *, 5, +。首先深度遍历左子树，然后返回到根节点，再遍历右子树。

    • 反向后序遍历：遍历顺序是 2, 3, 4, 5, *, +。首先遍历兄弟节点，然后递归到子节点。

    总之，深度优先后序遍历和反向后序遍历是两种不同的遍历方式，它们在遍历节点的顺序上有所不同，适用于不同的应用场景。