Compiler Construction Lecture 10/14

コンパイラを書くのは難しくない。

簡単なコンパイラを書いてみよう。そして、実際のCコンパイラの ソースを読みながらC言語を理解する。Pentinum、PowerPC などの コードを出力するコンパイラをかけるようになりたい。(ここまで は簡単) そして、世界最高速のコンパイラを作ろう。(もちろん、 これは難しい)

インタプリタとは何か

いろいろな動作や仕様を記述する言語を作る。その言語に従った動作を 実現するのがインタプリタである。Websterには、
inerret \in-'ter-pret, -pet\ vb
1: to explain or tell the meaning of: present in understandable terms
とある。日本語では翻訳系などと呼ぶ人もいる。要するに、プログラム言語を 実行するシステムがインタプリタである。

例えば、メモりに格納されているRS-6000の機械語を実行するのはRISC CPU だが、この場合はRISC CPUがインタプリタに相当する。このRISC CPUは、 簡単に言えば、以下のようなことを電子回路によって行っている。

• 一命令をメモりから取ってくる
• その命令で何をすればいいかを解読する
• その命令に必要なデータを取ってくる
• 計算をおこなう
• 結果をどこかにしまう
• 次に実行すべき命令の場所を決める
インタプリタのすべきことはこれと同じである。しかし、CPUの命令は 1 wordを取ってくれば良いのだが、プログラム言語の場合は、まず言語を 分解して、その構造を調べるひつようがある。これを、
• 字句解析 単語に相当する部分を切りだす
• 構文解析 SVCなどの文の構造を作りあげる
という形に分解するのが普通である。

簡単な言語ならば、構文解析と同時に実行することができる。しか し、同じインタプリタでも前者の方が簡単に実行できるし、電子回 路として実装できるので高速になる。また、プログラムは普通は同 じ所を何回も実行するので、その度に、同じ文を解析するのは効率 が悪い。

したがって、字句解析、構文解析を前もって行って、より実行が簡 単な言語に変換するのが一般的である。現在ではどんなインタプリ タでも、一度、内部コードに変換して実行している。内部コードを 小さくするには1 byteを単位にするコード(byte code)を使うこと も多い。しかし、CPUにより実行する場合は1 word(4 byte)を単位 にするのが普通である。

コンパイラとは何か

このようなプログラムを別な言語に変換するシステムをコンパイラ と呼ぶ。コンパイルとは編集するという意味である。

コンパイラは字句解析、構文解析に関してはインタプリタと同じだ が、実行する代わりに、別な言語を生成する。生成自身は難しくな い。難しいのは、特定の実行アーキテクチャを想定して、もっとも 速く実行できるようなコードを生成することである。

コンパイラが生成する言語は、機械語やバイトコードである必要は ない。他の高級言語でも良い。実際、C言語がこれだけ広まってい るので、C言語を生成するコンパイラ言語が多数ある。例えば、

• TeXを記述しているWebはCに変換される
• LISPやPrologなどの高水準言語をCに変換する
などである。 構文解析や字句解析は、言語を簡単にすることによって、可能な限り さぼることができる。例えば、PostScript は後置記法 (Post fix notation) というのを使って構文解析を簡単にして、printer内部 での実行を高速化している。LISPやforth、APL、BASICなども同じ 発想で作られている。このような言語は、プログラム自身でプログ ラムを取り扱うのに向いており、その言語自身のコンパイラを書く のにもっとも適している。実際、インタプリタがあれば、構文解析 や字句解析が既に存在しているので、コード生成のみが問題となる。 Cなどの複雑な構文を持つ言語は、その点は最悪である。しかし、 だから面白いともいえる。

バイトコード/中間言語を用いる実行は、一つ一つの命令に複雑な 機能を割り当てることができる。この複雑な機能を実現すること自 身は難しくない。しかし、もし、その機能を機械語に落すとなると、 それは簡単ではない。実際には、その機能を実現するライブラリを 併用して実現することになる。高機能な言語のコンパイラを作る時 には、この実行時ライブラリ(Runtime Library)の実現とその最適 化が一番難しい。

Cなどは、言語の機能が機械語に対応しているので、コード生成は 容易である。しかし、それを読みやすい形にしていることが構文解 析を複雑にしている。

コンパイラとインタプリタの組み合わせ

コンパイラを作る時には、さまざまな方法がある。
• まずインタプリタを機械語で作り、その上でコンパイラを作る。
• 作成したコンパイラで、コンパイラ自身をコンパイルする。
あるいは、まず、仕様の小さいコンパイラを作り、それにより、よ り大きな仕様の言語を作るということもある。C言語は、BやBCPLと いう言語から、そのように作られている。また、GNU Projectのgcc は、まず、そこにあるCでsub setをコンパイルして、そののち、そ のコンパイラでgcc自身をコンパイルして、full setを実現すると いう方法を取っている。

このような状況を記述する記法がある。



これは、インタプリタをコンパイラを表している。例えば、プリロセッサ を持つコンパイラは以下のように記述される。

インタプリタを持つコンパイラを自分でコンパイルする。

その言語自身が、その言語を実現するのに、どれくらい使われてい るかは、その言語を評価する一つの基準である。他の言語に依存す る度合いが大きい言語は、優れているとはいいがたい。