コンパイラ

テンプレート:Otheruseslist コンパイラ（compiler）とは、プログラミング言語で書かれた、プログラムのソースコード（原始コード）を、機械語、ないしバイトコードなどの中間言語によるオブジェクトコード（目的コード）に翻訳(変換)するプログラムである。コンパイラによる翻訳(変換)工程をコンパイル(翻訳)と呼ぶ（ビルドと呼んでいるツール等もある。厳密にはコンパイルはビルドの一工程である）。直接バイナリを出力するものもあるが、コンパイラ自身はアセンブリ言語によるコード（アセンブリソース）を出力し、さらにアセンブラを呼んでいるものも多い。コンパイラー(Compiler)という名称は日本語では、翻訳者という意味を持ち、ソフトウェアとしてのコンパイラーは翻訳機という意味を持っている。

一般に、コンパイル結果のプログラムの実行速度は、インタプリタを介した実行より高速である。一方、ソースコードの修正から実行までにコンパイルの時間を要するため、開発時など、修正と動作テストを繰り返す場合などでは作業性が悪い。

近年のコンパイラでは、ひとつのプログラムとして動作する全てのコードをいっぺんにコンパイルするのではなく、モジュール毎などに分けてコンパイルし（分割コンパイル）、ライブラリなどはあらかじめコンパイルされているものと合わせて、実行するようにすることが多い。この場合、コンパイラはリロケータブルバイナリを出力し、実行可能ファイルの生成にはリンケージエディタが必要であり、さらに動的リンクで実行する場合はダイナミックリンカローダ（ローダの一種）も必要である。

歴史

初期のコンピュータのプログラミングは機械語で直接おこなわれていた。プログラムを指して「コード」（暗号の意がある）という語があるのは、知らない人間には機械語は全く意味のわからない数値の塊だからである。しかし、十進法の数字で書かれたアドレスを内部表現の二進法に変換する、といったごく単純なアセンブリ言語の機能を持ったプログラムはEDSACにおいて既に存在していた。

機械語でのプログラミングは言うには及ばず、アセンブリ言語でもプログラミングは面倒な作業である。そういった低水準言語から、より扱いやすい高水準言語が徐々に求められるようになった。また、機械の詳細が抽象化されることにより、プログラミング言語で書かれた同一のソースコードを元に、詳細が異なる機械で動くプログラムが生成できる、という利点もあった。

1950年代末までに、プログラミング言語がいくつか提案され、実験的なコンパイラがいくつか開発された。世界初のコンパイラは1952年、グレース・ホッパーが書いたA-0 Systemである。

1957年、IBMのジョン・バッカスのチームが開発したFORTRANコンパイラが一般には世界初の完全なコンパイラであるとされている。一般的なコンパイラの開発では、まず動くものを作ってから最適化の機能を付加するが、最初のFORTRANコンパイラでは、コンパイラが実用になることを示すために、最初から最適化に労力が向けられた。

1960年の、ホッパーらによるCOBOLは複数のアーキテクチャ上でコンパイル可能となった最初の言語の1つである[1]。

様々なアプリケーション領域で、高水準言語というアイデアは素早く浸透していった。機能が拡張されたプログラミング言語が次々と提案され、コンピュータのアーキテクチャそのものも複雑化していったため、コンパイラはどんどん複雑化していった。

初期のコンパイラはアセンブリ言語で書かれていた。世界初のセルフホスティングコンパイラ（コンパイル対象言語で書かれたコンパイラのソースコードをコンパイルできるコンパイラ）は1962年にマサチューセッツ工科大学の Hart と Levin が開発したLISPである[2]。1970年代には、特にPascalやC言語などにおいて、コンパイル対象言語でコンパイラを書くのが一般化した。より高水準の言語では、PascalやC言語で実装することも多い。セルフホスティング・コンパイラの構築には、ブートストラップ問題がつきまとう。すなわち、コンパイル対象言語で書かれたコンパイラを最初にコンパイルするには、別の言語で書かれたコンパイラが必要になるという問題である。Hart と Levin の LISPコンパイラではコンパイラをインタプリタ上で動作させてコンパイルを行った。

教育用コンパイラ

コンパイラ構築とコンパイラ最適化は、大学での計算機科学や情報工学のカリキュラムの一部となっている。そのようなコースでは適当な言語のコンパイラを実際に作らせることが多い。文書が豊富な例としてはニクラウス・ヴィルトが1970年代に教育用に設計し、教科書中で示した PL/0 がある[3]。PL/0 は単純だが、教育目的にかなった基本が学べるようになっている。PL/0 はPascalで書かれていた。ヴィルトによる教科書は何度か改訂されており、1996年の版ではOberonでOberonのサブセットOberon-0を実装している。

