はじめに
これは拓殖大学ディジタルコンテンツ研究愛好会 Advent Calendar 2019 2日目の記事です。
追記(2019/12/05)：コードに一部誤りがあることが分かりました。
指摘していただいたfujitanozomuさんありがとうございます！
アルゴリズムとデータ構造の勉強の一環として、Brainf*ckを書けないのにJavaScriptでBrainf*ckのインタプリタを実装しました。せっかくなのでアドベントカレンダーの記事としてアウトプットしようと思います。
【注意】今回は入力 , を実装しません
参考
仕様
>ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。<ポインタをデクリメントする。C言語の「ptr--;」に相当。+ポインタが指す値をインクリメントする。C言語の「(*ptr)++;」に相当。-ポインタが指す値をデクリメントする。C言語の「(*ptr)--;」に相当。.ポインタが指す値を出力に書き出す。C言語の「putchar(*ptr);」に相当。,入力から1バイト読み込んで、ポインタが指す先に代入する。C言語の「*ptr=getchar();」に相当。[ポインタが指す値が0なら、対応する ] の直後にジャンプする。C言語の「while(*ptr){」に相当。]ポインタが指す値が0でないなら、対応する [ （の直後[1]）にジャンプする。C言語の「}」に相当。
Wikipediaより参照
コードの全容
再度書いておきますが、今回は入力 , を実装しません
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にもあげてあります。
解説
軽くですが、説明します。
準備
-
input = input.split("");入ってきたコマンドを一文字ずつに区切って配列にしています。 -
let output = "";.で出てくる文字を格納します。 -
let ptr = 0;ポインタの役割をします。 -
let data = [0, null];文字コードとなる数字を格納します。番兵としてnullを最後に入れます。これでコマンドを可変にします。ついでに可変三連とガチ恋口上、ホグワーツMIXも抑えましょう。(なんで？) -
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のインタプリタを実装してみた。を参考にしてみてください。
[]
ここが難しいんですよね。準備のところで分かった方も多いと思いますが、スタックを使って実装します。
分からなくてもスタックかLIFOでググれば出ます。
まずはポインタの指す値が0でないときを考えます。
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 が活きてきます。
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 の前に以下のコードを書きます。
if(skipCounter != 0 && /[^\[\]]/.test(input[i])){
// ptr++; // 変更ポイント
continue;
}
switch(input[i]){
case ">":
・
・
・
こうすることで skipCounter が溜まっているときは []以外評価されなくなります。
[] は正規表現を使って/[^\[\]]/.test(input[i]) と書いて透かしてします。
^は/[]/内に書くとnotになります。(参考：基本的な正規表現一覧)
以上で述べた通り、 [] 以外は評価する必要ないので continue で switch 内を見ずに次へ回します。
brainf*ckのコード例
Hello, world!
+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+.
ABC
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+.+.>++++++++++.
0123456789
++++++[>++++++++<-]++++++++++[>.+<-]
const command = ""; に文字列として渡して実行すると表示されると思います。
おわりに
お疲れさまでした。
他の 拓殖大学ディジタルコンテンツ研究愛好会 Advent Calendar 2019 もよろしくお願いします。