コンパイラ
![]() |
プログラムの |
---|
|
コードの |
コンパイル |
|
|
|
|
ソフトウェア |
---|
|
パラダイムとモデル |
|
|
プラクティス |
ツール |
|
|
コンパイラ(
概説
[コンパイラの
(なお、
よくあるのは、
コンパイラを
またコンパイラの
またコンパイルを
なお、「コンパイラ(
なお
歴史
[1940
1960
分類
[コンパイラに
いわゆるネイティブコードではなく
ワンパスとマルチパス
[コンパイラは
ワンパスの
コンパイラを
ネイティブコンパイラの
何 らかの高水準 言語 から、何 らかの高水準 言語 に変換 する「トランスレータ」。「トランスコンパイラ」などという語 もある。たとえば、OpenMPなどの自動 並列 化 コンパイラは並列 化 が明示 されていないプログラムを、並列 化 を明示 したプログラムに変換 する。または、FORTRANのDOALL
文 など何 らかの言語 構文 を変換 する。- ステージコンパイラ(Stage Compiler)は
何 らかの理論 上 のマシンのアセンブリ言語 を出力 する。たとえば、一部 のPrologでそのような実装 がなされている。[要 出典 ]Java や Python のバイトコードコンパイラもステージコンパイラの一種 と言 える。 - Java や Smalltalk やマイクロソフトの
共通 中 間 言語 システムで使 われているJITコンパイラ。コンパイラはいったん中間 表現 を生成 し、実行 時 に中間 表現 がターゲットの機械 語 にコンパイルされる。
コンパイラ言語
[もっぱらその
Common Lispなど
ハードウェア・コンパイラ
[ハードウェア
コンパイルのタイミング
[コンパイルをアプリケーションの
事前 コンパイラ -実行 前 に事前 にコンパイルする。Ahead-Of-Timeコンパイラ (AOTコンパイラ)。実行 時 コンパイラ -実行 時 にコンパイルする。Just-In-Timeコンパイラ (JITコンパイラ)。
教育 用 コンパイラ
[コンパイラ
段階 的 改良 によるプログラム開発 [リンク切 れ]の採用 再帰 下降 構文 解析 の採用 拡張 BNF記法 による文法 記述 の採用 - Pコードの
採用 - ブートストラップ
問題 をT図式 (en:Tombstone diagram)で形式 的 に記述
インタプリタとの違 い
[もともとは、コンパイラはしばしばインタプリタと
しくみと設計
[コンパイラは、
ソースプログラム(ソースコード) ↓字句 解析 器 ↓構文 解析 器 ↓ セマンティック解析 器 ↓中間 コード生成 器 ↓ コード最適 化 器 ↓ コード生成 器 ↓ ターゲットプログラム(オブジェクトコード)
なお、コンパイラの
コンパイラ
コンパイル
ミドルエンドはソースコードでも
バックエンドはミドルエンドの
このフロントエンド/ミドルエンド/バックエンドという
フロントエンド
[フロントエンドはソースコードを
行 再 構築 (Line reconstruction) - キーワードにストロッピングを施 す場合 や識別子 に空白 を挿入 可能 な場合 、字句 解析 の前 に入力 文字 列 を「正規 化 」する必要 がある。1960年代 の一般 的 なトップダウンの再帰 下降 型 の表 駆動 構文 解析 では、ソースコードを一度 読 み込 むだけでトークン化 のフェーズは不要 だった。ストロッピングを行 う言語 としては、Atlas Autocode、Edinburgh IMP、一部 のALGOL処理 系 などがあり、これらは「行 再 構築 」フェーズを持 っている。ストロッピングとは、キーワードに何 らかの記号 をつけることでキーワードとして使 われている文字 列 を予約 語 とせず、同 じ文字 列 を変数 名 やサブル ーチン名 に利用 できるようにしたものである。たとえば、シングルクオートでキーワードを囲 むとか、%記号 を先頭 につけるなどの記法 がある。字句 解析 - ソースコードの文字 列 を、「トークン」と呼 ばれる、言語 的 に意味 のある最小 単位 に分割 する。各 トークンは最小 構成 要素 であり、たとえばキーワード、識別子 、シンボル名 、「10」や「365」のような数 、などである[21]。トークンは一般 に正規 言語 に従 うため、正規 表現 を解釈 する有限 オートマトンで認識 できる[22]。字句 解析 を行 うソフトウェアを字句 解析 器 (lexical analyzer)と呼 ぶ。- プリプロセッサ - コンパイル
前 の全 処理 を行 うもの。マクロを実装 や、定数 の定義 、ヘッダファイルの読 み込 みに使 われる。一般 にこのフェーズは構文 解析 や意味 解析 の前 に行 われる。プリプロセッサはトークンを操作 するものであって、構文 を考慮 しない[23]。だから、C言語 などでは、プリプロセッサでマクロを実装 できるが、LISPのような言語 では構文 解析 後 にマクロを置 き換 える必要 があり、プリプロセッサは使 われない。 構文 解析 - トークン列 を解析 し、プログラムの構造 を明 らかにする。このフェーズで構文 木 が構築 され、単 なるトークンの列 だったプログラムにその言語 の文法 を定義 した形式 文法 の規則 を適用 することで木 構造 を生成 する[24][25]。構文 木 は、この後 の工程 で解析 され、強化 され、変換 される。意味 解析 -構文 木 の要素 に意味 を追加 し、シンボルテーブルを作成 する。型 チェック(データ型 などを間違 っていないかのチェック)や、変数 や関数 の定義 と参照 箇所 を結 びつける処理 、既定 値 代入 (自動 変数 の初期 化 )、意味 的 に不正 なプログラムを検出 して通知 するなどの処理 が行 われる。[22]意味 解析 には完全 な構文 木 が必要 であり、理論 上 構文 解析 とコード生成 の間 に行 わなければならない。もちろんコンパイラの実装 によってはこれらを一 度 に行 うこともある。
バックエンド
[「バックエンド」という
バックエンドに
解析 部 -入力 から生成 された中 間 表現 を使 って各種 情報 を収集 する。主 な解析 としてUD連鎖 を構築 するデータフロー解析 、依存 関係 解析 、エイリアス解析 、ポインタ解析 、エスケープ解析 などがある。正確 な解析 によってコンパイラ最適 化 が可能 となる。また、コールグラフや制御 フローグラフがここで作 られることが多 い。最適 化 -中間 表現 を機能 的 には等価 だがより「ベター」な形式 に変換 する。主 な最適 化 手法 としてインライン展開 、デッドコード削除 、定数 伝播 、ループ変換 、レジスタ割 り当 て、自動 並列 化 などがある[26]。- コード
生成 -実際 に出力 する機械 語 やバイトコードを生成 する。ここでリソースや記憶 装置 の割 り当 てが決定 される。たとえば、どの変数 をレジスタに格納 し、どの変数 をメモリに格納 するか、どの命令 をどういう順番 で実行 するかをアドレッシングモードなどをセシィ-ウルマン法 などを用 いて決定 する。
コンパイラ
さらに、コンパイラ
コンパイラ
簡単 な例
[![]() |
#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
- オブジェクトコンバータ
逆 コンパイラ分割 コンパイル編集