2日で作る電卓インタプリタ[0日目]

[1日目はこちらから](https://qiita.com/admarimoin/items/1079c698dc488ffdde9b)
[2日目はこちらから](https://qiita.com/admarimoin/items/fd83e71e36dd9de12196)


ﾑﾑｯ！あなた，言語処理系に興味を持ってそうな顔をしてますね！？僕もそうなんですよ，奇遇ですね．お友達になりませんか？

# これはなに
この記事を読み終える頃には一つの超簡単な言語処理系が出来てます．できることは

- 四則演算(整数のみ)

これだけです．言語処理系を謳ってる割にはかなりショボいですが，内容はちゃんとあるので許してほしいです．そして記事が長すぎると読む気も失せちゃうと思うので分けました．
あとこれは**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日目からは本格的に実装に入っていきます．

お疲れ様でした．

# この他参考になるリンク集
・[コンパイラの仕組みをサルでもわかるように説明する](http://www.ituore.com/entry/compiler)
・[低レイヤを知りたい人のためのCコンパイラ作成入門](https://www.sigbus.info/compilerbook/)
・[高階関数を持つ言語に対するスタックベースのVM型処理系の実装](https://alpha-kai-net.info/info_sp_2018/report.pdf)
・[Pythonの処理系はどのように実装され，どのように動いているのか？ 我々はその実態を調査すべくアマゾンへと飛んだ．](https://www.slideshare.net/utgw/python-73389442)