Cコンパイラ設計(yacc・lexの応用)/第5章　セマンティックス上の制限事項のバックアップ(No.2)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
Cコンパイラ設計(yacc・lexの応用)/第5章　セマンティックス上の制限事項へ行く。

2008/05/16からのアクセス回数 5920

第5章　セマンティックス上の制限事項

第5章　セマンティックス上の制限事項 †

かたくるしい言語認識の一般的問題から、プログラム・テキストを解析し翻訳した実行可能なものを生成する、という明確な問題に移ることにしよう。したがってここでは、文章の代わりにプログラムという言葉を用いることにする。これは、終端記号の列として定義され、ある文法に対応した唯一のパーズ・トリーが構成できるもののことである。この章でプログラムにどのような付加制限を加えるかを扱って、コンパイラの解析部の設計を完了する。以下の章では、プログラムによって記述されたアルゴリズムの実行可能バージョンの合成について述べる。

↑

問題点 †

プログラムは構文的に正しくても、意味的な誤りを含むことがある。典型的な例として、次のようなものが挙げられる。

Pascalでは、ラベルは数字だけからなる文字列で、使う前にlabe1宣言部で宣言されていなければならない。このような数字列は、字句解析部がIntegerC㎝stantとしていても、 gOto文で使う時には、宣言されているラベルであることをコンパイラが検証しなければならない。
Pascalでは、ラベルは使う前に宣言しなければならない。C言語では、ラベルはIdentifier である。すなわち、goto文で新たに導入されると、暗黙的にラベルとして宣言されたことになる。ほとんどすべての言語で、ラベルは使った後で定義することができる。コンパイラは、すべてのラベルが、実際に定義されているかどうかを検証しなければならない。

ラベルは、可視範囲のやっかいな問題の一つの例である。ユーザが定義したオブジェクトは、名前の可視範囲として知られているプログラム・テキストの特定の範囲でのみ認識される。 BASICでは、変数名の可視範囲はプログラム・テキスト全体である(ただし、ユーザ定義関数の引数名は例外)。FORTRANでは、変数名はプログラム単位、すなわち一つのfunctionまたはsubroutine内でのみ認識される。そして、プログラム単位名と。ommonエリア名は、実行される一つのファイルであるイメージに束縛されるすべてのモジュールから認識される。Pascal やその他のAlgo1系言語では、ユーザが定義した名前は、ブロック、すなわちそれが定義されているプログラム・テキストの文法的に区切られた一部分でのみ認識される。フロックは入れ子構造をとることができ、外側のブロックの名前の定義は、内側のフロックで同じ名前を定義することにより、内側のフロック内で覆い隠すことができる。C言語では、Algolのブロック構造と、FORTRANのモジュールの概念を結合している。複合文は、入れ子構造をとることができるブロックであり、宣言を持つことができ、その可視範囲は限定される。関数名は、広域的に認識することができ、呼び出される前に宣言される必要はない。さまざまなオブジェクトに対する適切なアクセスを提供するコードを生成することと同様、ユーザが定義した名前がそれぞれに対応した可視範囲内で正しく使われているかどうかをモニターするのも、コンパイラの仕事である。

通常、名前は一つのコンテクスト中で二度宣言することはできない。たとえば、二つのパラメータは同じ名前であってはならず、同じブロック内の二つの局所変数には別の名前を使わなければならず、また同じstruct、mion、recordの二つの構成要素は異なっていなければならない。C言語では、structと他の名前が同一になってもいいことになっているが、C言語のいくつかのバージョンでは、異なる構造体であっても、構成要素の名前は異なっていなければならないという制限があるものもある。

プログラムにおける宣言は、コンパイラに対し、一つの名前の意図した使われ方を伝達する。いったんユーザが合意すれば、誤った使われ方をされないようにしなければならない。次のようなことを考えてみよう。

PL/Iや、awkのような入念に設計された寛大なツールは例外として、多くの言語では、文字列と数値を組み合わせることができない。たとえば、文字列と数値の加算はできない。 Pascalでは混合モードの式、すなわちrea1型とinteger型の値の組合せはほとんどの演算子に対して許されているが、一定の制限が適用される。すなわち、divはintegerの除算のみを表わし、ノはたとえオペランドが二つともintegerであっても、結果がrealになるものを表わす。:= は、integerからrealへの代入は許すが逆は許さない、などである。

