9

我对 C++ 还是有点陌生​​，所以请耐心等待。我正在为一种名为 Core 的假设语言实现解释器，该语言由 BNF 语法描述。到目前为止，我已经实现了一个标记器，它给了我一个很好的代表核心程序的标记队列。我现在正在编写 Parser/Executer，它从标记器获取输出并使用它使用递归下降解析来填充 ParseTree 类的对象（我必须设计）。我了解如何做到这一点的基础知识，但在实现 ParseTree 类时遇到了麻烦。Core BNF 描述的产品通常有 2-5 个终端/非终端符号，但有些可能多达 20 个，所以我需要一个 n 叉树，其中每个节点可以有不同数量的子节点。

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

4

1 回答 1

7

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

概念如下：如果 A 有 3 个孩子：B、C 和 D 并且 C 有 2 个孩子 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'.
于 2012-10-26T04:26:25.467 回答