段階的改良によるプログラム開発の採用
再帰下降構文解析の採用
拡張BNF記法による文法記述の採用
Pコードの採用
ブートストラップ問題をT図式で形式的に記述（T図式とは、コンパイル元言語、コンパイル先言語、コンパイラ実装言語をTの字形に図示するもの）

分類

オブジェクトコードが機械語ではない別のプログラミング言語である場合、あるいは扱う言語がプログラミング言語ではない言語処理系一般（TeXなど）の場合はコンパイラではなくトランスレータと呼ぶ場合がある。コンパイラでは多くの場合、ソースコードの言語は、人間向けの簡潔な言語（高級言語）であり、オブジェクトコードはコンピュータが直接実行可能な機械語（プログラミング言語に含めないこともある）である。機械語が特定のプロセッサ群の「固有語」であることから、機械語プログラムを「ネイティブコード」とも言い、またネイティブコードを出力するコンパイラを「ネイティブコンパイラ」という。

コンパイラは翻訳機と言えるもので、入力するプログラミング言語と対象となるCPUやオペレーティングシステムによるオブジェクトコード形式によって、違う形式のオブジェクトを生成する必要がある。一般的には1つのプログラミング言語を1つのオブジェクトコード形式に変換するものがよく使われる。

開発環境とは別の環境で実行できるコードを生成するコンパイラは、クロスコンパイラと呼ばれる。新しいコンピュータが開発されるとき、BIOSやOSなどもっとも基本となるプログラムについて、既存のものがそのままでは実行できない場合がある。あるいは、組み込みシステムやPDAなど、それ自体が開発環境を動作させるだけの性能を持たない場合がある。こういった場合、クロスコンパイラが必要になる。同じCPUの場合はセルフコンパイラ。

直接CPUで解釈実行可能なコードを生成せずに、中間コードを生成し、別のインタプリタによって実行するものもある。これを中間言語コンパイラ、バイトコードコンパイラなどと呼ぶ。インタプリタ・コンパイラとは呼ばない。インタプリタを作るためのコンパイラがあれば、インタプリタ・コンパイラと呼んでもよい。

ワンパスとマルチパス

コンパイラは様々な処理の集合体であり、初期のコンピュータではメモリ容量が不十分であったため、一度に全ての処理を行うことができなかった。このためコンパイラを複数に分割し、ソースコード（あるいは何らかの中間的な表現）に何度も処理を施すことで解析や変換を行っていた。

一回でコンパイルが可能なものをワンパスコンパイラと呼び、一般にマルチパスコンパイラよりも高速で扱いやすい。多くの言語はワンパスでコンパイルできるよう意図して設計されている（たとえば、Pascal）。

言語の設計によっては、コンパイラがソースコードを複数回読み込む必要がある。たとえば、20行目に出現する宣言文が10行目の文の変換に影響を与える場合がある。この場合、一回目のパス（読み込み）で影響を受ける文の後にある宣言に関する情報を集め、二回目のパスで実際の変換を行う。

ワンパスの欠点は、高品質のコードに欠かせない最適化を行いにくいという点が挙げられる。最適化コンパイラが何回読み込みを行うかというのは決まっていないが、最適化の各フェーズで同じ式や文を何度も解析することもあるし、一回しか解析しない箇所もある。

コンパイラを小さなプログラムに分割する手法は、研究レベルでよく行われる。プログラムの正当性の判定は、対象プログラムが小さいほど簡単なためである。

マルチパスコンパイラは最終パスで機械語コードを出力するのが普通だが、次のような変種も存在する。

高級言語から別の高級言語への翻訳を行うトランスレータでは、機械語コードは生成しない。たとえば、自動並列化コンパイラは高級言語で書かれたプログラムを並列化した記述に変換したり（OpenMPなど）、何らかの言語構文を変換したりする（FORTRANの DOALL 文など）。
ステージコンパイラ（Stage Compiler）は何らかの理論上のマシンのアセンブリ言語を出力する。たとえば、一部のPrologでそのような実装がなされている。Java や Python のバイトコードコンパイラもステージコンパイラの一種と言える。
Java や Smalltalk やマイクロソフトの共通中間言語システムで使われているJITコンパイラ。コンパイラはいったんバイトコードを生成し、実行時にバイトコードが機械語にコンパイルされる。

「コンパイラ言語」

