シンボルテーブル

コンピュータサイエンスにおいて、シンボルテーブルは、コンパイラやインタープリタなどの言語翻訳者が使用するデータ構造であり、プログラムのソースコード内の各識別子、シンボル、定数、手続き、関数は、その宣言やソース内での出現に関する情報と関連付けられます。つまり、シンボルテーブルのエントリには、エントリに対応するシンボルに関する情報が格納されます。^[1]

シンボルテーブルは、変換プロセス中にメモリ内にのみ存在する場合もあれば、後で使用するためにABI オブジェクトファイルなどの変換の出力に埋め込まれる場合もあります。たとえば、対話型デバッグセッション中に使用される場合や、プログラムの実行中または実行後に診断レポートをフォーマットするためのリソースとして使用される場合もあります。^[2]

トランスレータと中間表現(IR) が使用するシンボル テーブルに含まれる最小限の情報には、シンボルの名前と位置またはアドレスが含まれます。再配置可能性の概念を持つプラットフォームをターゲットとするコンパイラの場合、再配置可能性属性 (絶対、再配置可能など) と再配置可能なシンボルに必要な再配置情報も含まれます。高水準プログラミング言語のシンボル テーブルには、シンボルの型 (文字列、整数、浮動小数点など)、サイズ、次元、境界が格納されます。この情報はすべて出力ファイルに含まれるわけではありませんが、デバッグに使用するために提供される場合があります。多くの場合、シンボルの相互参照情報はシンボル テーブルとともに格納されるか、シンボル テーブルにリンクされます。ほとんどのコンパイラは、この情報の一部またはすべてを、変換の最後にシンボル テーブルと相互参照リストに出力します。^[1]

テーブルを実装するために、さまざまなデータ構造を使用できます。ツリー、線形リスト、自己組織化リストはすべて、シンボル テーブルを実装するために使用できます。シンボル テーブルは、字句解析から始まり、最適化まで、 コンパイラのほとんどのフェーズでアクセスされます。

コンパイラは、すべてのシンボルに対して 1 つの大きなシンボル テーブルを使用することも、異なるスコープに対して分離された階層的なシンボル テーブルを使用することもできます。たとえば、AlgolやPL/Iなどのスコープ付き言語では、シンボル「p」は、おそらく異なる属性を持つ複数のプロシージャで個別に宣言できます。各宣言のスコープは、その宣言で「p」への参照が解決されるプログラムのセクションです。各宣言は、一意の識別子「p」を表します。シンボル テーブルには、異なる「p」への参照を区別する何らかの手段が必要です。

シンボルテーブルを実装するために使用される一般的なデータ構造はハッシュテーブルです。ハッシュテーブルの検索時間はテーブルに格納されている要素の数に依存しないため、要素数が多い場合に効率的です。また、ハッシュキーの計算に分類を含めることで、表形式のリテラルの分類を簡素化します。^[3]

字句解析プログラムは、シンボル テーブルの検索に多くの時間を費やすため、このアクティビティはコンパイラ全体の速度に重大な影響を及ぼします。シンボル テーブルは、エントリが可能な限り迅速に見つかるような方法で編成する必要があります。ハッシュ テーブルは通常、シンボル テーブルを編成するために使用されます。ハッシュ テーブルでは、キーワードまたは識別子が「ハッシュ」されて配列の添え字が生成されます。ハッシュ テーブルでは衝突は避けられません。衝突を処理する一般的な方法は、同義語をテーブル内の次の空き領域に格納することです。

オブジェクトファイルには、外部から参照可能な識別子のシンボル テーブルが含まれます。異なるオブジェクト ファイルをリンクする際に、リンカーはこれらのシンボル参照を識別して解決します。通常、すべての未定義の外部シンボルは、1 つ以上のオブジェクト ライブラリで検索されます。そのシンボルを定義するモジュールが見つかった場合は、最初のオブジェクト ファイルと一緒にリンクされ、未定義の外部識別子は、検索する識別子のリストに追加されます。このプロセスは、すべての外部参照が解決されるまで続行されます。プロセスの最後に 1 つ以上の未解決の識別子が残っている場合はエラーになります。

実行可能ファイルをリバース エンジニアリングする際、多くのツールはシンボル テーブルを参照して、グローバル変数と既知の関数に割り当てられたアドレスを確認します。実行可能ファイルに変換する前にシンボル テーブルが削除または消去されている場合、ツールはアドレスを特定したり、プログラムについて理解したりすることが難しくなります。

Cで書かれた次のプログラムを考えてみます。

// 外部関数を宣言します
extern double bar ( double x );   

// パブリック関数を定義します
double foo ( int count ) { double sum = 0.0 ;  

       

    // bar(1)からbar(count)までのすべての値を合計します。
for ( int i = 1 ; i <= count ; i ++ ) sum += bar (( double ) i ); return sum ; }            
           
     

このコードを解析する C コンパイラには、少なくとも次のシンボル テーブル エントリが含まれます。

iさらに、シンボル テーブルには、中間式の値 (たとえば、ループ変数を にキャストする式double、関数 の呼び出しの戻り値bar()など)、ステートメント ラベルなどに対してコンパイラによって生成されたエントリも含まれる場合があります。

シンボル テーブルの例は、 SysV アプリケーション バイナリ インターフェイス(ABI) 仕様にあります。この仕様では、バイナリ ファイル内でシンボルをどのように配置するかを規定しており、これにより、さまざまなコンパイラ、リンカー、ローダーが、コンパイルされたオブジェクト内のシンボルを一貫して見つけて操作できるようになります。

SysV ABI は、GNU binutils の nmユーティリティで実装されています。この形式では、ソートされたメモリ アドレスフィールド、「シンボル タイプ」フィールド、およびシンボル識別子 (「名前」と呼ばれる) が使用されます。^[4]

SysV ABI (および nm の出力) のシンボル タイプは、シンボル テーブルの各エントリの性質を示します。各シンボル タイプは 1 つの文字で表されます。たとえば、初期化されたデータを表すシンボル テーブル エントリは文字 "d" で示され、関数のシンボル テーブル エントリはシンボル タイプ "t" を持ちます (実行可能コードはオブジェクト ファイルのテキストセクションにあるため)。さらに、シンボル タイプの大文字化は、リンケージのタイプを示します。小文字はシンボルがローカルであることを示し、大文字は外部 (グローバル) リンケージを示します。

Pythonプログラミング言語には、シンボルテーブルの作成と操作に対する広範なサポートが含まれています。^[5]照会できるプロパティには、特定のシンボルが自由変数か束縛変数か、ブロックスコープかグローバルスコープか、インポートされているかどうか、どの名前空間に属しているかなどがあります。

一部のプログラミング言語では、シンボルテーブルを実行時に操作できるため、いつでもシンボルを追加できます。Racketはそのような言語の一例です。^[6]

LISPとSchemeの両方のプログラミング言語では、各シンボルに任意の汎用プロパティを関連付けることができます。^[7]

Prologプログラミング言語は、本質的にはシンボル テーブル操作言語です。シンボルはアトムと呼ばれ、シンボル間の関係を推論することができます。同様に、OpenCog は、知識表現に使用されるアトムスペースと呼ばれる動的シンボル テーブルを提供します。

• デバッグシンボル
• .デバッグ情報

• Copper, Keith D.; Torczon, Linda (2011 年 1 月 18 日)。コンパイラのエンジニアリング (第 2 版)。テキサス州ヒューストン: Elsevier 、ライス大学。doi : 10.1016 / C2009-0-27982-7。ISBN 978-0-12-088478-0. S2CID  40425497。