コンパイラ
何らかのプログラミング言語で記述されたプログラムをコンピュータが実行可能なコードに変換し、その後実行するする言語システムを一般にコンパイラ言語と呼ぶ。コンパイラは、その中でコード変換を行う中核部分もしくは、その技術の名称である。
一般に人間が理解しやすい表現形式を持つ言語を「高級言語」と呼ぶが、この高級言語をコンピュータが実行するには、大きくコンパイラ方式とインタープリタ方式の2つがある。前者は、ソースプログラムを読みこみ、実行可能な機械語からなるバイナリプログラムを出力し、その後実行を行う。インタープリタ方式では、ソースプログラムを読みこみながら、解釈を行い、直接実行を行う。一般にコンパイラ言語のほうが実行効率がよいとされているが、中間言語方式など、両者の方法を取り入れたものなどもあれば、言語仕様によってはインタープリタでも高速な実行が可能な場合もある。
コンパイラ
コンパイラとは、特定のプログラミング言語で記述されたソースコードを読み込み、ターゲットとなるコンピュータ、あるいは、バーチャルマシンが直接実行できる命令語に変換するソフトウェアのことである。
ソフトウェア開発に用いられるプログラミング言語には、アセンブラ言語のような低水準のもの(低級言語)から、より人間に近い表現が可能であるFortran、COBOL、C言語、C++、Pascal、Java、C#といった高水準の言語(高級言語)まで多種である。高級言語でプログラムを作成した場合、そのソースコードは、計算機で直接実行することはできない。コンピュータに実行を指示するためには、CPUが解釈できる機械語で記述された実行プログラムを、あらかじめ記憶装置に格納しておいてから計算機の動作を開始させる必要がある。コンパイラは、あらかじめ高級言語のソースコードを読み込み、実行対象となる計算機のCPUが解釈可能な機械語へと変換するために用いられる。
コンパイラを用いてソースコードを機械語に変換する処理そのものは、コンパイルと呼ばれる。
コンパイラが、最終ターゲットであるCPU固有の機械語を出力する場合、そのコンパイラは特にネイティブコンパイラと呼ばれ、その処理はネイティブコンパイルと呼ばれる。対して、Java仮想マシンのような仮想的な論理計算機をターゲットにしてコンパイルを行うようなコンパイラは、中間言語コンパイラと呼ばれる。中間言語コンパイラにより出力された、中間言語のプログラムを実行するのは、ネイティブな計算機ではなく、Java仮想マシンのようなインタープリタということになる。インタープリタが実行時に、中間言語の一部を部分的にネイティブの機械語に変換してから実行する場合は、動的コンパイル、あるいはジャストインタイムコンパイルと呼ばれる。動的コンパイルに対して、通常のコンパイルは、実行に先立ってあらかじめコンパイルしておくという意味で、事前コンパイル(プリコンパイル)と呼ばれる。
プログラミング言語のうち、高級言語を用いて作成されたプログラムは、特定のターゲットCPUに依存しない。コンパイル時にターゲットCPU向けのコンパイラを用いることにより、特定CPU向けの実行コードを得ることができるため、最終的に任意の計算機で実行できることになる。なお、中間言語方式のコンパイラの場合、コンパイル作業自体は1回だけ行えば、同じ中間言語プログラムをさまざまな計算機上で実行することができる。この場合、コンパイラは1種類で済むものの、コンパイル結果の中間言語プログラムを解釈実行するインタープリタ、あるいは仮想計算機が、ターゲットとなる計算機の種類の分だけ用意する必要がある。
ソフトウェアの規模がある程度以上となる場合、ソフトウェアをモジュールに分割して、モジュールごとにコンパイルを行うこともある。この作業は、特に分割コンパイルと呼ばれる。分割コンパイルを行った場合、その出力としてオブジェクトコードと呼ばれるモジュール単位の出力が得られる。実行に際しては、出力されたオブジェクトコードを一つにまとめ上げ、実行形式のファイルを作成する必要がある。このような操作がリンクと呼ばれる。リンクにより、モジュールごとに記述されている変数やコードが相互に参照できるように相対アドレスの解決を行う。
なお、世界で最初に実用化されたコンパイラは、1957年に開発されたFortranコンパイラである。1960年には、複数のアーキテクチャに対応したCOBOLコンパイラが開発された。1962年には、LISP言語で記述されたLISPコンパイラで自分自身をコンパイルするセルフホスティングコンパイラが初めて開発されている。
コンパイラ
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/10/15 08:56 UTC 版)
この記事には参考文献や外部リンクの一覧が含まれていますが、脚注による参照が不十分であるため、情報源が依然不明確です。 |
プログラムの実行 |
---|
一般的な概念 |
コードの種類 |
コンパイル戦略 |
有名なランタイム |
|
有名なコンパイラとツールチェーン |
|
ソフトウェア開発 |
---|
中心となる活動 |
パラダイムとモデル |
方法論とフレームワーク |
開発支援 |
プラクティス |
ツール |
標準と機関 |
用語集 |
|
コンパイラ(英: compiler)は、高水準言語で書かれたコンピュータプログラムを、 コンピュータが実行や解釈できる形式に、一括して(※[1])変換するソフトウェア[2]。
概説
コンパイラの技術書のバイブルとされるAlfred V.Aho(アルフレッド・エイホ)著 Compilers, Principles, Techniques, and Tools(通称「ドラゴンブック」[注釈 1])の第1章1節の冒頭に、コンパイラとはそもそも何かということについて説明が掲載されており、そこには「簡潔に言うと、コンパイラとは、ある言語(プログラミング言語)で書かれたプログラム(ソースプログラム)を読み、それを別の言語で書かれた等価のプログラム(ターゲットプログラム)へと翻訳(translate)するプログラムである。」と書かれており、さらに続けて「コンパイラは、ソースプログラムに含まれるエラーをユーザに報告するという重要なことを翻訳の1プロセスとして行う。」という説明も加えている[3]。
英語の動詞で、あるプログラム言語で書かれたコードを別の言語で書かれたコードに変換することを"compile"(コンパイル)といい、コンパイラとはその変換を一括して(※[1] )行なうコンピュータプログラムのことである。インタプリタとよく対比される。
(なお、上では「ソースプログラム」「ターゲットプログラム」という古典的用語を含む説明文を紹介したが、最近の技術用語では、変換される前のプログラムを「ソースコード」と呼び、変換後の機械語あるいは中間言語のプログラムなどを「オブジェクトコード」と呼ぶ[4]傾向がある。また機械語は二進数で書かれているので近年では「バイナリコード」ということもある。)
よくあるのは、高水準言語で書かれたプログラムを、コンピュータのプロセッサ[5]が直接実行できる機械語あるいはアセンブリ言語のような低水準言語あるいは元のプログラムよりも"低いレベル"のコード(例えばバイトコードなどの仮想機械向け中間言語あるいは中間表現)に変換するものである。
コンパイラを俯瞰してみると、この世には圧倒されるほど多種類のコンパイラがある[3]。というのは、ソースコード(ソースプログラム)の記述に使われるプログラミング言語だけに着目しても、FORTRANなど歴史の古い言語から始まり近年勃興してきている言語まで含めると数千にもおよぶプログラミング言語があり、他方、オブジェクトコード(ターゲットプログラム)の記述に使われる言語のほうに着目しても、種類がやはり非常に多く、ソースコードの言語とは別の言語であるかも知れないし[注釈 2]、(あるいは中間言語であるかも知れないし)、あるいは機械語であるかも知れないからであり、その機械語もマイクロプロセッサを用いたコンピュータのものからスーパーコンピュータのものまであり多種多様だからである[3]。
またコンパイラの種類には、シングルパス(ワンパスとも。1回で変換作業を完了できるもの)、マルチパス(en:Multi-pass compiler。複数回の作業が必要だが、主記憶が少なくても動くもの)、ロード・アンド・ゴー(変換してすぐに実行を開始するもの)、デバッグ用、最適化用などの種類もある[3]。 →#分類の節で説明
またコンパイルを使ったコンパイル作業は、ひとつのプログラムとして動作する全てのコードをいっぺんにコンパイルするのではなく、モジュール毎などに分けてコンパイルし(「分割コンパイル」)、ライブラリなどはあらかじめコンパイルされているものと合わせて、実行するようにすることも多い[6]。この場合、コンパイラはリロケータブルバイナリを出力し、実行可能ファイルの生成にはリンケージエディタが必要であり、さらに動的リンクで実行する場合はダイナミックリンカ/ローダ(ローダの一種)も必要である。
なお、「コンパイラ(言語) / インタプリタ(言語)」という2分法的な分類は、Java登場以前では一般的で適切だったが、近年では適切でないことも増えている。開発環境などでは、コンパイルした後に実行するというような手続きを1コマンドで行えるものも増えている。そして、Java以降はインタプリタでも実行時コンパイラなどの技術の利用がさかんになってきており、古典的な意味での「コンパイラ」と「インタプリタ」の中間的な性質のツール(プログラム)も増えてきているからである。
なお英語の「compile」はもともと「編集する」「編纂する」という意味の英語であり[7][8]、「compiler」というのは「編集者」という意味の英語である[9][10][11][12]。
歴史
1940年代まで、コンピュータのプログラミングは機械語で直接行なわれていた。プログラムを指して「コード」(英語では暗号を意味する)と呼ぶのは、知らない人間には機械語は全く意味のわからない数値の羅列だからである。しかし、(人間にとって比較的理解のしやすい)十進法の数字で書かれたアドレスを内部表現の二進法に変換する、といったプログラムならばEDSAC(1940年代末に登場した、イギリスのマシン)において既に存在していた。(つまり、この段階で、アセンブラのごく一部の機能に限れば、実現していたことになる)
機械語でのプログラミングは言うに及ばず、アセンブリ言語を用いても、プログラミングというのは面倒な作業である。そういった低水準言語から、人間がより扱いやすい高水準言語が徐々に求められるようになった。また、機械の詳細が抽象化されることにより、高水準なプログラミング言語で書かれた同一のソースコードを元に、詳細仕様が異なる機械でも動くプログラムを生成できる、という利点もあった。1950年代末までに、プログラミング言語がいくつか提案され、実験的なコンパイラがいくつか開発された。
世界初のコンパイラについては、1952年にグレース・ホッパーが書いたA-0 Systemだとされることもある。だが一般的には1957年にIBMのジョン・バッカスのチームが開発したFORTRANコンパイラが世界初の完全なコンパイラであるとされている。一般的なコンパイラの開発では、まず動くものを作ってから最適化の機能が付け加えられるが、最初のFORTRANコンパイラでは、コンパイラが実用になることを示すために、最初から最適化に労力が向けられた。
1960年の、ホッパーらによるCOBOLは複数のアーキテクチャ上でコンパイル可能となった言語の最初期の1つである。
様々なアプリケーション領域で、高水準言語というアイデアは素早く浸透していった。機能が拡張されたプログラミング言語が次々と提案され、コンピュータのアーキテクチャそのものも複雑化していったため、コンパイラはどんどん複雑化していった。
初期のコンパイラはアセンブリ言語で書かれていた。世界初の「セルフホスティングコンパイラ」は、1962年にマサチューセッツ工科大学の Hart と Levin が開発したLISPである[13]。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 がある[14]。PL/0 は単純だが、教育目的にかなった基本が学べるようになっている。PL/0 はPascalで書かれていた。ヴィルトによる教科書は何度か改訂されており、1996年の版ではOberonでOberonのサブセットOberon-0を実装している。
- 段階的改良によるプログラム開発[リンク切れ]の採用
- 再帰下降構文解析の採用
- 拡張BNF記法による文法記述の採用
- Pコードの採用
- ブートストラップ問題をT図式(en:Tombstone diagram)で形式的に記述
インタプリタとの違い
もともとは、コンパイラはしばしばインタプリタと対比されてきたものである。コンパイラは、生成された機械語プログラムなどの実行は行わないが、一度コンパイルすればコンパイラを使わずに何度も実行できるという利点がある。しかし、インタプリタは、バイナリの実行ファイルは生成せず、実行するときに常に必要だが、プログラムを作ったらすぐに実行できるという利点がある[15][16]。
しくみと設計
コンパイラは、概念的に言うと、一般に次のようなフェーズ(phase(s)、段階)に従い処理を行う[17] [18]。
通常、次のような入・出力図で説明される。[17]
ソースプログラム(ソースコード) ↓ 字句解析器 ↓ 構文解析器 ↓ セマンティック解析器 ↓ 中間コード生成器 ↓ コード最適化器 ↓ コード生成器 ↓ ターゲットプログラム(オブジェクトコード)
太字で表記したものがコンパイラの中に含まれている部分(コンパイラの部品)である。つまり、まず字句解析器(字句解析部)がソースコードを読み込みトークンに分解し、次に構文解析器(構文解析部)がトークン列からプログラムの構文木を構築し、次にセマンティック解析器(意味解析器)が意味論的な解析を行い、次に中間コード作成器が中間コードを生成し、次に最適化器がコードの最適化を行い、最後にコード生成器が最終的なターゲットプログラム(オブジェクトコード)[注釈 3]を生成する。
なお、コンパイラの作成に関することだが、字句規則から字句解析器を生成するlex[19]、構文規則から構文解析器を生成するパーサジェネレータ[20]というプログラムがあり、広く実用的に使われている。つまりコンパイラのプログラムの一部分を自動的に書いてくれるようなプログラムがすでにあり、それのおかげで全部人力で書くようなことはしないで済む。(なお、コンパイラ全体を生成するコンパイラジェネレータも研究されているものの、広く実用に使われるには至っていない。)
コンパイラ設計手法は処理の複雑さ、設計者の経験、利用可能なリソース(人間やツール)に影響される。
コンパイル処理の分割を採用したのはカーネギーメロン大学での 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」のような数、などである[21]。トークンは一般に正規言語に従うため、正規表現を解釈する有限オートマトンで認識できる[22]。字句解析を行うソフトウェアを字句解析器(lexical analyzer)と呼ぶ。
- プリプロセッサ - コンパイル前の全処理を行うもの。マクロを実装や、定数の定義、ヘッダファイルの読み込みに使われる。一般にこのフェーズは構文解析や意味解析の前に行われる。プリプロセッサはトークンを操作するものであって、構文を考慮しない[23]。だから、C言語などでは、プリプロセッサでマクロを実装できるが、LISPのような言語では構文解析後にマクロを置き換える必要があり、プリプロセッサは使われない。
- 構文解析 - トークン列を解析し、プログラムの構造を明らかにする。このフェーズで構文木が構築され、単なるトークンの列だったプログラムにその言語の文法を定義した形式文法の規則を適用することで木構造を生成する[24][25]。構文木は、この後の工程で解析され、強化され、変換される。
- 意味解析 - 構文木の要素に意味を追加し、シンボルテーブルを作成する。型チェック(データ型などを間違っていないかのチェック)や、変数や関数の定義と参照箇所を結びつける処理、既定値代入(自動変数の初期化)、意味的に不正なプログラムを検出して通知するなどの処理が行われる。[22]意味解析には完全な構文木が必要であり、理論上構文解析とコード生成の間に行わなければならない。もちろんコンパイラの実装によってはこれらを一度に行うこともある。
バックエンド
「バックエンド」という用語は「コード生成」という用語と混同されることが多い。アセンブリ言語コードを生成するという意味で機能的にも類似しているためである。書籍によっては、バックエンドの汎用解析フェーズと最適化フェーズを「ミドルエンド」と称してマシン依存のコード生成部と区別することがある。
バックエンドに含まれる主なフェーズは以下の通りである。
- 解析部 - 入力から生成された中間表現を使って各種情報を収集する。主な解析としてUD連鎖を構築するデータフロー解析、依存関係解析、エイリアス解析、ポインタ解析、エスケープ解析などがある。正確な解析によってコンパイラ最適化が可能となる。また、コールグラフや制御フローグラフがここで作られることが多い。
- 最適化 - 中間表現を機能的には等価だがより「ベター」な形式に変換する。主な最適化手法としてインライン展開、デッドコード削除、定数伝播、ループ変換、レジスタ割り当て、自動並列化などがある[26]。
- コード生成 - 実際に出力する機械語やバイトコードを生成する。ここでリソースや記憶装置の割り当てが決定される。たとえば、どの変数をレジスタに格納し、どの変数をメモリに格納するか、どの命令をどういう順番で実行するかをアドレッシングモードなどをセシィ-ウルマン法などを用いて決定する。
コンパイラ解析とは、コンパイラ最適化の前に行われる処理で、両者は密接な関係がある。たとえば依存関係解析はループ変換実施に重要な意味を持つ。
さらに、コンパイラ解析と最適化の範囲は様々であり、基本的なブロック単位の場合からプロシージャや関数レベル、さらにはプロシージャの垣根を超えてプログラム全体を対象とすることもある。広範囲を考慮するコンパイラほど最適化に用いることができる「ヒント」が増え、結果としてより良いコードを生成する可能性がある。しかし、広範囲を考慮する解析や最適化はコンパイル時間やメモリ消費のコストが大きい。これは特にプロシージャ間の解析や最適化を行う場合に顕著である。
最近の商用コンパイラはプロシージャ間解析/最適化を備えているのが普通である(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
脚注
注釈
- ^ この本の表紙には赤いドラゴンの絵が描かれているのでドラゴンブックと呼ばれている。
- ^ オブジェクトコードの記述に使われる言語は、要は、その言語から最終的に機械語に翻訳する道筋が1筋(1本)でもあるものであればよい。理論上、機械語にたどり着くまでに途中で何種類もの言語にコンパイル(翻訳)する必要があっても、ともかく最終的に機械語に翻訳するまでの道筋が1本あれば良い。オブジェクトコードの記述に使われる言語は必ずしもアセンブリ言語や機械語でなくてもよい。たとえばC++で書かれたオブジェクトコードを出力するコンパイラやC言語で書かれたオブジェクトコードを出力するコンパイラもある。それぞれ、C++を機械語に、あるいはC言語を機械語に変換するコンパイラを別途用意すれば最終的にCPUが実行できる機械語に変換できる。よくあるのはアセンブリ言語で書かれたオブジェクトコードを出力するコンパイラである。アセンブリ言語で書かれたプログラムも通常そのままでは実行できないが、アセンブラを使ってやはりCPUが実行できる機械語に変換できる。
- ^ 最終的に出力されるターゲットプログラムは、機械語やアセンブリ言語で記述したものが多いが、それらに限るわけではなく、中間コードや高級言語のプログラムを出力するコンパイラもある。
出典
- ^ a b (※)コンパイラの定義文にわざわざ「一括して」という言葉を含めることが多いのは、インタプリタと対比するためである。「一括して」を入れないとインタプリタまで含んでしまい、定義文としては落第点ものとなる。Merriam Websterの英文の定義文でも、やはり「translates an entire set of instructions」[1]と、「命令群(の一部分ではなく)全部を」と明記している。
- ^ “コンパイラとは - IT用語辞典”. IT用語辞典 e-Words. 2023年2月22日閲覧。
- ^ a b c d Alfred V. Aho, Compilers, Principles, Techniques, and Tools. Reprinted with corrections March, 1988.(Copyright 1986,Bell Telephone Laboratories, Incorporated), pp.1-2. (Chapter 1.1 "COMPILERS"の節の説明)
- ^ ASCII.jpデジタル用語辞典,デジタル大辞泉,IT用語がわかる辞典. “オブジェクトコード(おぶじぇくとこーど)とは”. コトバンク. 2020年4月26日閲覧。
- ^ 例えばCPUやGPUなど。
- ^ “分割コンパイル”. www3.nit.ac.jp. 2020年4月27日閲覧。
- ^ プログレッシブ英和中辞典「compile」
- ^ Oxford Dictionary; Produce (a list or book) by assembling information collected from other sources 「何らかの情報源から集めた情報を元にして、一覧や本を作りだす」
- ^ プログレッシブ英和中辞典「compiler」
- ^ 大辞泉「コンパイラ」
- ^ Oxford Dictionary; compiler: A person who produces a list or book by assembling information or written material collected from other sources.
- ^ bit 編集部『bit 単語帳』共立出版、1990年8月15日、82頁。ISBN 4-320-02526-1。
- ^ “CSAIL Publications”. publications.csail.mit.edu. 2020年6月16日閲覧。
- ^ “https://www.246.dk/” (デンマーク語). 2020年6月16日閲覧。
- ^ 2020年4月13日 8分. “コンパイラとインタプリタの違いは?言語の違いを分かりやすく解説!”. じゃぱざむ. 2020年4月27日閲覧。
- ^ “インタプリタとコンパイラ”. nyumon-info.com. 2020年4月27日閲覧。
- ^ a b Alfred V. Aho, Compilers, Principles, Techniques, and Tools. 1988., pp.10-15. 「1.3(1章3節) THE PHASES OF A COMPILER」
- ^ “コンパイラの構造を解説 | Shinta's Site”. www.gadgety.net. 2020年4月27日閲覧。
- ^ “コマンド:lex: UNIX/Linuxの部屋”. x68000.q-e-d.net. 2020年4月27日閲覧。
- ^ “パーサジェネレータとは - Weblio辞書”. www.weblio.jp. 2020年4月27日閲覧。
- ^ “コンパイラの入り口、「字句解析」のための文字列操作 (1/3)”. @IT. 2020年4月27日閲覧。
- ^ a b コンパイラの構成と最適化. Nakata, Ikuo, 1935-, 中田, 育男, 1935-. Tōkyō: Asakurashoten. (2009). ISBN 978-4-254-12177-3. OCLC 675837876
- ^ “プリプロセッサとは - IT用語辞典”. IT用語辞典 e-Words. 2020年4月27日閲覧。
- ^ “抽象構文木”. home.a00.itscom.net. 2020年4月27日閲覧。
- ^ “VU - exp. - compiler-general”. www.is.s.u-tokyo.ac.jp. 2020年4月27日閲覧。
- ^ MaryCore. “知っておいて損はない「コンパイラ最適化」の数々”. MaryCore 言語知能総合研究所. 2020年4月27日閲覧。
参考文献
- 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.
- ニクラウス・ヴィルト(著)、滝沢徹(訳)、牧野裕子(訳):「ヴィルトのコンパイラ構成法」、星雲社、ISBN 4-7952-9706-1(1997年11月28日)。
- 中田育男:「コンパイラの構成と最適化」、朝倉書店、ISBN 978-4-254-12177-3(第2版)(1999年9月15日初版、2009年11月15日第2版)。
- A.V.エイホ、M.S.ラム、R.セシィ、J.D.ウルマン、原田賢一(訳):「コンパイラ[第2版]」、サイエンス社、ISBN 978-4-7819-1229-5(2009年5月25日第2版、1990年10月10日初版)。
- 五月女健治:「JavaCC:コンパイラコンパイラ for Java」、テクノプレス、ISBN 4-924998-64-8(2003年10月20日)。
- Andrew W. Appel、神林靖、滝本宗宏(訳):「最新コンパイラ構成技法」、翔泳社、ISBN 978-4-7981-1468-2(2009年10月29日)。
- 中田育男、渡邊担、佐々政宏:「コンパイラの基盤技術と実践」、朝倉書店、ISBN 978-4-254-12173-5(2008年6月25日)。
- 柏木餅子、風薬:「きつねさんでもわかるLLVM コンパイラを自作するためのガイドブック」、インプレスジャパン、ISBN 978-4-8443-3415-6(2013年6月21日)。
- 中田育男:「コンパイラ 作りながら学ぶ」、オーム社、 ISBN 978-4-274-22116-3(2017年10月25日)。
関連項目
- アセンブラ
- リンケージエディタ(リンカ)
- プリプロセッサ
- GNUコンパイラコレクション
- make (UNIX)
- Autotools
- オブジェクトコンバータ
- 逆コンパイラ
- 分割コンパイル
- 編集
外部リンク
「コンパイラ」の例文・使い方・用例・文例
- 特定のコンピュータで実行の用意ができているコンパイラーの機械語出力
- Cで書かれたプログラムのコンパイラ
- FORTRANで書かれたプログラムのコンパイラ
- LISPに書かれたプログラムのためのコンパイラ
- パスカルで書かれたプログラムのコンパイラ
- コンパイラは、ソースコードをオブジェクトコードに変換するために、ソースコードを解析しなければならない
- (オペレーティング・システム、コンパイラ、ユーティリティー・プログラムのような)コンピュータ操作のある側面を制御するプログラム
- コンパイラーという,コンピューターのプログラム
- コンパイラー言語という,コンパイラーで機械コードに翻訳される人間にわかりやすい形で書かれたプログラム言語
コンパイラと同じ種類の言葉
- コンパイラのページへのリンク