9

私はまだC++に少し慣れていないので、我慢してください。私は BNF 文法で記述された Core と呼ばれる仮想言語のインタープリターを実装しています。ここまでで、コア プログラムを表すトークンのキューを作成するトークナイザーを実装しました。現在、トークナイザーからの出力を取得し、それを使用して、再帰降下解析を使用して ParseTree クラス (これを設計する必要があります) のオブジェクトを設定するパーサー/実行プログラムを作成中です。これを行う方法の基本は理解していますが、ParseTree クラスの実装に問題があります。コア BNF で記述されたプロダクションには、通常 2 ～ 5 個の終端/非終端記号がありますが、最大 20 個あるものもあるため、各ノードが異なる数の子を持つことができる n-ary ツリーが必要です。

ParseTree クラスは必ずしもその実装にツリーを使用する必要はないと思いますが、それが最も理にかなっているようです (より良い/簡単な別のデータ構造はありますか?)。私が必要とするものに適合するSTLのコンテナを認識していません。Boost プロパティ ツリーを見てきましたが、どちらも機能しないことがわかります。可能であれば、車輪を再発明してツリーをゼロから実装することは避けたいと思います。また、Boost 以外の外部ライブラリを使用できないという制約もあります。私の ParseTree を実装する最良の方法は何ですか? 使用できる事前に作成されたツリーの実装はありますか?

4

1 に答える 1

7

解析ツリーを表すために、「左の子、右の兄弟」のバイナリツリーを使用することをお勧めします。これは、n-aryツリーの置き換えです。任意のn-aryツリーは、「最初の子、次の兄弟」のBINARYツリーを使用して表すことができます。

概念は次のとおりです。Aに3つの子がある場合：B、C、およびDであり、Cには次のように2つの子EおよびFがあります。

              A
            / | \
           B  C  D
              /\
             E  F

これは次のように表すことができます

              A
             /
             B
              \
               C
              / \
             E   D
              \
               F

つまり、子は常に左側のノードに移動し、兄弟は右側のノードに移動します。構築も簡単で、このツリーの事前注文トラバーサルは、n-aryツリーの事前注文トラバーサルと同じです。

n-aryツリーの事前注文トラバーサル：

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 に答える