C++递归下降解析中n元树的实现

Question

我还不太熟悉C++，所以请多包容。我正在为一个叫做Core的虚构语言编写解释器。目前我已经实现了一个分词器，可以给出表示Core程序的标记队列。现在我正在编写解析器/执行器，该解析器将从分词器输出并使用递归下降解析来填充ParseTree类的对象（需要自行设计）。我理解如何实现这个功能的基本原理，但在实现ParseTree类时遇到了麻烦。Core BNF描述的产生式通常有2-5个终端/非终端符号，但有些可能有多达20个，因此我需要一个n元树，其中每个节点都可以有不同数量的子节点。

我想ParseTree类的实现不一定需要使用树，但那似乎是最合理的选择（是否有更好/更容易的数据结构？）。 我不知道STL中是否有适合我需求的容器。虽然我已经看过Boost属性树，但据我所知，那也不行。 如果可能的话，我希望不要从头开始实现树而重新发明轮子，而是使用最佳的方式来实现ParseTree。是否有任何好的预制树实现我可以使用？

- user1776041

---

你的问题涉及数据结构，而不是递归下降解析。 - user207421

Answer 1

我建议使用“左儿子右兄弟”二叉树来表示解析树。它是n叉树的替代品。“第一个孩子，下一个兄弟”二叉树可以表示任何n叉树。

概念如下： 如果A有三个孩子：B、C和D，C有两个孩子E和F，如下所示。

              A
            / | \
           B  C  D
              /\
             E  F

这可以表示为：

              A
             /
             B
              \
               C
              / \
             E   D
              \
               F

即孩子节点始终进入左节点，兄弟节点进入右节点。这样构建树也很容易，此树的先序遍历与n叉树的先序遍历相同。

n叉树的先序遍历：

display (node, level) {
    if (!node) return;
    print node;
    display (node->left, level+1);
    display (node->right, level+1);
}

子节点兄弟二叉树的前序遍历

display (node, level) {
    if (!node) return;
    print node;
    display (node->left, level+1);
    display (node->right, level);
}

如何构建这棵树：

1. Throw your terminals and non-terminals in a Stack.
2. When you want to combine n nodes under parent node 'p', pop 'n' elements from stack, making the last pop as the right child of the current pop.
3. Finally make the nth pop the left child of node 'p'.

- aakash

---

听起来需要遍历很多次，这种类型的树有什么好处？ - hexist

@hexist：'Node'的结构很简单。在构建具有未知子节点数量的AST时，这非常有效，因为我们只需要维护2个指针（左、右）。此外，如果我没记错的话，在构建解释器时，经常访问兄弟节点，在这种情况下应该很容易实现。 - aakash

啊，我明白了，你总是知道自己相对于兄弟姐妹的位置，这在某些情况下确实很有用。 - hexist

我同意这个答案。我以前就用过这种树来达到这个目的。 - john