4

私は現在 C でコンパイラに取り組んでおり、AST のデータ構造を構築する部分、特に ID の構造を構築する部分で少し迷っています。これは「シンボル テーブル エントリ」と呼ばれます。

次のようなネット上の構造が表示されます。

struct ste {
  struct id   *name;  /* pointer into hash table for assoc. id */
  struct decl *decl;  /* pointer into symbol table for its decl */
  struct ste  *prev;  /* pointer to previous entry in symbol table */
};

前のエントリ (*prev) へのポインターを保持しているため、リンクされたリストのように見えますが、この背後にあるロジックは何ですか?

4

3 に答える 3

8

具体的な質問への答えは次のとおりです。前のリンクは、コードにこれらのノードのいずれかへのポインターがある場合、チェーン内の前のリンクへのリンクをたどることができることを意味します。シンボル テーブルにこのようなリストが含まれる理由の 1 つは、ネストされたスコープを処理するためです。

{
int x;
  {
   int x;
  }
}

ただし、シンボル ノードをリストに配置する理由は他にもたくさんあります。コンパイラがすべてのノードにアクセスする必要があるのには理由があります。

于 2009-12-26T00:54:36.917 に答える
2

あなたはずっと前に C プログラマーからの有害な習慣の名残りを見ています: シンボルがいくつかのリストにあると想定され、リスト構造を個別に割り当てる代わりに、リスト ポインターはシンボル構造の一部として含まれます。このトリックにより、リスト要素ごとに 1 つの割り当てが節約されますが、コストがかかります。シンボルを配置できるリストのセットは固定されており、この構造はプログラマーを混乱させます。アプリケーションがコンパイラである場合、このトリックを使用する理由はもうありません。次のように定義された別のリスト構造を持つ方がはるかに明確です。

struct ste_list {
    struct ste *symbol_table_entry;
    struct str_list *next;
};

これらは好きなだけ持つことができ、賢い人はいません。そして、紛らわしい内部ポインタはなくなります。

あなたが尋ねる

この背後にあるロジックは何ですか？

答えの一部は単純に、識別リストにシンボルがあると便利だということです。特定のコンパイラについて詳しく知らないと、質問に明確に答えることはできません。私の最善の推測では、prevエントリがネストされたスコープ ( { ... }C の括弧) を実装するために使用されることになりますが、それは私が見たり作業したりしたコンパイラに基づく推測です。したがって、おそらくロジックは、右中かっこが検出されると、コンパイラは、それがste外側のスコープ内に到達するまでそのリンクをたどる可能性があるということです。あなたが勉強しているコンパイラの作者よりも少し経験のある人は、通常、このロジックを「シンボルテーブルの抽象化」に入れますenterscope()。exitscope()、およびこれらの操作の詳細は、個々のシンボル テーブル エントリの内部表現から隠されます。

于 2009-12-26T02:54:30.017 に答える
1

逆方向リンクリストの使用について私が最初に考えたのは、次のような変数名のオーバーライドをサポートする言語用です。

int main (void) {
    int x = 1;
    int y = 1;
    if (x == 1) {
        int y = 2;
        printf ("y = %d\n", y);
    }
    return 0;
}

その場合、最も内側のスコープ (最後に定義されたスコープ) を持つ変数にアクセスする必要があります。これは、リストを逆方向にたどることで見つけることができます (もちろん、順方向にリストを作成していると仮定します)。

次に、スコープが消えたら、「ヘッド」ポインターを調整して、最後に追加された変数を削除することもできます。

もちろん、リストの末尾に追加するのではなく、現在のヘッドの前に挿入することで同じ効果を得ることができます (概念的prevには、 の代わりにポインターが呼び出されるだけで何が行われているように見えますnext)。

于 2009-12-26T00:58:25.953 に答える