このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

コンパイラ

 コンピュータが仕事を行うには、プログラムが必要であり、このプログラムは基本的にC,C++,Javaなどといった高級言語を用いて記述されている。この高級言語で書かれたプログラムは直接コンピュータが理解して実行することはできないので、何らかの解釈システム(翻訳システム)が必要となる。この解釈システムに当たるのがコンパイラ(compiler)である。

 コンパイラは高級言語で書かれたプログラムを入力として受け取り、コンピュータが直接理解できる機械語プログラムへ翻訳(この作業をコンパイルという)する。ここで、入力されるプログラムを原始プログラムまたはソースプログラム(単にソースと略される場合もある)、出力されるプログラムを目的プログラムまたはオブジェクトプログラムという。

 コンパイラでコンパイルされた目的プログラムは主記憶にロードされて、そこで実行される。

 一方、目的プログラムを生成せず、直接コンパイル後コンピュータが実行するシステムも存在する。このようなシステムをインタプリタ(interpreter)と呼ぶ。インタプリタ型プログラミング言語として、Perl,BASIC,Lispなどがある。

 このインタプリタ型はコンパイル型と比べて実行速度は遅いという欠点を持つが、作成が容易という利点も持つ。さらに、原始プログラムがそのまま(あるいはそれに近い形で)保持されているので、プログラムの変更と実行を交互に繰り返すことができる。これはプログラム作成の際、非常に楽できることを意味する。

 さらに、コンパイラとインタプリタの中間に位置する特殊なシステムも存在する。これは仮想的なコンピュータの機械語を中間コードというが、このシステムは中間コードに高級言語のプログラムを変換してから、次に変換された中間コードを解釈実行するのである。

 以上で、コンパイラ型・インタプリタ型・中間型の3つ紹介した。これらをまとめて、言語処理系(language processor)と呼ぶ。

変換系

 言語処理系をさらに一般化すると、ある言語(L1)で書かれたプログラムを他の言語(L2)のプログラムへ変換するシステムを考えることができる。このシステムを変換系(translator)と呼ぶ。

T-図形

 言語Mで書かれた変換系が言語L1のプログラムを言語L2のプログラムに変換するとき、次のような図形で表される。この図形をT-図形という。このとき、L1が原始言語、L2が目的言語、Mが記述言語に当たる。

例1:L1をFortran、L2を機械語とするとその変換系はFortranコンパイラに他ならない。

例2:Javaプログラムは、通常Javacと呼ばれるコンパイラでバイトコードBCと呼ばれる中間言語に変換された後、Java VM(Java Virtual Machine)と呼ぶインタプリタで解釈実行される。Javac自身はBCで書かれている。

T-図形の特徴

 T-図形を使って表現することは次のような解釈(変換過程という)を行えることを直感的に理解できる点でも優れている。

 これはまず、Cで記述されたBコンパイラ、Cコンパイラ、Bコンパイラを用意して、Cで記述されたBコンパイラを入力として、Cコンパイラに施し、その結果Bコンパイラが出力されていることを意味している。これら3つをまとめると次のようにひとつに書ける。

 また、Bコンパイラを作成するには、次のアセンブラと変換系をコンパイルしたものを考えればよい。関数で言うならば、合成関数のように考えると良い。

アセンブラ(Aがアセンブリ言語、Mが機械語)

変換系

Bコンパイラ

 これと次のものは同値である。

Bコンパイラとの同値

コンパイラとプログラミング言語

 プログラミング言語を大別すると代入操作を基本とする手続き型言語とそれ以外の言語に分けることができる。

 前者の例としてFortran,PL/I,Pascal,C,Algolなど、後者の例としてLisp(関数定義と式の評価を基本とする関数型言語),Prolog(項の単一化を基本操作とする論理型言語),Smalltalk(オブジェクトにメッセージを送る操作を基本とするオブジェクト指向言語)などがある。

 プログラミング言語とコンパイラの関係は次の通りである。

  • 言語が異なれば、当然コンパイラも異なる。
  • 同一言語であっても、使用するコンピュータが異なれば、コンパイラも異なる。
  • 同一言語かつ同一コンピュータであっても、実行効率に重点をおくのかコンパイル速度に重点をおくのかによって、コンパイラも異なる。

 しかしながら、これらコンパイラの間にも共通項が存在し、これら共通の枠組みの基礎としてコンパイラの理論がある。特に、コンパイラの前半部(字句解析、構文解析)については理論的によく研究されており、ほとんど全ての言語に適応できる枠組みが得られている。なぜならば、ほとんどの言語がその構文記述において、BNF(Backus Naur(normal) form)が採用されていて、このBNFで記述された構文の解析法がすでに確立しているからである。同様にコンパイラの後半部に当たる目的コード生成においても、種々の計算機に対しても適応可能な一般的な方法が考案されている。

コンパイラとプログラミング言語の意味

 プログラム言語の構文は前述した通り、BNFを用いて形式的に定義されるので、プログラムが文法的に正しいかどうかの検査は容易にできる。

 一方、プログラミング言語の意味はこれまで自然言語などで非形式的に説明される場合が多く、意味のあいまいな部分がどうしても残るという問題点があった。このような意味不明な部分はコンパイルして実行結果を調べることによって、あるいはコンパイラ自身を解析することによって明らかにされるが、プログラミング言語の正確な意味を理解するにはコンパイラを直接的あるいは間接的に使用しなければならない。

 プログラミング言語の意味が形式的に与えられれば、コンパイラの正当性についても形式的に議論ができる。次の写像が成り立つとき、Compilerは正当であると定義できる。

