ﾑﾑｯ！あなた，言語処理系に興味を持ってそうな顔をしてますね！？僕もそうなんですよ，奇遇ですね．お友達になりませんか？
これはなに
この記事を読み終える頃には一つの超簡単な言語処理系が出来てます．できることは
- 四則演算(整数のみ)
これだけです．言語処理系を謳ってる割にはかなりショボいですが，内容はちゃんとあるので許してほしいです．そして記事が長すぎると読む気も失せちゃうと思うので分けました．
あとこれはC++で実装します．他言語で実装したいという人は面倒だとは思いますが自分で翻訳して下さい．
もくじ(？)
予定ですが，0日目が前置き(だいたいの説明)，1日目が字句解析器と構文解析器の実装，2日目が実行コード生成とそれを元に動作するVMの実装を行います．ちなみに今僕は試験期間中です．もし更新が遅れても優しくして下さい．
実行までの流れ
インタプリタがソースコードを受け取って実行されるまで
ソースコード → 字句解析 → 字句 → 構文解析 → 抽象構文木(AST) → 評価
または
ソースコード → 字句解析 → 字句 → 構文解析 → 抽象構文木(AST) → 実行コード生成 → 実行コード → VM
のような道を辿っています．PythonやRubyなどメジャーなプログラミング言語は大抵下のやり方を採用しています．僕もそれに便乗して今回は下のやり方で実装していこうと思います．
と，その前にそれぞれの言葉の説明からやっていきます．(「そんなこと知ってるぞタコ」という方は読み飛ばして下さい)
字句解析
以下のようなソースコードがあるとしましょう．
1 * 2 + 3 * 4 * 5
こいつを後々処理しやすくするため，最小単位の字句(トークン)に分けます．これが字句解析です．
字句解析したものがこちらになります．
Number( 1 )
Symbol( * )
Number( 2 )
Symbol( + )
Number( 3 )
Symbol( * )
Number( 4 )
Symbol( * )
Number( 5 )
数はNumber，演算子はSymbolなど，そのトークンの種類もここではっきりさせておきます．こいつらは次の構文解析で使います．
構文解析
先程の工程であられもない姿になってしまったソースコードくんですが，さらに手を加えて行きます．
+
/ \
* *
/ \ / \
1 2 3 *
/ \
4 5
...？
もう元のソースコードくんの姿はありません．どういうことなのでしょうか．
構文木
プログラムの構造をそのまま木構造で表現したものを構文木といいます．
今回のソースコードでは含まれませんが，一般的なプログラミング言語で出現してくるトークンには(;や(, )など)不必要なものも含まれています．それらを全て取り除いたものが抽象構文木(AST)です．
この構文解析で演算子の優先順位なども表現しちゃいます．(上のASTを木の端から辿ってみて下さい．演算子の優先順位(+ < *)が表現できていることが分かると思います．)
このASTは次の実行コード生成で使います．
実行コード生成
ここでコンピュータが理解できる言語を先程できたASTを辿って生成します．今回はVM(仮想機械)で動かすので，それ用の実行コードを生成します．
push 1
push 2
mul
push 3
push 4
mul
push 5
mul
add
なんとなんと1 * 2 + 3 * 4 * 5が，今回作っていくVM用の実行コードに化けてしまいました．
次にこのコードをVMで実行します．
スタックマシン型VM
VMにはレジスタマシンとスタックマシンの2種類があります．今回はスタックマシン型VMを採用しました(実装が楽)．
スタックってなんだよ
スタックとはデータ構造の一つで，後に入れたものが先に出るようになっています．先に入れたものを先に出すキューというデータ構造も存在しますが，今回はその話は置いときます．
突然ですが，ハンバーガーを作りましょう．俺はチーズバーガーが好きです．
ハンバーガーの一番下にはまあバンズでしょう．ということでバンズを置きます．
_________
|__バンズ__|
まあ次は大体野菜系でしょう，というわけでトマトでも乗っけます．
_________
|__トマト__|
|__バンズ__|
まあなんと四角いトマトですが，そこは置いといて．同じノリでレタスも乗っけます．
_________
|__レタス__|
|__トマト__|
|__バンズ__|
もう野菜はこりごりなので肉行きましょう．人生肉ですよ肉．
|____肉___|
|__レタス__|
|__トマト__|
|__バンズ__|
っとここで客からクレームが入ります．「俺トマト無理だからどうにかしてよ！」
今こんなことをしてはTwitterにアップされては拡散されてしまいますが，そんなことはどうでもよくて．
うまくトマトだけを抜こうとしても形が崩れてまたケチをつけられてしまいます．なので上から順々に肉・レタスと取り除いていくしかありません．
ここで先程の動作を思い出して下さい．肉は一番最後に載せました．なのに，一番最初に取り除かれてしまいます．なんと世知辛い．
そう，これがスタックです．これが後入れ先出しです．
ちなみにキューでは下のバンズから取り除いていきます．一番最初に載せたものを一番最初に取り除く先入れ先出しです．
...こんな説明のためだけにこんなスペース取ってんじゃねえよ❗って感じですが，そこは多めに見て下さい．これがやりたかった
実際にシミュレーションしよう
スタックの説明を終えたとこで，スタックマシンに話を戻します．先程出した
push 1
push 2
mul
push 3
push 4
mul
push 5
mul
add
この実行コードをスタックに積んだり取ったりして実際に実行してみましょう．
最初の二行を実行します．pushはスタックに物を積む命令です．
するとスタックはこんな感じになります．
|__2__|
|__1__|
次のmul命令で，スタックから2つの値をpopして(取り出して)掛けた結果をスタックにpushします．1 * 2 = 2なので，
|__2__|
スタックはこのようになりますね．その次の２つの命令を実行すると，スタックは
|__4__|
|__3__|
|__2__|
ですね．さらにその次のmul命令でスタックは
|__12_|
|__2__|
になります.push 5をして
|__5__|
|__12_|
|__2__|
mul命令を実行すると
|__60_|
|__2__|
そして最後にadd命令(mul命令での掛け算が足し算に置き換わっただけ)を実行すると，
|__62_|
スタックの一番上に1 * 2 + 3 * 4 * 5の計算結果が残る，というわけです．コンピュータはこのように計算しているのです．
この記事ではこのような動作をするVMを実装します．
おわりに
今からこんなことをするのか〜という雰囲気をつかめて頂けたでしょうか．さて，1日目からは本格的に実装に入っていきます．
お疲れ様でした．
この他参考になるリンク集
・コンパイラの仕組みをサルでもわかるように説明する
・低レイヤを知りたい人のためのCコンパイラ作成入門
・高階関数を持つ言語に対するスタックベースのVM型処理系の実装
・Pythonの処理系はどのように実装され，どのように動いているのか？ 我々はその実態を調査すべくアマゾンへと飛んだ．