JavaScriptでbrainfuckのインタプリタを実装した

# はじめに
これは[拓殖大学ディジタルコンテンツ研究愛好会 Advent Calendar 2019 2日目](https://adventar.org/calendars/4622)の記事です。

追記(2019/12/05)：コードに一部誤りがあることが分かりました。
指摘していただいたfujitanozomuさんありがとうございます！

アルゴリズムとデータ構造の勉強の一環として、~~Brainf*ckを書けないのに~~JavaScriptでBrainf*ckのインタプリタを実装しました。せっかくなのでアドベントカレンダーの記事としてアウトプットしようと思います。

【注意】**今回は入力 `,` を実装しません**

# 参考

- [Brainfuck-Wikipedia](https://ja.wikipedia.org/wiki/Brainfuck)
- [Brainfuckとは-ニコニコ大百科](https://dic.nicovideo.jp/a/brainfuck)
- [brainfuck-visualizer](https://fatiherikli.github.io/brainfuck-visualizer/)
- [JavascriptでBrainfuckのインタプリタを実装してみた。](https://techblog.kayac.com/js-brainfuck.html)

# 仕様

> - `>` ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。
> - `<` ポインタをデクリメントする。C言語の「ptr--;」に相当。
> - `+` ポインタが指す値をインクリメントする。C言語の「(*ptr)++;」に相当。
> - `-` ポインタが指す値をデクリメントする。C言語の「(*ptr)--;」に相当。
> - `.` ポインタが指す値を出力に書き出す。C言語の「putchar(*ptr);」に相当。
> - `,` 入力から1バイト読み込んで、ポインタが指す先に代入する。C言語の「*ptr=getchar();」に相当。
> - `[` ポインタが指す値が0なら、対応する ] の直後にジャンプする。C言語の「while(*ptr){」に相当。
> - `]` ポインタが指す値が0でないなら、対応する [ （の直後[1]）にジャンプする。C言語の「}」に相当。

[Wikipedia](https://ja.wikipedia.org/wiki/Brainfuck)より参照

# コードの全容

再度書いておきますが、**今回は入力 `,` を実装しません**

```javascript
function main(input){
    input = input.split("");
    let output = "";
    let ptr = 0;
    let data = [0, null];
    let bracketIndex = [];
    let skipCounter = 0

    for(let i = 0;i < input.length;i++){
        if(skipCounter != 0 && /[^\[\]]/.test(input[i])){
            // ptr++; // 変更ポイント
            continue;
        }
        switch(input[i]){
            case ">":
                ptr++;
                if(data[ptr] == null){
                    data[ptr] = 0;
                    data.push(null);
                }
                break;
            case "<":
                ptr--;
                break;
            case "+":
                data[ptr] += 1;
                break;
            case "-":
                data[ptr] -= 1;
                break;
            case ".":
                output += String.fromCharCode(data[ptr]);
                break;
            case "[":
                if(data[ptr] != 0){
                    bracketIndex.push(i);
                }else{
                    skipCounter++;
                }
                break;
            case "]":
                if(data[ptr] != 0){
                    i = bracketIndex.pop()-1;
                }else{
                    if(skipCounter == 0){
                        bracketIndex.pop();
                    }else{
                        skipCounter--;
                    }
                }
                break;
        }
    }
    console.log(output);
}

const command = ""; // ここにbrainf*ckのコードを入れる

main(command);
```

[github](https://github.com/masayasviel/algorithmAndDataStructure/blob/master/study_algorithm/brainfuck.js)にもあげてあります。

# 解説

軽くですが、説明します。

## 準備

- `input = input.split("");` 入ってきたコマンドを一文字ずつに区切って配列にしています。
- `let output = "";` `.`で出てくる文字を格納します。
- `let ptr = 0;` ポインタの役割をします。
- `let data = [0, null];` 文字コードとなる数字を格納します。番兵として`null`を最後に入れます。これでコマンドを可変にします。ついでに[可変三連](https://xn--nzwp98desh.com/2018/08/22/post-1304/)と[ガチ恋口上](https://xn--nzwp98desh.com/2019/01/06/post-1741/#toc_id_6)、[ホグワーツMIX](https://xn--nzwp98desh.com/2019/06/30/post-2510/)も抑えましょう。(なんで？)
- `let bracketIndex = [];` ポインタの指す値が0でないとき`[`のインデックスをpushします。対応する`]`がきたとき、ポインタの指す値が0でなければpopします。
- `let skipCounter = 0` ポインタの指す値が0でないとき`[`の対応する`]`まで飛ぶためのカウンタです。

## 実装

`for(let i = 0;i < input.length;i++){}`
この中でループして、コマンドの最後まで舐めます。`in`や`of`、`foreach`、`map`などを使っていないのには理由があります。(whileのほうがよかったかも)

`+-><.`
以上5つについては、[JavascriptでBrainfuckのインタプリタを実装してみた。](https://techblog.kayac.com/js-brainfuck.html)を参考にしてみてください。

`[]`
ここが難しいんですよね。準備のところで分かった方も多いと思いますが、スタックを使って実装します。
分からなくてもスタックかLIFOでググれば出ます。

まずはポインタの指す値が0でないときを考えます。

```javascript
case "[":
  if(data[ptr] != 0){
    bracketIndex.push(i);
  break;
case "]":
  if(data[ptr] != 0){
    i = bracketIndex.pop()-1;
  }
  break;
```

`[` がきたらそのインデックスをpush、 `]` がきたらpopしてループで使っている変数 `i` に代入します。これで対応する `[` まで戻れるわけですね。
`for(let i = 0;i < input.length;i++)` より、インクリメントされてしまい `-1` しないとズレるため注意が必要です。

次はポインタの指す値が0だった場合を考えます。
ここで `skipCounter` が活きてきます。

```javascript
case "[":
  if(data[ptr] != 0){
    bracketIndex.push(i);
  }else{
    skipCounter++;
  }
  break;
case "]":
  if(data[ptr] != 0){
    i = bracketIndex.pop()-1;
  }else{
    if(skipCounter == 0){
      bracketIndex.pop();
    }else{
      skipCounter--;
    }
  }
  break;
```

`[` のときポインタの指す値が0ならば `skipCounter` を増やします。
`]` のときポインタの指す値が0ならば、`skipCounter` が0でなければ減らし、0ならばpopします。

しかしこれだけではまだ問題があります。`[]`がきたときは評価されなくなったとはいえ、それ以外のコマンドがきたときは評価されてしまいます。

そこで、`switch` の前に以下のコードを書きます。

```javascript
if(skipCounter != 0 && /[^\[\]]/.test(input[i])){
  // ptr++; // 変更ポイント
  continue;
}
switch(input[i]){
  case ">":
  ・
  ・
  ・
```

こうすることで `skipCounter` が溜まっているときは `[]`以外評価されなくなります。
`[]` は正規表現を使って`/[^\[\]]/.test(input[i])` と書いて透かしてします。
`^`は`/[]/`内に書くとnotになります。(参考：[基本的な正規表現一覧](https://murashun.jp/blog/20190215-01.html))

以上で述べた通り、 `[]` 以外は評価する必要ないので `continue` で `switch` 内を見ずに次へ回します。

# brainf*ckのコード例

```
Hello, world!
+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+.

ABC
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+.+.>++++++++++.

0123456789
++++++[>++++++++<-]++++++++++[>.+<-]
```

`const command = "";` に文字列として渡して実行すると表示されると思います。

# おわりに

お疲れさまでした。

他の [拓殖大学ディジタルコンテンツ研究愛好会 Advent Calendar 2019](https://adventar.org/calendars/4622) もよろしくお願いします。

[終わりだよ～](https://ameblo.jp/asakuramomoblog/)