読み込み中...コンパイラ
コンパイル前のプログラムを特に「ソースコード」（原始コード）と呼び、反対にコンパイル後のプログラムを「オブジェクトコード」（目的コード）と呼んで区別する。
多くの場合、コンパイルされた機械語プログラムの実行は、インタプリタを介した実行より高速である。反面、開発時には動作テストのたびに比較的時間のかかるコンパイル作業が必要である。
コンパイラが出力するオブジェクトファイルは、実際に実行するコード以外に外部からの呼び出しをするための名前と、実行開始位置をセットにした情報を持っている場合があり、外部からコードを参照して実行することができる。場合によっては実行できるソフトウェアにするために、ほかのオブジェクトファイルとのリンクが必要なこともある。
歴史
初期のコンピュータのソフトウェアはアセンブリ言語で書かれていた。高級プログラミング言語の開発は、コンパイラ開発のコストよりもソースコードを異なるCPU上で再利用する利点が上回るようになるまで行われなかった。初期のコンピュータは記憶装置の容量が少なく、コンパイラの実装には様々な技法が駆使された。
1950年代末までに、機械に依存しないプログラミング言語が提案され、実験的なコンパイラがいくつか開発された。世界初のコンパイラは1952年、グレース・ホッパーが書いたA-0プログラミング言語である。1957年、IBMのジョン・バッカスのチームが開発したFORTRANが一般には世界初の完全なコンパイラであるとされている。1960年のCOBOLは複数のアーキテクチャ上でコンパイル可能となった最初の言語の1つであるhttp://www.interesting-people.org/archives/interesting-people/199706/msg00011.html。
様々なアプリケーション領域で高級言語というアイデアは素早く浸透していった。プログラミング言語が新たに登場するたびに機能が拡張されていき、コンピュータのアーキテクチャそのものも複雑化していったため、コンパイラはどんどん複雑化していった。
初期のコンパイラはアセンブリ言語で書かれていた。世界初のセルフホスティングコンパイラ（コンパイル対象言語で書かれたコンパイラのソースコードをコンパイルできるコンパイラ）は1962年にマサチューセッツ工科大学の Hart と Levin が開発したLISPであるhttp://www.ai.mit.edu/research/publications/browse/0000browse.shtml。1970年代にはコンパイル対象言語でコンパイラを書くのが一般化したが、PascalとC言語で言語を実装するほうが一般的であった。セルフホスティング・コンパイラの構築には、ブートストラップ問題がつきまとう。すなわち、コンパイル対象言語で書かれたコンパイラを最初にコンパイルするには、別の言語で書かれたコンパイラが必要になるという問題である。Hart と Levin の LISPコンパイラではコンパイラをインタプリタ上で動作させてコンパイルを行った。
教育用コンパイラ
コンパイラ構築とコンパイラ最適化は、大学での計算機科学や情報工学のカリキュラムの一部となっている。そのようなコースでは適当な言語のコンパイラを実際に作らせることが多い。文書が豊富な例としてはニクラウス・ヴィルトが1970年代に教育用に設計した PL/0 があるhttp://www.246.dk/pl0.html。PL/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 やマイクロソフトの共通中間言語システムで使われているジャストインタイムコンパイル方式。コンパイラはいったんバイトコードを生成し、実行時にバイトコードが機械語にコンパイルされる。
コンパイラとインタプリタ
ソースコードをコンパイラによってコンピュータが直接実行可能なプログラムに変換して実行するプログラミング言語のことをコンパイラ言語と呼ぶ。これはインタプリタを介して実行されるインタプリタ言語と対比した言い方である。ただし、多くの言語は、コンパイルされる場合・インタプリタを使って実行される場合のいずれもあり、あくまでどちらが主流であるかを示すものである。コンパイラ言語・インタプリタ言語のどちらにも分類できない言語もある。一般に、コンパイラ言語は、言語仕様がコンパイラ向きに、インタプリタ言語は、言語仕様がインタプリタ向きになっている。
例外として言語仕様にコンパイラの存在が前提とされているものもある（例えばCommon Lisp）。また、インタプリタの実装が非常に容易なのにコンパイラの実装が困難な言語仕様もある（APL、SNOBOL4など）。スクリプト言語なども実行時にソースコードに文字列操作を施して評価するため、コンパイラ実装は困難である。このような機能をコンパイラで実装するには、実行環境としてコンパイラ自体を実行コードに付属させる必要がある。
ハードウェア・コンパイラ
FPGAなどのハードウェアを対象としたコンパイラも存在する。この種のコンパイラをハードウェア・コンパイラとも呼ぶ（詳しくはReconfigurable computing参照）。
設計
コンパイラは、一般にソースコードを読み込み、トークンに分解する字句解析部、トークン列をもとにプログラムの構文木を構築する構文解析部、構文木からオブジェクトコードを生成するコード生成部からなる。加えて、コード生成の前段階で効率の高いコードに変換する最適化部を持つことがある。
プログラミング言語の文法規則からコンパイラの作成に必要な字句解析部・構文解析部を生成するソフトウェアをコンパイラコンパイラと呼ぶ。コンパイラコンパイラはコンパイラを全て生成するわけではなく、オブジェクトコードの生成部等は別途作らなければならない。
コンパイラ設計手法は処理の複雑さ、設計者の経験、利用可能なリソース（人間やツール）に影響される。
比較的単純な言語のコンパイラを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#include #include #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 コンパイラ構成論の教科書（英語）のリスト
- 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, by F.E. Allen, IBM Journal of Research and Development, v.25, no.5, September 1981.
