Brainfuckのインタープリタを作ろう(2)

過去のブログのアーカイブ
この記事は前身のブログのアーカイブを引き継いだものです. 画像が正しく表示できないなど,コンテンツの表示に問題がある恐れがあります.

前回は基本的な命令の実装を一通り行いました。今回はループ処理の追加です。

Brainfuckのインタープリタを作ろう(1)

2018.05.31

ループ処理のおさらい

Brainfuck(以下「BF」)のループ処理は少々厄介です。ループの挙動に置いておさらいして起きましょう。

  • ループ開始時点でメモリの値が0ならばそのループの中は実行しない
  • メモリの値が0になるまでループを繰り返す

です。ここでキモとなるのがループ開始時点でメモリの値が0ならそのループは全てスキップする必要があるところです。
それでは実装していきたいと思います。

実装していこう

変数を用意する

ループ終了時が0ではない場合、ループ開始の場所まで戻らないといけません。なので、ループを開始した場所の記録するための配列が必要になります。
というわけで新たにループの位置を記録するloop配列、今どこのループなのか記録するl_pointer、そしてループ開始時点で0の場合、中身を全てスキップしないといけないのでloopskip変数を作りましょう。

int[] loop = new int[20];
int l_pointer = 0;
int skipcount = 0;

これだけあればループを実装することができます。

まずは基本的なところを実装していく

ループをスキップするパターンは一旦後回しで、とりあえず実装しましょう。

// [命令
loop[l_pointer] = i;
l_pointer;

ループの開始はとても単純で、loop配列に現在の読込位置を入れたらいいだけです。
問題はループの終了の場合で、0の場合、0ではない場合で条件分岐をしてあげる必要があります。

if (memory[pointer] == 0)
    l_pointer--;
else
    i = loop[l_pointer - 1];

もし0ではない場合、またループをしないといけないので読込位置をループ開始位置に移動してあげないといけません。(elseの部分ですね)
そして0の場合は読込位置は操作せず、そのままスルーしてあげるだけでいいです。ただl_pointerの位置は元に戻してあげましょう。

とりあえず実行してみよう

これでループ処理は表面上完成です。さっそくHello World!を実行してみましょう。

>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>++++++++[<++++>-]<+.[-]++++++++++.
引用: http://www.kmonos.net/alang/etc/brainfuck.php

Hello World!と表示されたでしょうか。

ループのスキップ処理

次にループのスキップ処理を実装してみましょう。ループの開始時点で0の場合、ループの中身は実行せずにスキップしてあげる必要があります。ここでの注意点として、ループの中にループが入っている可能性もあります。その場合、ループの中のループもスキップしてあげる必要があります。
それでは実装していきましょう。[命令を改造します。

if (memory[pointer] == 0)
{
    skipcount++;
}
else
{
    loop[l_pointer] = i;
    l_pointer++;
}

これでメモリの値が0だった場合、skipcountを1増やします。そしてこのskipcountが1以上である場合、ループ終了の]がくるまでずっとスキップし続けます。
スキップ処理をswitch文の前に描いてあげましょう。

if (skipcount >= 1)
{
    if (c == '[') skipcount++;
    else if (c == ']') skipcount--;
    continue;
}

skipcountが1以上の場合、それ以降のコードはswitch文にいかないようcontinueしてあげます。
そして、ループの中にループがあった場合([があった場合)、skipcountをさらに+1します。そしてループ終了]があった場合、skipcountを-1します。
skipcountが0になった場合、このif文の中に行かないようになるというわけです。

実行してみよう

>++++++++++[-<++++++++++>]<--->[<+++>]<.

これでaと表示されたら成功です。スキップ実装する前のコードだとdが表示されるんじゃないかなと思います。

まとめ

BFでは、ループの開始の時、メモリの値が0ならばループの中身は実行されない。という仕様がありました。ということは、これを利用することで条件分岐も実装することができるわけです。
その辺について気になる方はこのあたりとか面白いのではないでしょうか。他にもBFで短いコードを実現するBrainfuck Goldというものもあります。
非常に難解な言語としてもはや世界的に有名な言語であるBrainfuck、ぜひ極めて見てはいかがでしょうか。