コンパイラ入門2 コンパイラの例・論理的構造・物理的構造

前回の記事はこちら

コンパイラ入門1 変換系と通訳系・後置記法・スタック

コンパイラの例

前回の記事で基本的な知識を解説したので、ここでは原始プログラムの文がどのようにして目的プログラムへと変換されるかをみていきます。

例として、次のようなC言語のプログラムの代入式をみてみます。

float abc, e3, fg;
abc = e3*2.56 + abc/e3;

これを後置記法へと変換すると、次のようになります。

abc e3 2.56 * abc e3 / + =

スタックを持った仮想マシンを想定し、変数宣言の部分は解析済みとします。

変数宣言部の解析結果は、変数名や型名、割り当てられた番地などの情報を表にまとめてコンパイラ内部に保存されます。

表1:変数名表1
ID 変数名 番地
0 abc float 100
1 e3 float 104
2 fg float 108

今、コンパイルの対象となる文は次のような文字列として読み込まれています

abc = e3*2.56 + abc/e3

最初のabcを、1番目の表の0番目として(1,0)という記号で表すとします。この記法はコンパイラ内部で字句を表すものでトークン、もしくは符と呼ばれたりします。

演算数は読むとすぐ出力するので、以下のようになります

出力:(1,0)

次に「=」を見ると、代入記号であるので、(8,1)という記号としてスタックに積みます。(8は演算記号、1は代入を表すものとする)、開始記号は「(」です。

出力:(1,0)

スタック:(, 1

次にe3を読み込み(1,1)を出力、「*」を読んで優先順位が高かったため(8,5)としてスタックに積みます

出力:(1,0) (1,1)

スタック:(, 1, 5

次に2.56を見ると、これは定数であるため計算機の内部表現として浮動小数てんの2.56に変換して定数表に書き込みます

表2:定数表1
ID 変数名 番地
0 2.56 double 200

出力:(1,0) (1,1) (2,0)

スタック:(, 1, 5

次に「+」を読み(8,3)としてスタックの演算記号と比較すると、演算記号5(*)の方が優先順位が高いためこれをスタックから下ろして出力、演算記号1(=)よりは優先順位が高いためスタックに積みます

出力:(1,0) (1,1) (2,0) (8,5)

スタック:(, 1, 3

次にabcは(1,0)として出力し、「/」は(8,6)として、演算記号3より高いためスタックに積みます

出力:(1,0) (1,1) (2,0) (8,5) (1,0)

スタック:(, 1, 3, 6

最後にe3を読んで(1,1)を出力し、「;」を読んでスタックの全ての演算記号を下ろして出力します

出力:(1,0) (1,1) (2,0) (8,5) (1,0) (1,1) (8,6) (8,3) (8,1)

これを表と比較し直すと、出力は以下のようになります

abc e3 2.56 * abc e3 / + =

論理的構造

コンパイラは以下のような流れでコンパイルを行います。

1, 読み込み

原始プログラムをファイルから読みこむ、一般的には行単位

2, 字句解析

読み込まれた文字列を調べながらプログラム言語の基本要素を切り出し、それが変数名なのか演算子なのかなどの解析を行う。

字句解析の結果は変数名表に書き込まれ、結果として渡されるのはトークン

3, 構文解析

単語から文がどのように構成されているかを調べる、文法(構文規則)のどの規則に対応しているかを解析し、プログラムが文法的に正しいかを判定する

4, 中間語生成

構文木がプログラムの構造を示しているので、そのまま中間語とする場合もある。またはより目的コードに使い形として構文木の要素を実行される順に並べた列を中間語の形とする場合もある

5, 最適化

目的プログラムを効率よく実行するようにするためのプロセスで、中間語の中で無駄なものを省いたり、順序を入れ替えることでより効率の良い目的プログラムとする

6, 目的コード生成

中間語のプログラムから機械語の目的プログラムを生成する

 

このように、コンパイラは論理的な段階に分けて考えることができ、この各段階を相(フェーズ)と言います。

物理的構造

コンパイラの論理的構造を説明しましたが、実際のコンパイラは必ずこの通りになっている訳ではなく、最適化の相がなかったり順番が違っていたりします。

原始プログラムはあるルーチン群によって中間プログラムに変換され、それがまた別のルーチン群により変換されて…といったプロセスを経て最終的な目的プログラムに変換されます。このルーチン群のことをパスと呼びます。

1パスコンパイラとは論理構造の全ての相を1つにまとめたもので、通常は最適化の相はありません。1パスコンパイラはコンパイル時間が短いため、プログラムのデバック時などに適しています。しかし最適化されていないため実行効率はよくありません。実行効率を重要とするコンパイラは最適化コンパイラと呼ばれ最適化のパスを持ちます。

最適化のパスにかかる比重は大きいため、読み込みから中間語作成をパス1、最適化をパス2、コード生成をパス3とする3パスコンパイラのようなものもあります。

もし中間語をマシンに依存しないような形にすれば、言語の種類がn,マシンの種類がkの時、パス1(フロントエンド)をn個、パス2(バックエンド)をk個作成するだけでn*k個のコンパイラができます。