もっぱらその言語の処理系がコンパイラとして実装される言語を「コンパイラ言語」などと言い、インタプリタとして実装される言語を「インタプリタ言語」などと言うこともあるが、実験的な実装まで含めればどちらもある言語も多く、Javaのような、コンパイラで中間表現にコンパイルしそれをインタプリタで実行する、というようなシステムもどんどん一般的になりつつもある今日、テンプレート:独自研究範囲

言語によっては、仕様にコンパイラの存在を前提とした項目があるものもある（たとえばCommon Lisp）。また、インタプリタの実装が容易でコンパイラの実装が困難な言語もある（APL、SNOBOL4など）。メタプログラミングの利用、特に文字列をevalすることはインタプリタではなんでもないが、コンパイラでは実行環境にコンパイラ自体が必要がある（動的プログラミング言語も参照）。

ハードウェア・コンパイラ

ハードウェア記述言語の処理系（合成系）を、ハードウェアコンパイラとかシリコンコンパイラなどと呼ぶことがある。

コンパイルのタイミング

コンパイルをアプリケーションの実行時に行うか、実行前に行うかで2つに分かれる。

事前コンパイラ - 実行前に事前にコンパイルする。Ahead-Of-Timeコンパイラ (AOTコンパイラ)。
実行時コンパイラ - 実行時にコンパイルする。Just-In-Timeコンパイラ (JITコンパイラ)。

設計

コンパイラは、一般にソースコードを読み込み、トークンに分解する字句解析部（字句解析器）、トークン列をもとにプログラムの構文木を構築する構文解析部（構文解析器）、構文木からオブジェクトコードを生成するコード生成部からなる。加えて、コード生成の前段階で効率の高いコードに変換する最適化部を持つことがある。

字句規則から字句解析器を生成するlex、構文規則から構文解析器を生成するパーサジェネレータというプログラムがあり、広く実用に使われている。コンパイラ全体を生成するコンパイラジェネレータも研究されているものの、広く実用に使われるには至っていない。

コンパイラ設計手法は処理の複雑さ、設計者の経験、利用可能なリソース（人間やツール）に影響される。

比較的単純な言語のコンパイラを1人で書く場合、単一でモノリシックなソフトウェアとなることが予想される。ソース言語が巨大で複雑なもので、高品質の出力を要求される場合、コンパイラを多段階に分割して設計していくことになるだろう。コンパイラ機能の分割により、複数の人々がそれを分担することになる。また、分割することで個別の改良が容易となり、新たな機能の追加（たとえばさらなる最適化）が容易になる。

コンパイル処理の分割を採用したのはカーネギーメロン大学での Production Quality Compiler-Compiler Project (PQCC) であった。このプロジェクトでは、「フロントエンド」、「ミドルエンド」（今日では滅多に使われない）、「バックエンド」という用語が生み出された。

非常に小さなコンパイラ以外、今日では2段階以上に分割されている。しかし、どういったフェーズ分けをしようとも、それらフェーズはフロントエンドかバックエンドの一部と見なすことができる。フロントエンドとバックエンドの分割点はどこかというのは論争の種にもなっている。フロントエンドでは主に文法的な処理と意味論的な処理が行われ、ソースコードよりも低レベルな表現に変換する処理が行われる。

ミドルエンドはソースコードでも機械語でもない形式に対して最適化を施すフェーズとされる。ソースコードや機械語と独立しているため、汎用的な最適化が可能とされ、各種言語や各種プロセッサに共通の処理を行う。

バックエンドはミドルエンドの結果を受けて処理を行う。ここでさらなる解析・変換・最適化を特定のプラットフォーム向けに行う場合もある。そして、特定のプロセッサやOS向けにコードを生成する。

このフロントエンド/ミドルエンド/バックエンドという分割により、異なるプログラミング言語向けのフロントエンドを結合したり、異なるCPU向けのバックエンドを結合したりできる。この手法の具体例としてはGNUコンパイラコレクションや Amsterdam Compiler Kit、LLVM がある。これらは複数のフロントエンドと複数のバックエンドがあり、解析部を共有している。

フロントエンド

フロントエンドはソースコードを分析して、中間表現または IR と呼ばれるプログラムの内部表現を構築する。また、シンボルテーブルを管理し、ソースコード内の各シンボルに対応したデータ構造に位置情報、型情報、スコープなどの情報を格納する。このような処理はいくつかのフェーズで実施される。たとえば以下のようなフェーズがある。

