11

新しく作成したプログラミング言語で Brainfuck (くそったれ) インタープリターを構築して、それがチューリング完全であることを証明したいと考えています。

これで、これまでのところすべてが明らかです ( <>+-,.) - 1 つのことを除いて: ループ ( [])。ここからは、(非常に難しい) BF 構文を知っていると仮定します。

  • インタープリターで BF ループを実装するにはどうすればよいですか?

擬似コードはどのように見えるでしょうか? [インタープリターがループ開始 ( ) またはループ終了 ( )に到達した場合、どうすればよい]ですか?

ループを続行するか停止するかを確認することは問題ではありませんが ( current cell==0)、次のようになります。

  • いつ、どこで確認すればよいですか？
  • ループの開始位置を知る方法は?
  • ネストされたループを処理するには?

ループはネストできるので、現在のループの開始位置を含む変数を使用することはできないと思います。

私は、さまざまな言語で実装された非常に小さな BF インタープリターを見てきました。どうやってループを機能させたのだろうかと思いますが、それを理解することはできません。

4

5 に答える 5

9

に到達[したら、データ ポインタをテストします。

それが false の場合は、次の一致する ]文字をスキャンして、表示された文字数を数え、[各].

それが正しい場合は、後でジャンプして戻ることができるように、その位置を追跡する必要があります。スタックを使用することをお勧めします。現在のプログラム位置をスタックにプッシュし、 に到達したら]、データ ポインターをテストします。true の場合、スタックの最上位のプログラム位置に移動します。false の場合は、スタックからポジションをポップして続行します。

内部ループにネストすると、スタックは各ループのコンテキストを明確に記録します。

スタック (ウィキペディア)を参照してください。これは、アセンブリ プログラムが関数呼び出しを処理する方法に似ています。

于 2010-04-06T20:47:32.730 に答える
7

これが私の「最適化」バージョンのインタープリターで、ループジャンプをプリコンパイルします。

def interpret2(code):
    data = [0] * 5000   # data memory
    cp = 0              # code pointer
    dp = 0              # data pointer
    # pre-compile a jump table
    stack = []
    jump = [None] * len(code)
    for i,o in enumerate(code):
        if o=='[':
            stack.append(i)
        elif o==']':
            jump[i] = stack.pop()
            jump[jump[i]] = i
    # execute
    while cp < len(code):
        cmd = code[cp]
        if   cmd == '>': dp += 1
        elif cmd == '<': dp -= 1
        elif cmd == '+': data[dp] += 1 
        elif cmd == '-': data[dp] -= 1 
        elif cmd == '.': stdout.write(chr(data[dp]))
        elif cmd == ',': data[dp] = ord(stdin.read(1))
        elif cmd == '[' and not data[dp]: # skip loop if ==0
            cp = jump[cp]
        elif cmd == ']' and data[dp]:     # loop back if !=0
            cp = jump[cp]
        cp += 1

コードのドライランを実行し、（スタック内の）角かっこを追跡し、jump実行中に後で参照される並列配列でgotoアドレスをマークします。

[長時間実行されるBFプログラム（PiのN桁を計算）の実行速度を比較しました。これにより、ソースを前方にスキャンして終了し、後方にスキャンしてループする無害な実装と比較して、速度が2倍になりました]。

于 2010-06-14T21:15:29.723 に答える
2

インタプリタにBFループを実装するにはどうすればよいですか？

それがポイントです–それは完全にあなたの言語に依存します。スタックベースのプログラミング言語（またはスタックを使用できる任意の言語）の場合、@rjhが優れたソリューションを提供します。他の言語は、再帰（つまり、スタックの暗黙的な使用）などの異なるソリューションを使用します。

于 2010-04-06T20:51:32.183 に答える
1

私の頭の上から、いくつかのエラーがあるかもしれませんが、次のようなものはうまくいくはずです:

char* interpret(char* instructions){
  char* c = instructions;
  while (*c) {
    if (*c == ".") putchar(*p);
    else if (*c == ",") *p = getchar();
    else if (*c == '+') (*p)++;
    else if (*c == '-') (*p)--;
    else if (*c == '<') p--;
    else if (*c == '>') p++;
    else if (*c == '[') c = interpret(c+1);
    else if (*c == ']') { if (*p) c = instructions else return c; }
    c++;
  }
  return 0;
}

Brainf*ck ソース コードを使用して解釈を呼び出します。ポインタ p は現在のメモリ位置です。[ を見つけたら再帰呼び出しを行います。] に遭遇すると、この再帰呼び出しから戻ります。

于 2010-04-06T20:56:17.960 に答える
0

私はジャンプ テーブルを使用することを好みます (生の BF から「バイトコード」への変換と共に)。最適化された BF インタープリターは明らかに進むべき道です!

于 2010-05-31T16:01:50.950 に答える