Compiler-design-symbol-table
コンパイラの設計-シンボルテーブル
シンボルテーブルは、変数名、関数名、オブジェクト、クラス、インタフェースなどのさまざまなエンティティの出現に関する情報を格納するためにコンパイラによって作成および管理される重要なデータ構造です。 シンボルテーブルは、コンパイラの解析部分と合成部分の両方で使用されます。
シンボルテーブルは、使用する言語に応じて次の目的に使用できます。
- すべてのエンティティの名前を構造化された形式で1か所に保存します。
- 変数が宣言されているかどうかを確認します。
- 型チェックを実装するには、ソースコード内の割り当てと式が意味的に正しいことを確認します。
- 名前のスコープを決定するには（スコープ解決）。
シンボルテーブルは、単なるテーブルであり、線形テーブルまたはハッシュテーブルのいずれかです。 次の形式で各名前のエントリを維持します。
<symbol name, type, attribute>たとえば、次の変数宣言に関する情報をシンボルテーブルに保存する必要がある場合：
static int interest;次に、次のようなエントリを保存する必要があります。
<interest, int, static>属性句には、名前に関連するエントリが含まれます。
実装
コンパイラが少量のデータを処理する場合、シンボルテーブルは順序付けられていないリストとして実装できます。これはコーディングが簡単ですが、小さなテーブルにのみ適しています。 シンボルテーブルは、次のいずれかの方法で実装できます。
- 線形（ソート済みまたは未ソート）リスト
- 二分探索ツリー
- ハッシュ表
とりわけ、シンボルテーブルはほとんどハッシュテーブルとして実装されます。ソースコードシンボル自体はハッシュ関数のキーとして扱われ、戻り値はシンボルに関する情報です。
オペレーション
シンボルテーブル（線形またはハッシュ）は、次の操作を提供する必要があります。
インサート（）
この操作は、分析フェーズ、つまりトークンが識別され、名前がテーブルに保存されるコンパイラーの前半でより頻繁に使用されます。 この操作は、ソースコードで発生する一意の名前に関する情報をシンボルテーブルに追加するために使用されます。 名前が格納される形式または構造は、手元のコンパイラに依存します。
ソースコード内のシンボルの属性は、そのシンボルに関連付けられた情報です。 この情報には、シンボルに関する値、状態、スコープ、およびタイプが含まれます。 insert（）関数は、シンボルとその属性を引数として受け取り、情報をシンボルテーブルに格納します。
例えば：
int a;コンパイラは次のように処理する必要があります。
insert(a, int);見上げる（）
lookup（）操作は、シンボルテーブル内の名前を検索して以下を決定するために使用されます。
- シンボルがテーブルに存在する場合。
- 使用される前に宣言されている場合。
- スコープで名前が使用されている場合。
- シンボルが初期化されている場合。
- シンボルが複数回宣言された場合。
lookup（）関数の形式は、プログラミング言語によって異なります。 基本的な形式は次と一致する必要があります。
lookup(symbol)シンボルがシンボルテーブルに存在しない場合、このメソッドは0（ゼロ）を返します。 シンボルがシンボルテーブルに存在する場合、テーブルに格納されている属性を返します。
スコープ管理
コンパイラは、2種類のシンボルテーブルを維持します。すべてのプロシージャからアクセスできる*グローバルシンボルテーブル*と、プログラムの各スコープに対して作成される*スコープシンボルテーブル*です。
名前の範囲を決定するために、下の例に示すように、シンボルテーブルは階層構造に配置されます。
. . .
int value=10;
void pro_one()
{
int one_1;
int one_2;
{ \
int one_3; |_ inner scope 1
int one_4; |
} /
int one_5;
{ \
int one_6; |_ inner scope 2
int one_7; |
} /
}
void pro_two()
{
int two_1;
int two_2;
{ \
int two_3; |_ inner scope 3
int two_4; |
} /
int two_5;
}
. . .上記のプログラムは、シンボルテーブルの階層構造で表すことができます。
グローバルシンボルテーブルには、1つのグローバル変数（int値）の名前と、上記のすべての子ノードで使用可能な2つのプロシージャ名が含まれています。 pro_oneシンボルテーブル（およびそのすべての子テーブル）に記載されている名前は、pro_twoシンボルとその子テーブルでは使用できません。
このシンボルテーブルのデータ構造階層はセマンティックアナライザに保存され、シンボルテーブルで名前を検索する必要がある場合は常に、次のアルゴリズムを使用して検索されます。
- 最初に、現在のスコープでシンボルが検索されます。 現在のシンボルテーブル。
- 名前が見つかった場合、検索は完了します。それ以外の場合は、親シンボルテーブルで検索され、
- 名前が見つかるか、グローバルシンボルテーブルで名前が検索されました。
