コンパイラ インタプリタとの違い

コンパイラ

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/11/26 23:30 UTC 版)

インタプリタとの違い

もともとは、コンパイラはしばしばインタプリタと対比されてきたものである。コンパイラは、生成された機械語プログラムなどの実行は行わないが、一度コンパイルすればコンパイラを使わずに何度も実行できるという利点がある。しかし、インタプリタは、バイナリの実行ファイルは生成せず、実行するときに常に必要だが、プログラムを作ったらすぐに実行できるという利点がある[15][16]

しくみと設計

コンパイラは、一般に次のような部分から成る[17]

字句規則から字句解析器を生成するlex[18]、構文規則から構文解析器を生成するパーサジェネレータ[19]というプログラムがあり、広く実用に使われている。コンパイラ全体を生成するコンパイラジェネレータも研究されているものの、広く実用に使われるには至っていない。

コンパイラ設計手法は処理の複雑さ、設計者の経験、利用可能なリソース(人間やツール)に影響される。

コンパイル処理の分割を採用したのはカーネギーメロン大学での Production Quality Compiler-Compiler Project であった。このプロジェクトでは、「フロントエンド」、「ミドルエンド」(今日では滅多に使われない)、「バックエンド」という用語が生み出された。

非常に小さなコンパイラ以外、今日では2段階(2フェーズ)以上に分割されている。しかし、どういったフェーズ分けをしようとも、それらフェーズはフロントエンドかバックエンドの一部と見なすことができる。フロントエンドとバックエンドの分割点はどこかというのは論争の種にもなっている。フロントエンドでは主に文法的な処理と意味論的な処理が行われ、ソースコードよりも低レベルな表現に変換する処理が行われる。

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

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

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

フロントエンド

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

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

バックエンド

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

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

  1. 解析部 - 入力から生成された中間表現を使って各種情報を収集する。主な解析としてUD連鎖を構築するデータフロー解析、依存関係解析、エイリアス解析、ポインタ解析、エスケープ解析などがある。正確な解析によってコンパイラ最適化が可能となる。また、コールグラフ制御フローグラフがここで作られることが多い。
  2. 最適化 - 中間表現を機能的には等価だがより「ベター」な形式に変換する。主な最適化手法としてインライン展開デッドコード削除定数伝播、ループ変換、レジスタ割り当て、自動並列化などがある[25]
  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

  1. ^ コンパイラとは - IT用語辞典” (日本語). IT用語辞典 e-Words. 2020年4月26日閲覧。
  2. ^ 例えばCPUGPUなど。
  3. ^ ASCII.jpデジタル用語辞典,デジタル大辞泉,IT用語がわかる辞典. “オブジェクトコード(おぶじぇくとこーど)とは” (日本語). コトバンク. 2020年4月26日閲覧。
  4. ^ プログレッシブ英和中辞典「compile」
  5. ^ Oxford Dictionary; Produce (a list or book) by assembling information collected from other sources 「何らかの情報源から集めた情報を元にして、一覧や本を作りだす」
  6. ^ プログレッシブ英和中辞典「compiler」
  7. ^ 大辞泉「コンパイラ」
  8. ^ Oxford Dictionary; compiler: A person who produces a list or book by assembling information or written material collected from other sources.
  9. ^ bit 編集部『bit 単語帳』共立出版、1990年8月15日、82頁。ISBN 4-320-02526-1
  10. ^ コンパイラ” (日本語). ITパスポート試験ドットコム. 2020年4月27日閲覧。
  11. ^ 分割コンパイル”. www3.nit.ac.jp. 2020年4月27日閲覧。
  12. ^ CSAIL Publications”. publications.csail.mit.edu. 2020年6月16日閲覧。
  13. ^ https://www.246.dk/” (デンマーク語). 2020年6月16日閲覧。
  14. ^ 【ワンパスコンパイラ】の例文集・使い方辞典 - 用例.jp”. yourei.jp. 2020年4月27日閲覧。
  15. ^ 2020年4月13日 8分. “コンパイラとインタプリタの違いは?言語の違いを分かりやすく解説!” (日本語). じゃぱざむ. 2020年4月27日閲覧。
  16. ^ インタプリタとコンパイラ”. nyumon-info.com. 2020年4月27日閲覧。
  17. ^ コンパイラの構造を解説 | Shinta's Site”. www.gadgety.net. 2020年4月27日閲覧。
  18. ^ コマンド:lex: UNIX/Linuxの部屋” (日本語). x68000.q-e-d.net. 2020年4月27日閲覧。
  19. ^ パーサジェネレータとは - Weblio辞書”. www.weblio.jp. 2020年4月27日閲覧。
  20. ^ コンパイラの入り口、「字句解析」のための文字列操作 (1/3)” (日本語). @IT. 2020年4月27日閲覧。
  21. ^ a b コンパイラの構成と最適化. Nakata, Ikuo, 1935-, 中田, 育男, 1935-. Tōkyō: Asakurashoten. (2009). ISBN 978-4-254-12177-3. OCLC 675837876. https://www.worldcat.org/oclc/675837876 
  22. ^ プリプロセッサとは - IT用語辞典” (日本語). IT用語辞典 e-Words. 2020年4月27日閲覧。
  23. ^ 抽象構文木”. home.a00.itscom.net. 2020年4月27日閲覧。
  24. ^ VU - exp. - compiler-general”. www.is.s.u-tokyo.ac.jp. 2020年4月27日閲覧。
  25. ^ MaryCore. “知っておいて損はない「コンパイラ最適化」の数々” (日本語). MaryCore 言語知能総合研究所. 2020年4月27日閲覧。


「コンパイラ」の続きの解説一覧




コンパイラと同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「コンパイラ」の関連用語

コンパイラのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



コンパイラのページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのコンパイラ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2021 GRAS Group, Inc.RSS