FrontPage

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

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

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

問題点

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

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

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

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

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

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

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

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

記号テーブルの原理

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

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

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

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

値スタックの型付け

問題

コメント

この記事は、

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

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



トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
SmartDoc