行再構築(Line reconstruction) - キーワードにストロッピング(stropping)を施す場合や識別子に空白を挿入可能な場合、字句解析の前に入力文字列を正規化する必要がある。1960年代の一般的なトップダウンの再帰下降型の表駆動構文解析では、ソースを一度読み込むだけでトークン化のフェーズは不要だった。ストロッピングを行う言語としては、Atlas Autocode、Edinburgh IMP、一部のALGOL処理系などがあり、これらは「行再構築」フェーズを持っている。ストロッピングとは、キーワードに何らかの記号をつけることでキーワードとして使われている文字列を予約語とせず、同じ文字列を変数名やサブルーチン名に利用できるようにしたものである。たとえば、シングルクオートでキーワードを囲むとか、%記号を先頭につけるなどの記法がある。
字句解析 - ソースコードを「トークン」と呼ばれる断片に分割する。各トークンは言語の最小構成要素であり、キーワード、識別子、シンボル名などである。トークンは一般に正規言語に従うため、正規表現を解釈する有限オートマトンで認識できる。字句解析を行うソフトウェアを字句解析器（lexical analyzer）と呼ぶ。
プリプロセッサ - C言語などでは、マクロによる文字列置き換えや条件付きコンパイルなどの処理をするフェーズが必要である。一般にこのフェーズは構文解析や意味解析の前に行われる。C言語の場合、プリプロセッサはトークンを操作するものであって、構文を考慮しない。しかし、Schemeのような言語では構文解析後にマクロによる置き換えが行われる。
構文解析 - トークン列を解析し、プログラムの構造を明らかにする。このフェーズで構文木が構築され、単なるトークンの列だったプログラムにその言語の文法を定義した形式文法の規則を適用することで木構造を生成する。構文木は、この後の工程で解析され、強化され、変換される。
意味解析 - 構文木に意味論的情報を追加し、シンボルテーブルを作成する。型チェック（データ型などを間違っていないかのチェック）や、変数や関数の定義と参照箇所を結びつける処理、既定値代入（自動変数の初期化）、意味的に不正なプログラムを検出して通知するなどの処理が行われる。意味解析には完全な構文木が必要であり、理論上構文解析とコード生成の間に行わなければならない。もちろんコンパイラの実装によってはこれらを渾然一体に行うこともある。

バックエンド

「バックエンド」という用語は「コード生成」という用語と混同されることが多い。アセンブリ言語コードを生成するという意味で機能的にも類似しているためである。書籍によっては、バックエンドの汎用解析フェーズと最適化フェーズを「ミドルエンド」と称してマシン依存のコード生成部と区別することがある。

バックエンドに含まれる主なフェーズは以下の通りである。

解析部 - 入力から生成された中間表現を使って各種情報を収集する。主な解析として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

参考文献

Compiler textbook references コンパイラ構成論の教科書（英語）のリスト
Compilers: Principles, Techniques and Tools by Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman (ISBN 0-201-10088-6)
- 原田賢一訳、『コンパイラ—原理・技法・ツール<1>』サイエンス社、1990年。ISBN 4781905854
- 原田賢一訳、『コンパイラ—原理・技法・ツール<2>』サイエンス社、1990年。ISBN 4781905862
Advanced Compiler Design and Implementation by Steven Muchnick (ISBN 1-55860-320-4).
Engineering a Compiler by Keith D. Cooper and Linda Torczon . Morgan Kaufmann 2004, ISBN 1-55860-699-8.
Understanding and Writing Compilers: A Do It Yourself Guide (ISBN 0-333-21732-2) by Richard Bornat - 構文木からの機械語の再帰的生成を説明している貴重な書籍。古いメインフレームやミニコンピュータの経験に基づいており、最近の書籍が見落としがちな部分もカバーしている。著者のサイトにあるPDF版
An Overview of the Production Quality Compiler-Compiler Project by Leverett, Cattel, Hobbs, Newcomer, Reiner, Schatz and Wulf. Computer 13(8):38-49 (August 1980)
Compiler Construction by Niklaus Wirth (ISBN 0-201-40353-6) Addison-Wesley 1996, 176 pages, PDF版。再帰下降構文解析の解説。Oberon-0という小型の言語のコンパイラを題材にしている。
"Programming Language Pragmatics" by Michael Scott (ISBN 0-12-633951-1) Morgan Kaufmann 2005, 2nd edition, 912 pages. 著者のサイト
"A History of Language Processor Technology in IBM", by F.E. Allen, IBM Journal of Research and Development, v.25, no.5, September 1981.

外部リンク

GCC, a widely-used open-source compiler
Building and Testing gcc/glibc cross toolchains
The Amsterdam Compiler Kit オープンソース
The comp.compilers newsgroup and RSS feed
コンパイラ構成論河野真治（琉球大学）