シンボルテーブル
コンピュータサイエンスにおいて、シンボルテーブルとは、コンパイラやインタープリタなどの言語翻訳者が用いるデータ構造であり、プログラムのソースコード内の各識別子、シンボル、定数、手続き、関数が、その宣言またはソースコード内での出現に関する情報と関連付けられている。言い換えれば、シンボルテーブルのエントリは、エントリに対応するシンボルに関する情報を格納している。[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 コンパイラには、少なくとも次のシンボル テーブル エントリが含まれます。
| シンボル名 | タイプ | 範囲 |
|---|---|---|
bar | 関数、double | 外部 |
x | ダブル | 関数パラメータ |
foo | 関数、double | グローバル |
count | 整数 | 関数パラメータ |
sum | ダブル | ローカルブロック |
i | 整数 | forループ文 |
さらに、シンボル テーブルには、中間式の値 (たとえば、iループ変数を にキャストする式doubleや、関数 の呼び出しの戻り値などbar())、ステートメント ラベルなどに対してコンパイラによって生成されたエントリも含まれる場合があります。
例: SysV ABI
| 住所 | タイプ | 名前 |
|---|---|---|
| 00000020 | 1つの | T_ビット |
| 00000040 | 1つの | F_ビット |
| 00000080 | 1つの | I_ビット |
| 20000004 | t | irqvec |
| 20000008 | t | フィクヴェツ |
| 200万セント | t | 初期化リセット |
| 20000018 | T | _主要 |
| 20000024 | t | 終わり |
| 20000030 | T | AT91F_US3_CfgPIO_useB |
| 2000005c | t | AT91F_PIO_Cfgペリフ |
| 200000b0 | T | 主要 |
| 20000120 | T | AT91F_DBGU_プリント |
| 20000190 | t | AT91F_US_TxReady |
| 200001c0 | t | AT91F_US_PutChar |
| 200001f8 | T | AT91F_スプリアスハンドラー |
| 20000214 | T | AT91F_データ中止 |
| 20000230 | T | AT91F_フェッチ中止 |
| 2000024c | T | AT91F_未定義 |
| 20000268 | T | AT91F_未定義ハンドラー |
| 20000284 | T | AT91F_低レベル初期化 |
| 200002e0 | t | AT91F_DBGU_CfgPIO |
| 2000030c | t | AT91F_PIO_Cfgペリフ |
| 20000360 | t | AT91F_US_構成 |
| 200003dc | t | AT91F_US_ボーレート設定 |
| 2000041c | t | AT91F_US_ボーレート |
| 200004ec | t | AT91F_US_SetTimeguard |
| 2000051c | t | AT91F_PDC_オープン |
| 2000059c | t | AT91F_PDC_無効Rx |
| 200005c8 | t | AT91F_PDC_送信無効 |
| 200005f4 | t | AT91F_PDC_SetNextTx |
| 20000638 | t | AT91F_PDC_SetNextRx |
| 2000067c | t | AT91F_PDC_SetTx |
| 200006c0 | t | AT91F_PDC_SetRx |
| 20000704 | t | AT91F_PDC_EnableRx |
| 20000730 | t | AT91F_PDC_EnableTx |
| 2000075c | t | AT91F_US_EnableTx |
| 20000788 | T | __aeabi_uidiv |
| 20000788 | T | __udivsi3 |
| 20000884 | T | __aeabi_uidivmod |
| 2000089c | T | __aeabi_idiv0 |
| 2000089c | T | __aeabi_ldiv0 |
| 2000089c | T | __div0 |
| 200009a0 | D | _データ |
| 200009a0 | あ | _etext |
| 200009a4 | あ | __bss_end__ |
| 200009a4 | あ | __bss_スタート |
| 200009a4 | あ | __bss_スタート__ |
| 200009a4 | あ | _edata |
| 200009a4 | あ | _終わり |
シンボル テーブルの例は、 SysV アプリケーション バイナリ インターフェイス(ABI) 仕様にあります。この仕様では、さまざまなコンパイラ、リンカー、ローダーがコンパイルされたオブジェクト内のシンボルを一貫して見つけて操作できるように、バイナリ ファイル内でシンボルをどのように配置するかが規定されています。
SysV ABIはGNU binutilsの nmユーティリティに実装されています。このフォーマットは、ソートされたメモリアドレスフィールド、「シンボルタイプ」フィールド、そしてシンボル識別子（「名前」と呼ばれます）を使用します。[4]
SysV ABI（およびnmの出力）のシンボルタイプは、シンボルテーブル内の各エントリの性質を示します。各シンボルタイプは1文字で表されます。例えば、初期化されたデータを表すシンボルテーブルエントリは文字「d」で示され、関数を表すシンボルテーブルエントリはシンボルタイプ「t」を持ちます（実行可能コードはオブジェクトファイルのテキストセクションに配置されるため）。さらに、シンボルタイプの大文字/小文字はリンケージの種類を示します。小文字はシンボルがローカルであることを示し、大文字は外部（グローバル）リンケージであることを示します。
例: Pythonのシンボルテーブル
Pythonプログラミング言語には、シンボルテーブルの作成と操作のための広範なサポートが含まれています。[5]照会できるプロパティには、特定のシンボルが自由変数か束縛変数か、ブロックスコープかグローバルスコープか、インポートされているかどうか、どの名前空間に属しているかなどがあります。
例: 動的シンボルテーブル
一部のプログラミング言語では、シンボルテーブルを実行時に操作できるため、いつでもシンボルを追加できます。Racketはそのような言語の一例です。[6]
LISPとSchemeの両方のプログラミング言語では、各シンボルに任意の汎用プロパティを関連付けることができます。[7]
Prologプログラミング言語は本質的にシンボルテーブル操作言語です。シンボルはアトムと呼ばれ、シンボル間の関係を論理的に解釈することができます。同様に、OpenCogはアトムスペースと呼ばれる動的なシンボルテーブルを提供し、知識表現に使用されます。
参照
参考文献
- ^ Copper & Torczon 2011、253ページより。
- ^ Nguyen, Binh (2004). Linux Dictionary. p. 1482 . 2018年4月14日閲覧。
- ^ Copper & Torczon 2011、254ページ。
- ^ “nm”. sourceware.org . 2020年5月30日閲覧。
- ^ symtable — Python ドキュメント
- ^ シンボル - Racket ドキュメント
- ^ シンボル - Guile ドキュメント
参考文献
- Copper, Keith D.; Torczon, Linda (2011年1月18日). Engineering a Compiler (第2版). Houston , Texas : Elsevier , Rice University . doi :10.1016/C2009-0-27982-7. ISBN 978-0-12-088478-0. S2CID 40425497。
