JavaScriptで自作言語インタープリタの作り方

自作言語やインタープリタの作り方の勉強。

書籍「[GO言語でつくるインタプリタ](https://www.oreilly.co.jp/books/9784873118222/)」で紹介されている、Monkey言語のインタープリタを作成します。

![6.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/70356/9dad65d7-142d-b962-aadf-a70aa386b1b4.png)


著者がGOのコードを[公開](https://interpreterbook.com/waiig_code_1.7.zip)していますが、読者によって様々な言語に移植されています。
今回は読者のコードを参考にJavaScriptで書いてみました。(本はまだ買ってない)

https://monkeylang.org/


## インタープリタ ＝ Lexer ＋ Parser ＋ Eval

|機能 |解説|
|:-:|:-|
|**Lexer**   |ソースコードを先頭から1文字ずつ読み込んで、プログラムとしての最小単位(**トークン**)に分解する|
|**Parser**   |トークンを先頭から1個ずつ読み込んで、プログラムとして意味のある単位(**ノード**)に組み立てる。ノードには**値**・**式**・**文**があり、1本のツリー(**AST**)を作る|
|**Eval**   |ASTを評価・実行する|

※ASTはHTMLに例えるとDOMみたいなもの


```js:インタープリタをコードで説明すると
function interpreter(code){
    const lexer = new Lexer(code)
    const ast   = new Parser(lexer).parse()
    return Eval(ast)
}
```
## ソースコード

| 機能 | 依存関係 | 難易度 |
|:-:|:-|:-|
|<a href="https://github.com/worldace/interpreter/blob/master/lexer.js" target="_blank">**lexer.js**</a>|<a href="https://github.com/worldace/interpreter/blob/master/token.js" target="_blank">token.js</a>   |★   |
|<a href="https://github.com/worldace/interpreter/blob/master/parser.js" target="_blank">**parser.js**</a>|<a href="https://github.com/worldace/interpreter/blob/master/lexer.js" target="_blank">lexer.js</a> <a href="https://github.com/worldace/interpreter/blob/master/token.js" target="_blank">token.js</a> <a href="https://github.com/worldace/interpreter/blob/master/ast.js" target="_blank">ast.js</a>|★★★   |
|<a href="https://github.com/worldace/interpreter/blob/master/eval.js" target="_blank">**eval.js**</a>|<a href="https://github.com/worldace/interpreter/blob/master/parser.js" target="_blank">parser.js</a> <a href="https://github.com/worldace/interpreter/blob/master/object.js" target="_blank">object.js</a> <a href="https://github.com/worldace/interpreter/blob/master/functions.js" target="_blank">functions.js</a>|★★   |


## 実行環境
https://worldace.github.io/interpreter/

JavaScript製なのでWebで実行できます。
開発者ツールのコンソールを開けば、トークン列とASTの内容を確認できます。

## 学習メモ
ソースコードを読むだけで理解できるように、できるだけ平易に書いてますが、根本的にインタープリタは難しいので限界もあります。

Prattパーサーと呼ばれるParser部の難易度が高い。特に``parseExpression()``の所。
どういう関数がどういう順番で実行されるのかログを取ったり、ASTを確認したりして、時間を掛けて体で覚えていくのが良いかと。

<!--
## Parserの優先度についての考察

``1+2``という式は、関数で書くと``plus(1,2)``となる。
この関数をHTMLタグで書くと次のようになる

```html
<call id="plus">
  <left>1</left>
  <right>2</right>
</call>
```

----

次に``1+2+3``について考える。
``1+2``(A)という式と``2+3``(B)という2つの式があると考える


```html
(A)
<call id="plus">
  <left>1</left>
  <right>2</right>
</call>

(B)
<call id="plus">
  <left>2</left>
  <right>3</right>
</call>
```

AとBの優先度は同じである。
AをB.leftに代入すれば正解が得られる

----
次に``1*2+3``について考える。
``1*2``(A)という式と``2+3``(B)という2つの式があると考える


```html
(A)
<call id="multi">
  <left>1</left>
  <right>2</right>
</call>

(B)
<call id="plus">
  <left>2</left>
  <right>3</right>
</call>
```

Aの方が優先度が高い。
AをB.leftに代入すれば正解が得られる

----
次に``1+2*3``について考える。
``1+2``(A)という式と``2*3``(B)という2つの式があると考える


```html
(A)
<call id="plus">
  <left>1</left>
  <right>2</right>
</call>

(B)
<call id="multi">
  <left>2</left>
  <right>3</right>
</call>
```

Bの方が優先度が高い。
BをA.rightに代入すれば正解が得られる

----



以上をまとめると、AとBの2つの式があった時

| 優先度 | 操作方法 |
|:-:|:-:|
|Bの方が優先度が高い|BをA.rightに代入|
|それ以外|AをB.leftに代入|

-->