コンパイラの仕組み（基本編）
後置記法
コンパイラの説明に入る前に、コンパイラの中で良く使われる後置記法について説明します。
普段、僕達が使ってるのは、中置記法といって、演算子が中に入っていますが、後置記法では、演算子を後ろにおきます。
a + ba * b + c * d + e * f
- 後置記法
a b +a b * c d * + d f * +
中置記法では、演算子に優先順位をつけなければいけませんが、後置記法では、左から順番に計算するだけなので、コンピュータで計算する場合にとても都合が良い。
多くのコンパイラは、中置記法で書かれた式を後置記法に変換して計算を行います。
リスト
リストの本来の意味は、一覧表、目録、名簿ですが、コンピュータサイエンスの分野では、要素を順番に並べたもののことを意味します。
抽象データ型のリストに対する基本操作は以下。
- k番目の要素の前に要素を挿入
- k番目の要素を削除する
- k番目の要素の内容を読む／書く
- 特定のキーをもつ要素を探索する
- 複数のリストを1つにまとめる
- 1つのリストを複数に分割する
- リストの複製を作る
- リストに含まれる要素の数を求める。
これらの操作を全部効率よく実行できるデータ構造を実現するのは難しいので、プログラムの中で必要となる操作のみを効率良く実行出来るデータ構造を採用する。
スタック
リストの特別な場合で、挿入と削除がリストの先頭のみで行われるもの。スタックに要素を挿入することを、積む（push）、削除することを降ろす（pop）と言います。
カッコの入れ子構造の解析などに向いており、コンパイラでは、いろんなところで使われています。
例えば、先ほどの中置記法を後置記法に変換する際にも使用されていて、以下のような手順で行われます。
優先順位を以下として、
"("、")" < "+"、"-" < "*"、 "/"
- スタックに、"("をpush
中置記法を左から読みながら
- 演算数を読んだら、それをそのまま出力
- 演算子を読んだら、スタック上にそれより優先順位の高い演算子があればそれをpopして出力し、読み込んだ演算子をスタックにpush
- 式の終わりには、")"を読み込んだことにする
コンパイラの論理構造
一般的なコンパイラの構造は、以下。
簡単な例以下のようなプログラムで考えてみる。
#include <stdio.h> int main() { int abc = 100; int a = 2; abc = a * 200 + abc / a; return 0; }
また、abcとaの宣言までは終わってるものとして進める
- 読み込み原始プログラムをファイルから、行単位で読み込む。
abc = a * 200 + abc / a;
- 字句解析
読み込まれた原始プログラムの文字の列を、1字1字調べながら、プログラム言語の基本要素を取り出していく。
abc = a * 200 + abc / a ;
↑ のように要素をわけ、その各要素が変数名か、定数か、演算子かなどの解析をする。
単語から文がどのように構成されているかを調べる。
-
- 中置記法でかかれた代入文を、
abc a 200 * abc a / + =
に変換し、構文木で表現する。
- 中間語生成
構文木はプログラムの構造を示しているものであるから、それをそのまま中間語の形とする場合もあるが、より目的コードに近い形として、構文木の構成要素を実行時に実行される順に並べた列を中間語とする場合もある。その場合、以下のような中間語列が得られる。
(*, a, 200, T0) (/, abc, a, T1) (+, T0, T1, T2) (=, T2, , abc)
これは、4つの組と呼ばれる形であり、例えば、最初の(*, a, 200, T0)は、a * 200の演算結果をT0に入れることを意味する。
- 最適化
目的プログラムを実行時の効率のよいものにすること。そのために、中間語の列の中で無駄なものをはぶいたり、順序を入れ替えたりして、より効率の良い木体プログラムとなるようにする。
- 目的コード生成
中間語のプログラムから機械語の目的プログラムを生成する。出来上がった目的プログラムは、通常はファイルに出力される。
... movl $100, -12(%ebp) # 100を%ebp-12に入れる（abc = 100） movl $2, -8(%ebp) # 2を%ebp-8に入れる（a = 2） ... movl -8(%ebp), %eax # aを%eaxに imull $200, %eax, %ecx # 200 と %eaxの値(a)を乗算して%ecxに入れる movl -12(%ebp), %edx # abcを%edxに movl %edx, %eax # %edxの値(abc)を%eaxに sarl $31, %edx idivl -8(%ebp) # %eaxの値(abc) / %ebp-8の値(a)の結果を商を%eaxに余りを%edxに leal (%ecx,%eax), %eax # %ecx + %eaxを%eaxに入れる movl %eax, -12(%ebp) # %eaxの値を%ebp-12に入れる ...
