Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
6
Help us understand the problem. What is going on with this article?
@gatayama

JavaScriptでBrainF*ckインタプリタを実装する

More than 5 years have passed since last update.

ニジボックスAdvent Calendar 2015 16日目の記事です。

BrainF*ckとは

BrainF*ckとは難解言語の一種で、下記の8つの実行可能な命令を持っている言語です。
1. > ポインタをインクリメントする
2. < ポインタをデクリメントする
3. + ポインタが指す値をインクリメントする
4. - ポインタが指す値をデクリメントする
5. . ポインタが指す値を出力する
6. , 入力から1バイト読み込んで、ポインタが指す先に代入する
7. [ ポインタが指す値が0なら対応する]の直後にジャンプする
8. ] ポインタが指す値が0以外なら対応する[の直後にジャンプする
以上Wikipedia先生から抜粋。

やたらとポインタと言う単語が出てきており、学生時代にC言語にいじめられた自分としては今すぐブラウザを閉じてお家へ帰りたいところではありますが、
折角なので、JavaScriptでBFのインタプリタを実装して、アドレスとその中の数値の動きを視覚的に見られるようにしてみましょう。

実装

まず実際の数値を入れる配列とその配列のキー(ポインタ)がどこかを示す変数が必要になります。
また、BFのソースコードのどこを読んでいるかを示すプログラムカウンタが必要です。
ブラウザから受け取るソースと出力用の変数も書いておきます。

var mem = [];
var ptr = 0;
var pc = 0;
var source = "input";
var result = "";

受取りの細かい部分は割愛して、BFの言語仕様を1つずつ実装していきます。
以下の処理をソースの読み込みが終わるまで繰り返します。

var c = source.substring(pc, pc+1);    //1文字取得
pc++;                                  //プログラムカウンタをインクリメント
switch(c){
}

簡単に実装できそうな値の加減算から

case '>':pt++; break;
case '<':pt--; break;
case '+':mem[pt]++; break;
case '-':mem[pt]--; break;

BFの出力はC言語でいうputcharと同じ動きのため、こちらもそのまま実装します。
入力はブラウザから行っているため実装しません。

case '.':result += String.fromCharCode(mem[pt]); break;

そして繰り返し処理につかうジャンプ命令を実装します。
処理自体は単純で、プログラムカウンタを増やし(減らし)ながら、対応するジャンプ命令を検知し、その時点のカウンタより1大きい数をプログラムカウンタに代入します。

この時に注意が必要なのは、ジャンプ命令のネストがあった場合に、単純に対応する命令を検知するだけでは正しく動作しないことです。

そのため、処理している命令と同種のジャンプ命令があった場合その数をカウントしておき、対応するジャンプ命令があった時にカウンタが0だったらループから抜けるようにします。

case '[':
    if(mem[pt] == 0){
        var count = 0;
        for(var i = pc; i < source.length; i++){
            if(source.substring(i, i + 1) == '['){
                count++;
            }
            if(source.substring(i, i + 1) == ']'){
                if(count == 0){
                    break;
                }
                count--;
            }
        }
        pc = i + 1;
    }
    break;
case ']':
    if(mem[pt] != 0){
        var count = 0;
        for(var i = pc - 2; i >= 0; i--){
            if(source.substring(i, i + 1) == ']'){
                count++;
            }
            if(source.substring(i, i + 1) == '['){
                if(count == 0){
                    break;
                }
        count--;
            }
        }
        pc = i;
    }
    break;

以上で一通りの機能実装が完了です。
あとはフロント側で見た目を整えたり、アドレスや数値の流れを追いやすいようにスリープやステップ実行を好みで付けてこうなりました。

bf_before.jpg

Runボタンを押すことで緑色のプログラムカウンタがソース上を読み取っていき、出力命令があった場合はresultに出力されます。
また今どこのメモリを指しているかはピンクの網掛けで表しています。

途中経過。
bf_run.jpg

無事、ハロワが表示されました。
bf_after.jpg

終わりに

今回、本当はGCPのCloudVisionの記事を書くつもりだったのですが、Googleの審査が間に合わずファ〇ク!ファ〇ク!と言っていたらこのネタ記事が出来上がりました。
審査が通ったら、笑わせた福沢諭吉を認識するか遊んでみたいと思っています。

6
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
gatayama

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
6
Help us understand the problem. What is going on with this article?