演算子は、オペランドの型によって、正確な意味が変化する。BASICの中には、十が数値の加算の他、文字列の結合を表わすものがある。Pascalでは、数値の加算の他、少なくともこの言語に共通する表現で集合型の和を表わす。C言語では、これがポインタと整数値を結び付けている場合、アドレス操作を表わす。数値的に、さらにマシン命令として、十は整数間と浮動小数点数間ではきわめて異なった操作である。すなわち、整数値操作の結果は、オペランドの順序には依存せず、暗黙的にカッコが付けられているが、浮動小数点数の結果は致命的にその順序に依存している。
struct、union、またはrecord型の構成要素を選択する場合、一般に、選択が行なわれる変数の構造に属する選択枝の名前を必要とする。すなわち、.、^、-> といった演算子は、それらのオペランドの型に対して、より厳密な制限事項がある。C言語は、この点において、意図的に比較的寛容に作られている。

固定した、同一の旬の最大数を数え上げるのは、BNFにおいては扱いにくいテクニックである。BNFはまた、プログラミング言語に通常見られる、次のようないくつかの特徴を扱うこともできない

通常BASICでは、配列は1次元または2次元である。FORTRANのいくつかのバージョンでは、配列を7次元までに制限している。通常コンパイラは、添字として用いられる式の数を制限しなければならない。また、それぞれの配列参照に対して、正しい数の添字が使われているかどうかを検証しなければならない。PascalやC言語では、任意の多次元配列が定義できるが、使われる添字の数は、参照しているデータの型を決定する。
同様な問題が、関数のパラメータにおいても起こってくる。引数の数と型は、組込み関数に対してはあらかじめ定義されており、ユーザ定義関数に対しては定義に従う。Pascalコンパイラは、少なくとも実引数の値が仮引数と合致していることを検証しなければならない。この点に関して、C言語はきわめて寛容にできている。PL/Iコンパイラは、引数変換も行なわなければならない。
引数の受渡しは、別の問題を引き起こす。もし、Pascalに見られるように、サブプログラムの引数が変更されうる場合、それらの引数だけが操作されるということを明確にするように注意しなければならない。FORTRANでは、すべての引数を変更することができるが、結果としては、特定の引数(C言語の感覚で言えばレフト値)だけを変更することができる。これはコード生成の一つの問題である。

多くのセマンティックス上の制限は、定数、型、変数、サブプログラム、およびラベルといったユーザ定義のオブジェクトを扱う。そこで、宣言および定義から得られるすべての情報を入れ、ユーザ定義名称が参照された時はいつでも参照することができるような記号テーブルを必要とする。

いくつかのセマンティックス上の制限が、単純なシンタックス上での解決を拒むという問題を扱う。次のようなことを考えてみよう。

PascalやC言語の。aseに現われる定数は、すべて異なっていなければならない。C言語では、caseおよびdefaultラベルは、一つのswitch句に依存する文の中になければならない。おもしろいことに、この依存する文は複合文である必要はない。
同様に、C言語のbreak文と。ontime文は、期待する飛び越しが意味を持つような場所に置かれなければならない。

これらの制限事項は、特定の構成要素に関連する局所的テストをある程度必要とする。我々のsampleCでは、別々のスタックによって、breakや。continueをどのようにチェックすることができるかを示すようにしている。一般には、ある程度の精巧な仕掛けを必要とするが、それはこれらの問題が、単一的な枠組には合わないからである。

↑

記号テーブルの原理 †

記号テーブルは、コンパイラがユーザの定義した名前や定数に関連するすべての情報を保持する中心地である。記号テーブル・エントリをどのように設計するかは、コンパイラがどのような情報を必要とするかに依存しており、プログラムの宣言部から得ることができる。一方、検索のためのエントリの構成はその言語の可視範囲に影響する。