\phi~\circ~\,~Compiler~=~\epsilon~~\circ~\theta ←(*)

コンパイラの正当性

[補講]符号化ε:DL→DTはあらかじめ与えられていると仮定してもよいが、より一般的に(*)を満たすような符号化ε:DL→DTを構成することによって、Compilerの正当性が証明される。

 以上のことから、プログラミング言語の意味を与えることとコンパイラ作成には密接な関係があることがわかった。

コンパイラの構造

 コンパイラは論理的に見るとフェーズ(phase)と呼ばれるいくつかの部分システムに分けられ、これらが次のように直列接続したものと見ることができる。

 上の直列接続において、矢印の下にあるのがフェーズに当たる。

字句解析系(lexical analyzer)

 ユーザーのプログラムを文法上の基本単位であるトークン(token)の列に変換する。このトークンは予約語、ラベル、識別子、特殊記号、数などから成る。

構文解析系(syntax analyzer)

 トークン列はこのフェーズでプログラミング言語の文法(構文)規則にしがって、より抽象度の高いレベルにまとめられて、構文木が構成される。

中間コード生成系(intermediate code generator)

 構文解析系の出力である解析木を入力として受け取り、出力としてアセンブリ(機械)コードを抽象化した命令である中間コードの列を生成する。このフェーズは目的(機械)コード生成部を2段階に分けた前段階に当たり、種々の計算機の機械語から独立した部分である。よって、異なった計算機に対しては同一のものでよい。

コード最適化(code optimization)

 中間コード列を入力として受け取り、より実行効率のよい、あるいは所有記憶量のより小さい等価な中間コード列に変換する。このよりよいプログラムの生成は最適化と呼ばれるが、これは文字通りの意味とは異なることに注意して欲しい。なぜならば、計算可能性の理論からわかるように、最適なプログラムを得る一般的なアルゴリズムは存在しないからである。

 このコード最適化は中間コードと目的コードの両方に対して行われる。

 コンパイラで行われるコード最適化では次のような最適化が実行される。

  • 畳込み
    • 定数の計算をコンパイル時に行う。
  • 関数のインライン展開
    • 手続きや関数を呼び出す代わりに、その手続きや関数を呼び出す場所に直接埋め込むことによって、呼び出しと復帰に要するコストを低減させる。
    • 最適化後にコードサイズが大きくなる。
  • ループ内不変式の移動
    • 不変式(値が変化しない式)がループ内にあるとき、これをループの外に移動してループ本体の命令数を減らす。
    • 最適化後のコードサイズは変わらない。
  • ループのアンローリング
    • コンパイル時に回数が特定できる単純な繰り返し処理を、繰り返しをしないコードに展開する。
    • 最適化後にコードサイズが大きくなる。
  • レジスタへの変数割付け
    • 変数がレジスタに割付けられる機会を増加させることにより、ロードやストア命令の回数を減らす。
    • 最適化後にコードサイズが減る。

[補講]「レジスタへの変数割付け」は、最適化後にコードサイズが減らすとともに、実行速度の最適化も行われる。

コード生成系(code generator)

 中間コードから機械(またはアセンブリ)コードへの変換が行われる。このフェーズでは効率よく計算を行うためのレジスタ割付け、命令コードの選択などが行われる。

[補講]コンパイラの理論的構造はこのような直列接続のようにみることができるが、物理的な実現レベルでは必ずしも順序的とは限らない。例えば、構文解析系がトークンを必要とするごとに字句解析系を呼び出すというように、これらが並行して動作する場合がある。

コンパイルと形式言語理論

1:原始プログラムは、まず文脈自由文法に基づいた字句解析によってトークン列に切り分けられる。

2:次いで、文脈依存文法に基づいた構文解析によって、解析木に変換される。

[補講]理論的には、文脈自由文法は文脈依存文法の特別な場合なので、これらをまとめて行うことも可能であるが、解析を容易にし、効率を上げるために、別々にこの順序で行うことが一般的である。

パスについて

 原始プログラムのある表現を先頭から順に1度読み込んで処理を行う部分をパス(pass)という。

 コンパイラの物理レベルでは幾つかのフェーズがひとつのパスにまとめれる。例えば、字句解析フェーズと構文解析フェーズはひとつのパスにまとめることができる。原始プログラムを1回読み込んで目的プログラムを出力する。このようにひとつのパスだけから成るコンパイラをワンパスコンパイラ(one-pass compiler)と呼び、そうでないものを多パスコンパイラと呼ぶ。ワンパスコンパイラは早くコンパイルすることに重点を置いたコンパイラ作成に適している。

参考文献

  • 『図解雑学 コンピュータ科学の基礎』
  • 『コンピュータ数学シリーズ10 コンパイラの理論』
  • 『ソフトウェア開発技術者試験対策 コンピュータサイエンス補足資料+午後演習問題』