コンパイラ
このプロジェクトでは、「フロントエンド」、「ミドルエンド」(今日では滅多に使われない)、「バックエンド」という用語が生み出された。
非常に小さなコンパイラ以外、今日では2段階(2フェーズ)以上に分割されている。しかし、どういったフェーズ分けをしようとも、それらフェーズはフロントエンドかバックエンドの一部と見なすことができる。フロントエンドとバックエンドの分割点はどこかというのは論争の種にもなっている。フロントエンドでは主に文法的な処理と意味論的な処理が行われ、ソースコードよりも低レベルな表現に変換する処理が行われる。
ミドルエンドはソースコードでも機械語でもない形式に対して最適化を施すフェーズとされる。ソースコードや機械語と独立しているため、汎用的な最適化が可能とされ、各種言語や各種プロセッサに共通の処理を行う。
バックエンドはミドルエンドの結果を受けて処理を行う。ここでさらなる解析・変換・最適化を特定のプラットフォーム向けに行う場合もある。そして、特定のプロセッサやOS向けにコードを生成する。
このフロントエンド/ミドルエンド/バックエンドという分割法を採用することにより、異なるプログラミング言語向けのフロントエンドを結合したり、異なるCPU向けのバックエンドを結合したりできる。この手法の具体例としてはGNUコンパイラコレクションや Amsterdam Compiler Kit、LLVM がある。これらは複数のフロントエンドと複数のバックエンドがあり、解析部を共有している。
コンパイラは、概念的に言うと、一般に次のようなフェーズ(phase(s)、段階)に従い処理を行う 。
通常、次のような入・出力図で説明される。
太字で表記したものがコンパイラの中に含まれている部分(コンパイラの部品)である。つまり、まず字句解析器(字句解析部)がソースコードを読み込みトークンに分解し、次に構文解析器(構文解析部)がトークン列からプログラムの構文木を構築し、次にセマンティック解析器(意味解析器)が意味論的な解析を行い、次に中間コード作成器が中間コードを生成し、次に最適化器がコードの最適化を行い、最後にコード生成器が最終的なターゲットプログラム(オブジェクトコード)を生成する。
なお、コンパイラの作成に関することだが、字句規則から字句解析器を生成するlex、構文規則から構文解析器を生成するパーサジェネレータというプログラムがあり、広く実用的に使われている。つまりコンパイラのプログラムの一部分を自動的に書いてくれるようなプログラムがすでにあり、それのおかげで全部人力で書くようなことはしないで済む。(なお、コンパイラ全体を生成するコンパイラジェネレータも研究されているものの、広く実用に使われるには至っていない。)
コンパイラ設計手法は処理の複雑さ、設計者の経験、利用可能なリソース(人間やツール)に影響される。
コンパイル処理の分割を採用したのはカーネギーメロン大学での Production Quality Compiler-Compiler Project であった。
もともとは、コンパイラはしばしばインタプリタと対比されてきたものである。コンパイラは、生成された機械語プログラムなどの実行は行わないが、一度コンパイルすればコンパイラを使わずに何度も実行できるという利点がある。しかし、インタプリタは、バイナリの実行ファイルは生成せず、実行するときに常に必要だが、プログラムを作ったらすぐに実行できるという利点がある。
「バックエンド」という用語は「コード生成」という用語と混同されることが多い。アセンブリ言語コードを生成するという意味で機能的にも類似しているためである。書籍によっては、バックエンドの汎用解析フェーズと最適化フェーズを「ミドルエンド」と称してマシン依存のコード生成部と区別することがある。
バックエンドに含まれる主なフェーズは以下の通りである。
解析部 - 入力から生成された中間表現を使って各種情報を収集する。主な解析としてUD連鎖を構築するデータフロー解析、依存関係解析、エイリアス解析、ポインタ解析、エスケープ解析などがある。正確な解析によってコンパイラ最適化が可能となる。また、コールグラフや制御フローグラフがここで作られることが多い。
最適化 - 中間表現を機能的には等価だがより「ベター」な形式に変換する。主な最適化手法としてインライン展開、デッドコード削除、定数伝播、ループ変換、レジスタ割り当て、自動並列化などがある。
コード生成 - 実際に出力する機械語やバイトコードを生成する。ここでリソースや記憶装置の割り当てが決定される。たとえば、どの変数をレジスタに格納し、どの変数をメモリに格納するか、どの命令をどういう順番で実行するかをアドレッシングモードなどをセシィ-ウルマン法などを用いて決定する。
一般的なコンパイラの開発では、まず動くものを作ってから最適化の機能が付け加えられるが、最初のFORTRANコンパイラでは、コンパイラが実用になることを示すために、最初から最適化に労力が向けられた。
1960年の、ホッパーらによるCOBOLは複数のアーキテクチャ上でコンパイル可能となった言語の最初期の1つである。
様々なアプリケーション領域で、高水準言語というアイデアは素早く浸透していった。機能が拡張されたプログラミング言語が次々と提案され、コンピュータのアーキテクチャそのものも複雑化していったため、コンパイラはどんどん複雑化していった。
初期のコンパイラはアセンブリ言語で書かれていた。世界初の「セルフホスティングコンパイラ」は、1962年にマサチューセッツ工科大学の Hart と Levin が開発したLISPである。1970年代には、特にPascalやC言語などにおいて、コンパイル対象言語でコンパイラを書くことが一般化した。さらにより高水準の言語のコンパイラは、PascalやC言語で実装することも多い。セルフホスティング・コンパイラの構築には、ブートストラップ問題がつきまとう。すなわち、コンパイル対象言語で書かれたコンパイラを最初にコンパイルするには、別の言語で書かれたコンパイラが必要になる。Hart と Levin の LISPコンパイラではコンパイラをインタプリタ上で動作させてコンパイルを行なった。