- 追加された行はこの色です。
- 削除された行はこの色です。
[[FrontPage]]
#freeze
削除しました（removed）
2008/05/16からのアクセス回数 &counter;
#contents
* 第5章 セマンティックス上の制限事項 [#efa48711]
かたくるしい言語認識の一般的問題から、プログラム・テキストを解析し翻訳した実行可能
なものを生成する、という明確な問題に移ることにしよう。したがってここでは、文章の代わ
りにプログラムという言葉を用いることにする。これは、終端記号の列として定義され、ある
文法に対応した唯一のパーズ・トリーが構成できるもののことである。この章でプログラムに
どのような付加制限を加えるかを扱って、コンパイラの解析部の設計を完了する。以下の章で
は、プログラムによって記述されたアルゴリズムの実行可能バージョンの合成について述べる。
** 問題点 [#ea4b7d8b]
プログラムは構文的に正しくても、意味的な誤りを含むことがある。典型的な例として、次
のようなものが挙げられる。
- 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をどのようにチェックするこ
とができるかを示すようにしている。一般には、ある程度の精巧な仕掛けを必要とするが、そ
れはこれらの問題が、単一的な枠組には合わないからである。
** 記号テーブルの原理 [#c8d1a75e]
記号テーブルは、コンパイラがユーザの定義した名前や定数に関連するすべての情報を保持
する中心地である。記号テーブル・エントリをどのように設計するかは、コンパイラがどのよ
うな情報を必要とするかに依存しており、プログラムの宣言部から得ることができる。一方、
検索のためのエントリの構成はその言語の可視範囲に影響する。
- たとえば、BASICでは一つのテーブルで操作することができ、新たに出現した名前は単に
それに追加するだけで良い。すべての名前は広域的に認識されており、したがって表は、
一つのプログラムに対するすべての情報が消されてしまうまで、取り除かれる必要がない。
ユーザ定義関数のパラメータは、その関数内でのみ認識される。それらは第二の表に入れ
られ、その関数に対する仕事が完了してしまえば、すぐに消されてしまう。
- FORTRANでは本質的に二つのテーブルを必要とする。一方は、一つのサブプログラム
の中に現われたすべての識別子に関する情報を持ち、もう一方は、サブプログラムの名前
を記憶する。最初のテーブルは、各サブプログラム単位のコンパイルが終ると消されるか
もしれない。サブプログラムがリンカによって結合される場合、二番目のテーブルは必ず
しも必要ではない。この場合、サブプログラムの名前はリンカに伝えられる。
- Pascalでは、使う前に宣言するという規則と、入れ子になった可視範囲という制限があ
る。可視範囲が入れ子になっていることから、スタックを一つの記号テーブルとして用い
るという結果になる。すなわち、新たな名前はスタックの先頭にプッシュされ、スタック
は、可視範囲の最後、すなわち一つのfunctionまたはprocedure定義の最後に到達すると
ポップされる。名前が参照された時は、スタックを上から検索することにより、その名前
のもっとも内側の定義を見つけることができる。
- その他のAlgol系言語では、名前はその可視範囲内に宣言が存在する限り、使われる前に
宣言されている必要がない。この場合、一つのプログラムに対して二つのパスが必要にな
ろう。最初のパスですべての宣言を集め、それらは可視範囲の最初の部分に伝えられ・二
番目のパスでは、最初のパスで集められた情報に基づいて参照の処理を行なう。
- C言語では、変数が入れ子になった可視範囲を持つが、関数は入れ子になることができな
い。また、結果がintになる関数を除いて、使う前に宣言しなければならないという規則が
ある。一般に、それらの参照が局所的に現われるにしても、関数を広域的なテーブルに入
れておく限りは、名前のスタックが必要である。
記号テーブル・エントリにはどのような情報が置かれるのであろうか。後で検索する必要が
あるので、エントリからユーザ定義の名前に対してアクセスできなければならない。また、使い
方を検証するために、オブジェクトの型を表現しておかなければならない。さらに、コード生
成の時にオブジェクトの表現方法に関する、スタック上の位置、オフセットまたは絶対アドレ
ス、長さなどの情報を持っていなければならない。
オブジェクトの型を表現するのはむずかしいかもしれない。FORTRANではほんのわずか
な型しか存在せず、さらにオブジェクトは一つの配列として次元が与えられているかもしれな
い。これは、記号テーブルの中で二、三の整数値で表わすことができる。PascalやC言語のよ
うな、豊富なデータ型構成要素がある言語では、通常、記号テーブル上で他のエントリヘのポ
インタになるような、再帰的記述方法を取り入れなければならない。
名前検索は、非常に多くのテクニックが存在する別の領域の問題である、一般に、字句解析
を行なう関数が、ユーザ定義の名前やリテラル定数をアセンブルすると、それは直ちに記号テ
ーブルに置かれるか、それがまた未知である場合に記号テーブルに入れられるかである。以降
は、記号テーブル・エントリに対するポインタがパスされ、それによりその記号に関する情報
へのアクセスが提供されるので。記号テーブルを一回以上検索することを避けることができる。
したがって、最初の検索は、字句解析部からだけ呼び出されるルーチンによって行なわれる。
この検索をスピードアップするため、記号テーブル自身の他に、八ツシュテーブルのようなデ
ータ構造が用いられるかもしれない。字句解析部が名前検索に非常に多くの処理時間を費すの
で、テーブル検索を主題とした文献がたくさんある。手始めとして、W、McKeemanによる
[Bau76]の3.D章などを参考にするとよい。
** 例 [#j950bb98]
** 値スタックの型付け [#rc80a47e]
** 問題 [#o4a8f351]
** コメント [#h71ae5f3]
この記事は、
#vote(おもしろかった,そうでもない,わかりずらい)
皆様のご意見、ご希望をお待ちしております。
#comment
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
