3

好奇心から、プログラミング言語のテキストパーサーを書いています。トークンの不変 (実行時) グラフを頂点/ノードとして定義したいとします。これらは当然、タイプが異なります。一部のトークンはキーワードであり、一部は識別子などです。ただし、それらはすべて、グラフ内の各トークンが別のトークンを指すという共通の特性を共有しています。このプロパティにより、パーサーは特定のトークンの後に何が続くかを知ることができます。したがって、グラフは言語の正式な文法を定義します。私の問題は、数年前に C++ を日常的に使用するのをやめ、それ以来、多くの高水準言語を使用しており、ヒープ割り当て、スタック割り当てなどに関して頭が完全に断片化されていることです。残念ながら、私の C++ は錆びています。

それでも、急な坂をすぐに登って、このグラフをこの命令型言語で最もパフォーマンスの高い方法で定義するという目標を設定したいと思います。たとえば、「new」を使用して各トークン オブジェクトをヒープに個別に割り当てることは避けたいと考えています。これは、これらのトークンのグラフ全体をいわば背中合わせに (配列内の要素のように線形に) 割り当てると考えるからです。これは、参照原則の局所性ごとに、何らかの形でパフォーマンスに利益をもたらします-すべてのトークンオブジェクトをランダムな場所に配置するのではなく、グラフ全体がメモリ内の「行」に沿って最小限のスペースを占有するように圧縮される場合、それはプラスですか? とにかく、ご覧のとおり、これは非常にオープンな質問です。

class token
{

}

class word: token
{
    const char* chars;

    word(const char* s): chars(s)
    {
    }
}

class ident: token
{
    /// haven't thought about these details yet
}

template<int N> class composite_token: token
{
    token tokens[N];
}

class graph
{
    token* p_root_token;
}

当面の質問は、このグラフ オブジェクトを作成する手順はどのようなものかということです。それは不変であり、コンパイル時に構造が既知であると考えられているため、値によるコピーなどを避けることができ、回避したいのです-このグラフをリテラルから構成することは可能ですか? ここで意味を成していることを願っています... (理解できなかったのはこれが初めてではありません。) グラフは、実行時にコンパイラの一部としてパーサーによって使用されます。これが C++ であるという理由だけで、C ソリューションにも満足できます。事前にどうもありがとうございました。

4

3 に答える 3

3

私のC++もさびているので、おそらくこれに対する最善の解決策はわかりません。しかし、他の誰も前進しなかったので...

1つのブロックにすべてのノードを割り当てると、最適なローカリティが得られるという点で正しいです。ただし、プログラムの開始時にグラフを動的に割り当てる場合は、ヒープの割り当ても密接にクラスター化される可能性があります。

すべてのノードを単一のメモリブロックに割り当てるには、2つの可能性が思い浮かびます。起動時にVector <>を作成してデータを入力するか（グラフ情報がメモリに2回あるという欠点があります）、静的配列初期化子「Node」を使用します。 []グラフ={...}; " 。

どちらのアプローチでも、最大の障害は、異種オブジェクトのグラフを作成することです。明らかな解決策の1つは、「しない」です。ノードをすべての可能なフィールドのスーパーセットにし、明示的な「type」メンバーでタイプを区別することができます。

さまざまなノードクラスを保持する場合は、タイプごとに1つずつ、複数の配列/ベクトルを使用する必要があります。

いずれの場合も、ノード間の接続は、最初に配列インデックスで定義する必要があります（Node[3]の後にNode[10]が続きます）。もちろん、解析パフォーマンスを向上させるために、これらのインデックスに基づいて、プログラムの起動時に直接オブジェクトポインタを作成することもできます。

リテラル文字列をノード（あなたの場合は「単語」）に入れません。キーワード、識別子、およびその他の字句要素の認識は、パーサーとは別の字句モジュールで行う必要があります。プログラムの入力に基づいてレクサーによって生成されたトークンと、プログラムが入力を解析するために使用する文法グラフノードをターミナルで区別することも役立つと思います。

これがお役に立てば幸いです。

于 2010-10-28T19:57:31.883 に答える
3

特にトークン間の関係が「許可されている」場合、実際のプログラミング言語の構文を定義するトークンの「グラフ」をどのように定義するのかわかりません。

プログラミング言語の文法を表す通常の方法は、Backus-Naur Form (BNF)または「EBNF」と呼ばれるこれの拡張バージョンを使用することです。

EBNF を (「不変のグラフとして」) 表現したい場合、この SO の回答では、C# でそれを行う方法について説明しています。このアイデアは、C++ に直接類似しています。

悪いニュースは、ほとんどの解析エンジンが EBNF を直接使用できないことです。これは、実際には非効率的すぎるためです。文法規則の直接表現を使用して効率的なパーサーを構築するのは困難です。これが、人々がパーサージェネレーターを発明した理由です。したがって、パーサー ジェネレーターを作成するつもりがない限り、これらのルールをメモリ構造に配置する必要性はまったく不明です。「効率的な」ルールは言うまでもありません。

最後に、文法情報を何らかの方法で最適にパックしたとしても、おそらく実際のパフォーマンスにわずかな違いはありません。パーサーの時間のほとんどは、語彙素で文字をグループ化することに費やされ、空白の抑制を行うだけになることもあります。

于 2010-10-28T22:46:20.933 に答える
1

トークンの小さな割り当ての多くがボトルネックになるとは思いません。ボトルネックがあれば、いつでもメモリプールを選択できます。

問題に; すべてのトークンには同様のデータがあるため（次のトークンへのポインターがあり、処理するトークンの列挙値が含まれている可能性があります）、同様のデータを1つのstd::vectorに入れることができます。これはメモリ内の連続データであり、ループオーバーするのに非常に効率的です。

ループしている間、必要な種類の情報を取得します。トークン自体には、理想的には「アクション」（メンバー関数）のみが含まれると思います。たとえば、前と次のトークンが数字で、私がプラス記号の場合は、数字を足し合わせる必要があります。

したがって、データは1つの中央の場所に格納され、トークンが割り当てられ（ただし、実際には多くのデータが含まれていない可能性があります）、中央の場所でデータに作用します。これは実際にはデータ指向の設計です。

ベクトルは次のようになります。

struct TokenData
{
    token *previous, *current, *next;
    token_id id; // some enum?
    ... // more data that is similar
}

std::vector<TokenData> token_data;

class token
{
    std::vector<TokenData> *token_data;
    size_t index;

    TokenData &data()
    {
        return (*token_data)[index];
    }

    const TokenData &data() const
    {
        return (*token_data)[index];
    }
}

// class plus_sign: token
// if (data().previous->data().id == NUMBER && data().next->data().id == NUMBER)

for (size_t i = 0; i < token_data.size(); i++)
{
    token_data[i].current->do_work();
}

それはアイデアです。

于 2010-10-28T23:01:38.037 に答える