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

Question

我对 C++ 还是有点陌生​​，所以请多多包涵。我正在为一种名为 Core 的假设语言实现解释器，该语言由 BNF 语法描述。到目前为止，我已经实现了一个分词器，它为我提供了一个很好的代表核心程序的分词队列。我现在正在编写解析器/执行器，它从分词器获取输出并使用它来使用递归下降解析来填充 ParseTree 类(我必须设计)的对象。我了解如何执行此操作的基础知识，但在实现 ParseTree 类时遇到问题。 Core BNF 描述的产生式通常有 2-5 个终结符/非终结符符号，但有些可能有多达 20 个，所以我需要一个 n 叉树，其中每个节点可以有不同数量的子节点。

我想 ParseTree 类不一定需要使用树来实现它，但这似乎最有意义(是否有不同的数据结构可能更好/更容易？)。我不知道 STL 中有任何容器符合我的需要。我查看了 Boost 属性树，但据我所知，这也行不通。如果可能的话，我不想重新发明轮子并从头开始实现树。此外，除了 Boost 之外，我无法使用任何外部库。实现我的 ParseTree 的最佳方法是什么？我可以使用任何好的预制树实现吗？

Answer 1

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

概念如下:如果A有三个 child :B、C和D，C有2个 child E和F如下

              A
            / | \
           B  C  D
              /\
             E  F

这可以表示为

              A
             /
             B
              \
               C
              / \
             E   D
              \
               F

即 child 总是去左节点， sibling 去右节点。构建起来也很容易，这棵树的前序遍历与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'.