たとえば、BASICでは一つのテーブルで操作することができ、新たに出現した名前は単にそれに追加するだけで良い。すべての名前は広域的に認識されており、したがって表は、一つのプログラムに対するすべての情報が消されてしまうまで、取り除かれる必要がない。ユーザ定義関数のパラメータは、その関数内でのみ認識される。それらは第二の表に入れられ、その関数に対する仕事が完了してしまえば、すぐに消されてしまう。
FORTRANでは本質的に二つのテーブルを必要とする。一方は、一つのサブプログラムの中に現われたすべての識別子に関する情報を持ち、もう一方は、サブプログラムの名前を記憶する。最初のテーブルは、各サブプログラム単位のコンパイルが終ると消されるかもしれない。サブプログラムがリンカによって結合される場合、二番目のテーブルは必ずしも必要ではない。この場合、サブプログラムの名前はリンカに伝えられる。
Pascalでは、使う前に宣言するという規則と、入れ子になった可視範囲という制限がある。可視範囲が入れ子になっていることから、スタックを一つの記号テーブルとして用いるという結果になる。すなわち、新たな名前はスタックの先頭にプッシュされ、スタックは、可視範囲の最後、すなわち一つのfunctionまたはprocedure定義の最後に到達するとポップされる。名前が参照された時は、スタックを上から検索することにより、その名前のもっとも内側の定義を見つけることができる。
その他のAlgol系言語では、名前はその可視範囲内に宣言が存在する限り、使われる前に宣言されている必要がない。この場合、一つのプログラムに対して二つのパスが必要になろう。最初のパスですべての宣言を集め、それらは可視範囲の最初の部分に伝えられ・二番目のパスでは、最初のパスで集められた情報に基づいて参照の処理を行なう。
C言語では、変数が入れ子になった可視範囲を持つが、関数は入れ子になることができない。また、結果がintになる関数を除いて、使う前に宣言しなければならないという規則がある。一般に、それらの参照が局所的に現われるにしても、関数を広域的なテーブルに入れておく限りは、名前のスタックが必要である。

記号テーブル・エントリにはどのような情報が置かれるのであろうか。後で検索する必要があるので、エントリからユーザ定義の名前に対してアクセスできなければならない。また、使い方を検証するために、オブジェクトの型を表現しておかなければならない。さらに、コード生成の時にオブジェクトの表現方法に関する、スタック上の位置、オフセットまたは絶対アドレス、長さなどの情報を持っていなければならない。

オブジェクトの型を表現するのはむずかしいかもしれない。FORTRANではほんのわずかな型しか存在せず、さらにオブジェクトは一つの配列として次元が与えられているかもしれない。これは、記号テーブルの中で二、三の整数値で表わすことができる。PascalやC言語のような、豊富なデータ型構成要素がある言語では、通常、記号テーブル上で他のエントリヘのポインタになるような、再帰的記述方法を取り入れなければならない。

名前検索は、非常に多くのテクニックが存在する別の領域の問題である、一般に、字句解析を行なう関数が、ユーザ定義の名前やリテラル定数をアセンブルすると、それは直ちに記号テーブルに置かれるか、それがまた未知である場合に記号テーブルに入れられるかである。以降は、記号テーブル・エントリに対するポインタがパスされ、それによりその記号に関する情報へのアクセスが提供されるので。記号テーブルを一回以上検索することを避けることができる。したがって、最初の検索は、字句解析部からだけ呼び出されるルーチンによって行なわれる。この検索をスピードアップするため、記号テーブル自身の他に、八ツシュテーブルのようなデータ構造が用いられるかもしれない。字句解析部が名前検索に非常に多くの処理時間を費すので、テーブル検索を主題とした文献がたくさんある。手始めとして、W、McKeemanによる [Bau76]の3.D章などを参考にするとよい。

↑

コメント †

この記事は、

皆様のご意見、ご希望をお待ちしております。

選択肢	投票
おもしろかった	0
そうでもない	0
わかりずらい	0

Cコンパイラ設計(yacc・lexの応用)/第5章 セマンティックス上の制限事項 のバックアップ(No.2)

第5章 セマンティックス上の制限事項 †

問題点 †

記号テーブルの原理 †

例 †

値スタックの型付け †

問題 †

コメント †

Cコンパイラ設計(yacc・lexの応用)/第5章　セマンティックス上の制限事項のバックアップ(No.2)

第5章　セマンティックス上の制限事項 †