コンパイラ

コンパイラ（英: compiler）は、高水準言語で書かれたコンピュータプログラムを、 コンピュータが実行や解釈できる形式に、一括して（※）変換するソフトウェア。 コンパイラの技術書のバイブルとされるAlfred V.Aho（アルフレッド・エイホ）著 Compilers, Principles, Techniques, and Tools（通称「ドラゴンブック」）の第1章1節の冒頭に、コンパイラとはそもそも何かということについて説明が掲載されており、そこには「簡潔に言うと、コンパイラとは、ある言語（プログラミング言語）で書かれたプログラム（ソースプログラム）を読み、それを別の言語で書かれた等価のプログラム（ターゲットプログラム）へと翻訳（translate）するプログラムである。」と書かれており、さらに続けて「コンパイラは、ソースプログラムに含まれるエラーをユーザに報告するという重要なことを翻訳の1プロセスとして行う。」という説明も加えている。 英語の動詞で、あるプログラム言語で書かれたコードを別の言語で書かれたコードに変換することを"compile"（コンパイル）といい、コンパイラとはその変換を一括して（※ ）行なうコンピュータプログラムのことである。インタプリタとよく対比される。 （なお、上では「ソースプログラム」「ターゲットプログラム」という古典的用語を含む説明文を紹介したが、最近の技術用語では、変換される前のプログラムを「ソースコード」と呼び、変換後の機械語あるいは中間言語のプログラムなどを「オブジェクトコード」と呼ぶ傾向がある。また機械語は二進数で書かれているので近年では「バイナリコード」ということもある。） よくあるのは、高水準言語で書かれたプログラムを、コンピュータのプロセッサが直接実行できる機械語あるいはアセンブリ言語のような低水準言語あるいは元のプログラムよりも"低いレベル"のコード（例えばバイトコードなどの仮想機械向け中間言語あるいは中間表現）に変換するものである。 コンパイラを俯瞰してみると、この世には圧倒されるほど多種類のコンパイラがある。というのは、ソースコード（ソースプログラム）の記述に使われるプログラミング言語だけに着目しても、FORTRANなど歴史の古い言語から始まり近年勃興してきている言語まで含めると数千にもおよぶプログラミング言語があり、他方、オブジェクトコード（ターゲットプログラム）の記述に使われる言語のほうに着目しても、種類がやはり非常に多く、ソースコードの言語とは別の言語であるかも知れないし、（あるいは中間言語であるかも知れないし）、あるいは機械語であるかも知れないからであり、その機械語もマイクロプロセッサを用いたコンピュータのものからスーパーコンピュータのものまであり多種多様だからである。 またコンパイラの種類には、シングルパス（ワンパスとも。1回で変換作業を完了できるもの）、マルチパス（en:Multi-pass compiler。複数回の作業が必要だが、主記憶が少なくても動くもの）、ロード・アンド・ゴー（変換してすぐに実行を開始するもの）、デバッグ用、最適化用などの種類もある。　→#分類の節で説明 またコンパイルを使ったコンパイル作業は、ひとつのプログラムとして動作する全てのコードをいっぺんにコンパイルするのではなく、モジュール毎などに分けてコンパイルし（「分割コンパイル」）、ライブラリなどはあらかじめコンパイルされているものと合わせて、実行するようにすることも多い。この場合、コンパイラはリロケータブルバイナリを出力し、実行可能ファイルの生成にはリンケージエディタが必要であり、さらに動的リンクで実行する場合はダイナミックリンカ／ローダ（ローダの一種）も必要である。 なお、「コンパイラ（言語） / インタプリタ（言語）」という2分法的な分類は、Java登場以前では一般的で適切だったが、近年では適切でないことも増えている。開発環境などでは、コンパイルした後に実行するというような手続きを1コマンドで行えるものも増えている。そして、Java以降はインタプリタでも実行時コンパイラなどの技術の利用がさかんになってきており、古典的な意味での「コンパイラ」と「インタプリタ」の中間的な性質のツール（プログラム）も増えてきているからである。 なお英語の「compile」はもともと「編集する」「編纂する」という意味の英語であり、「compiler」というのは「編集者」という意味の英語である。 1940年代まで、コンピュータのプログラミングは機械語で直接行なわれていた。プログラムを指して「コード」（英語では暗号を意味する）と呼ぶのは、知らない人間には機械語は全く意味のわからない数値の羅列だからである。しかし、（人間にとって比較的理解のしやすい）十進法の数字で書かれたアドレスを内部表現の二進法に変換する、といったプログラムならばEDSAC（1940年代末に登場した、イギリスのマシン）において既に存在していた。（つまり、この段階で、アセンブラのごく一部の機能に限れば、実現していたことになる） 機械語でのプログラミングは言うに及ばず、アセンブリ言語を用いても、プログラミングというのは面倒な作業である。そういった低水準言語から、人間がより扱いやすい高水準言語が徐々に求められるようになった。また、機械の詳細が抽象化されることにより、高水準なプログラミング言語で書かれた同一のソースコードを元に、詳細仕様が異なる機械でも動くプログラムを生成できる、という利点もあった。1950年代末までに、プログラミング言語がいくつか提案され、実験的なコンパイラがいくつか開発された。 世界初のコンパイラについては、1952年にグレース・ホッパーが書いたA-0 Systemだとされることもある。だが一般的には1957年にIBMのジョン・バッカスのチームが開発したFORTRANコンパイラが世界初の完全なコンパイラであるとされている。一般的なコンパイラの開発では、まず動くものを作ってから最適化の機能が付け加えられるが、最初のFORTRANコンパイラでは、コンパイラが実用になることを示すために、最初から最適化に労力が向けられた。 1960年の、ホッパーらによるCOBOLは複数のアーキテクチャ上でコンパイル可能となった言語の最初期の1つである。 様々なアプリケーション領域で、高水準言語というアイデアは素早く浸透していった。機能が拡張されたプログラミング言語が次々と提案され、コンピュータのアーキテクチャそのものも複雑化していったため、コンパイラはどんどん複雑化していった。 初期のコンパイラはアセンブリ言語で書かれていた。世界初の「セルフホスティングコンパイラ」は、1962年にマサチューセッツ工科大学の Hart と Levin が開発したLISPである。1970年代には、特にPascalやC言語などにおいて、コンパイル対象言語でコンパイラを書くことが一般化した。さらにより高水準の言語のコンパイラは、PascalやC言語で実装することも多い。セルフホスティング・コンパイラの構築には、ブートストラップ問題がつきまとう。すなわち、コンパイル対象言語で書かれたコンパイラを最初にコンパイルするには、別の言語で書かれたコンパイラが必要になる。Hart と Levin の LISPコンパイラではコンパイラをインタプリタ上で動作させてコンパイルを行なった。 機械語にコンパイルするコンパイラもあれば、そうでないコンパイラ（後述）もある。機械語コードのことを、ハードウェアであるプロセッサの生のコード、というような意味でネイティブコードなどと言うことがあり、機械語にコンパイルするコンパイラのことをネイティブコンパイラと言うことがある。 コンパイラに限らず、入力と出力を持つあらゆる変換系は、入力の種類がm種類、出力の種類がn種類あるとすると、m×n種類があることになる。コンパイラの場合、プログラミング言語がm種類、コード生成の対象となる命令セットアーキテクチャがn種類、といったような感じになるわけであり、入力側をフロントエンド、出力側をバックエンドと言うが、中間表現の設計いかんでは、残りの中間処理の部分、特に重要な部分であるコンパイラ最適化を共有できるため、1980年代以降に基本設計が為されたGCCやCOINSやLLVMなどでは、そのようにして多言語・多ターゲットに対応している。 汎用OSなど、開発環境と同じ環境で目的プログラムも動作させるような開発を「セルフ開発」と言い、セルフ開発のコンパイラを「セルフコンパイラ」という。それに対し、開発環境とは別の環境で実行するような開発を「クロス開発」といい、そのためのコンパイラをクロスコンパイラという。OSカーネル自身のコンパイルなどは、カーネル自身の実行環境は、そのOSではなくベアメタルであるという意味ではある種のクロスコンパイルのようなものであるし、新しいコンピュータシステムのための環境を最初に作るにはクロス開発の必要がある。あるいは、組み込みシステムやPDAなど、それ自体が開発環境を動作させるだけの機能や性能を持たない場合、といったものもある。 いわゆるネイティブコードではなく中間コードを生成し、さらに別のコンパイラに処理を任せたり、別のインタプリタによって実行したりするものもある。これを中間コードコンパイラ、バイトコードコンパイラなどと呼ぶ。またそのバイトコードを解釈実行する処理系をバイトコードインタプリタなどと呼ぶ。 コンパイラは様々な処理の集合体であり、初期のコンピュータではメモリ容量が不十分であったため、一度に全ての処理を行うことができなかった。このためコンパイラを複数に分割し、ソースコードや何らかの中間的な表現に何度も処理を施すことで解析や変換を行っていた。 一回でコンパイルが可能なものをワンパスコンパイラと呼び、一般にマルチパスコンパイラよりも高速で扱いやすい。Pascalなど、多くの言語はワンパスでコンパイルできるよう意図して設計されている。 言語の設計によっては、コンパイラがソースコードを複数回読み込む必要がある。たとえば、20行目に出現する宣言文が10行目の文の変換に影響を与える場合がある。この場合、一回目のパス（読み込み）で影響を受ける文の後にある宣言に関する情報を集め、二回目のパスで実際の変換を行う。 ワンパスの欠点は、高品質のコードに欠かせない最適化を行いにくいという点が挙げられる。最適化コンパイラが何回読み込みを行うかというのは決まっていないが、最適化の各フェーズで同じ式や文を何度も解析することもあるし、一回しか解析しない箇所もある。 コンパイラを小さなプログラムに分割する手法は、研究レベルでよく行われる。プログラムの正当性の判定は、対象プログラムが小さいほど簡単なためである。 ネイティブコンパイラの他にも以下のような、「ネイティブの機械語」以外をターゲットとするコンパイラ（ないしトランスレータ）がある。 何らかの高水準言語から、何らかの高水準言語に変換する「トランスレータ」。「トランスコンパイラ」などという語もある。たとえば、OpenMPなどの自動並列化コンパイラは並列化が明示されていないプログラムを、並列化を明示したプログラムに変換する。または、FORTRANの DOALL 文など何らかの言語構文を変換する。 ステージコンパイラ（Stage Compiler）は何らかの理論上のマシンのアセンブリ言語を出力する。たとえば、一部のPrologでそのような実装がなされている。[要出典]Java や Python のバイトコードコンパイラもステージコンパイラの一種と言える。 Java や Smalltalk やマイクロソフトの共通中間言語システムで使われているJITコンパイラ。コンパイラはいったん中間表現を生成し、実行時に中間表現がターゲットの機械語にコンパイルされる。 もっぱらその言語の処理系がコンパイラとして実装される言語を「コンパイラ言語」などと言い、インタプリタとして実装される言語を「インタプリタ言語」などと言うこともあるが、実験的な実装まで含めればどちらもある言語も多い。Microsoft Visual Studioに付属するF#/C# Interactiveのように、対話環境で入力したプログラムを、コンパイラで共通中間言語（中間表現）にコンパイルし、さらに共通言語ランタイム（仮想機械）上でネイティブコードにJITコンパイルしてインタプリタ的に実行する、というような処理系もある。JavaやMicrosoft Visual Basicのように、登場当初はインタプリタ方式だったが、のちにネイティブコードへのJITコンパイルやAOTコンパイルをサポートするようになった言語もある。 Common Lispなど言語によっては、実装にコンパイル機能を含むことを義務とする仕様もある(ただし、Common Lisp仕様は解釈実行の処理系を禁止しているのではない)。また、インタプリタの実装が容易でコンパイラの実装が困難な言語もある（APL、SNOBOL4など）。メタプログラミングの利用、特に文字列をevalすることは、インタプリタ方式では造作ないことだが、コンパイラ方式では実行環境にコンパイラ自体が必要となる（動的プログラミング言語も参照）。 ハードウェア記述言語の処理系（合成系）を、ハードウェアコンパイラとかシリコンコンパイラなどと呼ぶことがある。 コンパイルをアプリケーションの実行時に行うか、実行前に行うかで2つに分かれる。 事前コンパイラ - 実行前に事前にコンパイルする。Ahead-Of-Timeコンパイラ (AOTコンパイラ)。 実行時コンパイラ - 実行時にコンパイルする。Just-In-Timeコンパイラ (JITコンパイラ)。 コンパイラ構築とコンパイラ最適化は、大学での計算機科学や情報工学のカリキュラムの一部となっている。そのようなコースでは適当な言語のコンパイラを実際に作らせることが多い。文書が豊富な例としてはニクラウス・ヴィルトが1970年代に教育用に設計し、教科書中で示した PL/0 がある。PL/0 は単純だが、教育目的にかなった基本が学べるようになっている。PL/0 はPascalで書かれていた。ヴィルトによる教科書は何度か改訂されており、1996年の版ではOberonでOberonのサブセットOberon-0を実装している。 段階的改良によるプログラム開発の採用 再帰下降構文解析の採用 拡張BNF記法による文法記述の採用 Pコードの採用 ブートストラップ問題をT図式（en:Tombstone diagram）で形式的に記述 もともとは、コンパイラはしばしばインタプリタと対比されてきたものである。コンパイラは、生成された機械語プログラムなどの実行は行わないが、一度コンパイルすればコンパイラを使わずに何度も実行できるという利点がある。しかし、インタプリタは、バイナリの実行ファイルは生成せず、実行するときに常に必要だが、プログラムを作ったらすぐに実行できるという利点がある。 コンパイラは、概念的に言うと、一般に次のようなフェーズ（phase(s)、段階）に従い処理を行う。 通常、次のような入・出力図で説明される。 ソースプログラム（ソースコード） ↓ 字句解析器 ↓ 構文解析器 ↓ セマンティック解析器 ↓ 中間コード生成器 ↓ コード最適化器 ↓ コード生成器 ↓ ターゲットプログラム（オブジェクトコード） 太字で表記したものがコンパイラの中に含まれている部分（コンパイラの部品）である。つまり、まず字句解析器（字句解析部）がソースコードを読み込みトークンに分解し、次に構文解析器（構文解析部）がトークン列からプログラムの構文木を構築し、次にセマンティック解析器（意味解析器）が意味論的な解析を行い、次に中間コード作成器が中間コードを生成し、次に最適化器がコードの最適化を行い、最後にコード生成器が最終的なターゲットプログラム（オブジェクトコード）を生成する。 なお、コンパイラの作成に関することだが、字句規則から字句解析器を生成するlex、構文規則から構文解析器を生成するパーサジェネレータというプログラムがあり、広く実用的に使われている。つまりコンパイラのプログラムの一部分を自動的に書いてくれるようなプログラムがすでにあり、それのおかげで全部人力で書くようなことはしないで済む。（なお、コンパイラ全体を生成するコンパイラジェネレータも研究されているものの、広く実用に使われるには至っていない。） コンパイラ設計手法は処理の複雑さ、設計者の経験、利用可能なリソース（人間やツール）に影響される。 コンパイル処理の分割を採用したのはカーネギーメロン大学での Production Quality Compiler-Compiler Project であった。このプロジェクトでは、「フロントエンド」、「ミドルエンド」（今日では滅多に使われない）、「バックエンド」という用語が生み出された。 非常に小さなコンパイラ以外、今日では2段階（2フェーズ）以上に分割されている。しかし、どういったフェーズ分けをしようとも、それらフェーズはフロントエンドかバックエンドの一部と見なすことができる。フロントエンドとバックエンドの分割点はどこかというのは論争の種にもなっている。フロントエンドでは主に文法的な処理と意味論的な処理が行われ、ソースコードよりも低レベルな表現に変換する処理が行われる。 ミドルエンドはソースコードでも機械語でもない形式に対して最適化を施すフェーズとされる。ソースコードや機械語と独立しているため、汎用的な最適化が可能とされ、各種言語や各種プロセッサに共通の処理を行う。 バックエンドはミドルエンドの結果を受けて処理を行う。ここでさらなる解析・変換・最適化を特定のプラットフォーム向けに行う場合もある。そして、特定のプロセッサやOS向けにコードを生成する。 このフロントエンド/ミドルエンド/バックエンドという分割法を採用することにより、異なるプログラミング言語向けのフロントエンドを結合したり、異なるCPU向けのバックエンドを結合したりできる。この手法の具体例としてはGNUコンパイラコレクションや Amsterdam Compiler Kit、LLVM がある。これらは複数のフロントエンドと複数のバックエンドがあり、解析部を共有している。 フロントエンドはソースコードを分析して、中間表現または IR と呼ばれるプログラムの内部表現を構築する。また、シンボルテーブルを管理し、ソースコード内の各シンボルに対応したデータ構造に位置情報、型情報、スコープなどの情報を格納する。このような処理はいくつかのフェーズで実施される。たとえば以下のようなフェーズがある。 行再構築(Line reconstruction) - キーワードにストロッピング（英語版）を施す場合や識別子に空白を挿入可能な場合、字句解析の前に入力文字列を「正規化」する必要がある。1960年代の一般的なトップダウンの再帰下降型の表駆動構文解析では、ソースコードを一度読み込むだけでトークン化のフェーズは不要だった。ストロッピングを行う言語としては、Atlas Autocode（英語版）、Edinburgh IMP（英語版）、一部のALGOL処理系などがあり、これらは「行再構築」フェーズを持っている。ストロッピングとは、キーワードに何らかの記号をつけることでキーワードとして使われている文字列を予約語とせず、同じ文字列を変数名やサブルーチン名に利用できるようにしたものである。たとえば、シングルクオートでキーワードを囲むとか、%記号を先頭につけるなどの記法がある。 字句解析 - ソースコードの文字列を、「トークン」と呼ばれる、言語的に意味のある最小単位に分割する。各トークンは最小構成要素であり、たとえばキーワード、識別子、シンボル名、「10」や「365」のような数、などである。トークンは一般に正規言語に従うため、正規表現を解釈する有限オートマトンで認識できる。字句解析を行うソフトウェアを字句解析器（lexical analyzer）と呼ぶ。 プリプロセッサ - コンパイル前の全処理を行うもの。マクロを実装や、定数の定義、ヘッダファイルの読み込みに使われる。一般にこのフェーズは構文解析や意味解析の前に行われる。プリプロセッサはトークンを操作するものであって、構文を考慮しない。だから、C言語などでは、プリプロセッサでマクロを実装できるが、LISPのような言語では構文解析後にマクロを置き換える必要があり、プリプロセッサは使われない。 構文解析 - トークン列を解析し、プログラムの構造を明らかにする。このフェーズで構文木が構築され、単なるトークンの列だったプログラムにその言語の文法を定義した形式文法の規則を適用することで木構造を生成する。構文木は、この後の工程で解析され、強化され、変換される。 意味解析（英語版） - 構文木の要素に意味を追加し、シンボルテーブルを作成する。型チェック（データ型などを間違っていないかのチェック）や、変数や関数の定義と参照箇所を結びつける処理、既定値代入（自動変数の初期化）、意味的に不正なプログラムを検出して通知するなどの処理が行われる。意味解析には完全な構文木が必要であり、理論上構文解析とコード生成の間に行わなければならない。もちろんコンパイラの実装によってはこれらを一度に行うこともある。 「バックエンド」という用語は「コード生成」という用語と混同されることが多い。アセンブリ言語コードを生成するという意味で機能的にも類似しているためである。書籍によっては、バックエンドの汎用解析フェーズと最適化フェーズを「ミドルエンド」と称してマシン依存のコード生成部と区別することがある。 バックエンドに含まれる主なフェーズは以下の通りである。 解析部 - 入力から生成された中間表現を使って各種情報を収集する。主な解析としてUD連鎖を構築するデータフロー解析、依存関係解析、エイリアス解析、ポインタ解析、エスケープ解析などがある。正確な解析によってコンパイラ最適化が可能となる。また、コールグラフや制御フローグラフがここで作られることが多い。 最適化 - 中間表現を機能的には等価だがより「ベター」な形式に変換する。主な最適化手法としてインライン展開、デッドコード削除、定数伝播、ループ変換、レジスタ割り当て、自動並列化などがある。 コード生成 - 実際に出力する機械語やバイトコードを生成する。ここでリソースや記憶装置の割り当てが決定される。たとえば、どの変数をレジスタに格納し、どの変数をメモリに格納するか、どの命令をどういう順番で実行するかをアドレッシングモードなどをセシィ-ウルマン法などを用いて決定する。 コンパイラ解析とは、コンパイラ最適化の前に行われる処理で、両者は密接な関係がある。たとえば依存関係解析はループ変換実施に重要な意味を持つ。 さらに、コンパイラ解析と最適化の範囲は様々であり、基本的なブロック単位の場合からプロシージャや関数レベル、さらにはプロシージャの垣根を超えてプログラム全体を対象とすることもある。広範囲を考慮するコンパイラほど最適化に用いることができる「ヒント」が増え、結果としてより良いコードを生成する可能性がある。しかし、広範囲を考慮する解析や最適化はコンパイル時間やメモリ消費のコストが大きい。これは特にプロシージャ間の解析や最適化を行う場合に顕著である。 最近の商用コンパイラはプロシージャ間解析/最適化を備えているのが普通である（IBM、SGI、インテル、マイクロソフト、サン・マイクロシステムズなど）。オープンソースのGCCはプロシージャ間最適化を持たない点が弱点だったが、これも改善されつつある。他のオープンソースのコンパイラで完全な最適化を行うものとしてOpen64がある。 コンパイラ解析と最適化には時間と空間が必要となるため、コンパイラによってはデフォルトでこれらのフェーズを省略するものもある。この場合、ユーザーはオプションを指定して明示的に最適化を指示しなければならない。 以下のプログラムは中置記法で入力された四則演算を逆ポーランド記法を経て、独自の中間表現にコンパイルするC言語で書かれた非常に単純なワンパス・コンパイラである。このコンパイラは中置記法を逆ポーランド記法にコンパイルすると共に、ある種のアセンブリ言語にもコンパイルする。再帰下降型の戦略を採用している。このため、各関数が文法における各非終端記号に対応している。 #include <stdlib.h> #include <stdio.h> #include <string.h> #define MODE_POSTFIX 0 #define MODE_ASSEMBLY 1 char lookahead; int pos; int compile_mode; char expression[20+1]; void error() { printf("Syntax error!\n"); } void match( char t ) { if( lookahead == t ) { pos++; lookahead = expression[pos]; } else error(); } void digit() { switch( lookahead ) { case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': if( compile_mode == MODE_POSTFIX ) printf("%c", lookahead); else printf("\tPUSH %c\n", lookahead); match( lookahead ); break; default: error(); break; } } void term() { digit(); while(1) { switch( lookahead ) { case '*': match('*'); digit(); printf( "%s", compile_mode == MODE_POSTFIX ? "*" : "\tPOP B\n\tPOP A\n\tMUL A, B\n\tPUSH A\n"); break; case '/': match('/'); digit(); printf( "%s", compile_mode == MODE_POSTFIX ? "/" : "\tPOP B\n\tPOP A\n\tDIV A, B\n\tPUSH A\n"); break; default: return; } } } void expr() { term(); while(1) { switch( lookahead ) { case '+': match('+'); term(); printf( "%s", compile_mode == MODE_POSTFIX ? "+" : "\tPOP B\n\tPOP A\n\tADD A, B\n\tPUSH A\n"); break; case '-': match('-'); term(); printf( "%s", compile_mode == MODE_POSTFIX ? "-" : "\tPOP B\n\tPOP A\n\tSUB A, B\n\tPUSH A\n"); break; default: return; } } } int main ( int argc, char** argv ) { printf("Please enter an infix-notated expression with single digits:\n\n\t"); scanf("%20s", expression); printf("\nCompiling to postfix-notated expression:\n\n\t"); compile_mode = MODE_POSTFIX; pos = 0; lookahead = *expression; expr(); printf("\n\nCompiling to assembly-notated machine code:\n\n"); compile_mode = MODE_ASSEMBLY; pos = 0; lookahead = *expression; expr(); return 0; } この単純なコンパイラの実行例を以下に示す。 Please enter an infix-notated expression with single digits: 3-4*2+2 Compiling to postfix-notated expression: 342*-2+ Compiling to assembly-notated machine code: PUSH 3 PUSH 4 PUSH 2 POP B POP A MUL A, B PUSH A POP B POP A SUB A, B PUSH A PUSH 2 POP B POP A ADD A, B PUSH A