コンパイラとは

まずは、コンパイラとは何かを明確にしておきましょう。(とは言ってもWikipediaからですが..)

コンパイラとは、いわゆる「プログラミング言語」（＝人間が理解しやすい言語や数式でプログラムを記述可能な人工言語）で書かれたプログラムを、コンピュータ（のCPU）が直接的に実行できる機械語（あるいは、元のプログラムよりも低いレベルのコード。たとえばバイトコードなどの中間言語）に変換するプログラムのことである。

コンパイラは、人間が直接使うには厄介な機械語や中間言語を、いわゆるプログラミング言語から代わりに生成してくれます。自然言語で言えば、通訳者としての役割を果たしていますね。

コンパイラの基本構造

プログラミング言語は大きく分けると 字句解析 構文解析 意味解析 コード生成 という4つのフェーズを経てより低レベルなコードへと変換されていきます。
順に見ていきましょう。

字句解析

字句解析とは、ソースコードを意味の分かる最小単位ごとに分けていくことです。これは、例を見たほうがわかりやすいでしょう。
例えば、ここにCで書かれたコードがあるとします:

int main() {
  puts("hello world");
}

字句解析をすると以下のようなデータになります:

identifier: int
identifier: main
  symbol  : (
  symbol  : )
  symbol  : {
identifier: puts
  symbol  : (
  string  : hello world
  symbol  : )
  symbol  : ;
  symbol  : }

コードが int や ( などに分解されました。このそれぞれのことをトークンと呼びます。
トークンには、そのトークンが何を表しているかのデータが付属していることもあります。identifier や symbol などがそれです。どんなコンパイラを作るかによっては、これらのデータはもうちょっと細かく分類されたりします。
これは構文解析の時に役に立ちます。

以上のように、字句解析ではソースコードを細かく分けていきます。
わかりにくかったら、ちょうど国語の時間に文章を文節や単語ごとに分けていた時のことを思い出すといいでしょう。

構文解析

構文解析とは、字句解析でできたトークンをもとに、意味のわかる形式(e.g. AST(Abstract Syntax Tree)) に変換することを言います。
ここでは特にASTへの変換についてみていきます。

こちらもサンプルを見ていきましょう。さっき登場したトークン列を使用します:

identifier: int
identifier: main
  symbol  : (
  symbol  : )
  symbol  : {
identifier: puts
  symbol  : (
  string  : hello world
  symbol  : )
  symbol  : ;
  symbol  : }

今回はこれらをASTに変換してみましょう(中間コードでも考え方は同じはず)。
ここでは、ASTをS式で表します。

まず、このコードは関数定義を表しています。よって、関数定義を表すASTが出来上がれば良いはずです。

(func-def)

関数を作るには、返り値の型、名前、引数、中身などのデータが必要です。

(func-def (type int) main () (
  (func-call puts "hello world")
                             )
)

ASTは抽象構文木という名前から分かる通り、トークン列よりも抽象的になっています。カッコやセミコロンの類は消えてなくなり、(type int) など、見るだけで何を表しているかすぐにわかります（これは具体的?).

と、唐突にASTが完成しましたが、これだけでは何が起きたのかわかりませんね。
まずはトークン列が関数定義を表していることをしらなければなりません。

人間なら、int -> main -> ( -> )-> { と見ていきながら、最後の中括弧を見たところで、関数定義だと確信することができます。中括弧を見るまでは、プロトタイプと見分けがつきませんからね。
コンピューターも人間と同じように(いろんな方法がありますが普通は)トークンを前から見ていきながら、{ を見つけたところで関数定義だと確信します。

sorry coming soon

コンパイラ作り入門

コンパイラとは

コンパイラの基本構造

字句解析

構文解析