問題タブ [brainfuck]

私は、MATLAB スクリプト言語で単純な頭のおかしいインタープリターを作成しました。(遺伝的アルゴリズム プロジェクトの一部として) 実行するランダムな bf プログラムが与えられます。私が直面している問題は、プログラムにかなりの数のケースで無限ループがあることが判明したため、GA がその時点で動かなくなることです。
したがって、無限ループを検出し、そのコードを bf で実行しないようにするメカニズムが必要です。
明らかな（些細な）ケースの1つは、私が持っている場合です

私はこれを検出し、そのプログラムの実行を拒否できます。
自明ではないケースについては、基本的な考え方は、ループの 1 回の反復で現在のセルがどのように変化するかを判断することであることがわかりました。変化が負の場合、最終的に 0 に到達するため、有限ループです。それ以外の場合、変化が負でない場合、それは無限ループです。
これを実装するのは、単一のループの場合は簡単ですが、ネストされたループでは非常に複雑になります。例えば ​​(以下の (1) はセル 1 の内容などを指します )

したがって、コードは何度も実行されます。ただし、セル 1 で行われた + と - の数の単純なチェックでは、- の数が多いと判断されるため、無限ループは検出されません。
bf で任意の数のループが任意にネストされている場合、無限ループを検出するための優れたアルゴリズムを考えられる人はいますか?

編集:停止の問題が一般的に解決できないことは知っていますが、特別なケースの例外が存在しないかどうかはわかりませんでした。同様に、Matlab は bf プログラムの停止を判断できるスーパー チューリング マシンとして機能するかもしれません。私はひどく間違っているかもしれませんが、もしそうなら、その方法と理由を正確に知りたいです.

2 番目の編集: 無限ループ検出器であると主張するものを書きました。おそらくいくつかのエッジケースを見逃しています（または、おそらくチューリング氏のクラッチから逃れる可能性は低いです）が、今のところ私にとってはうまくいくようです。疑似コード形式では、次のようになります。

私は Brainfuck 用のインタープリターの作成を実験してきました。作成と実行は非常に簡単ですが、それに対してテストを実行できるようにしたいと考えています。実装が適切であることを確認するために、考えられるすべての命令の組み合わせをテストするために、どれだけ多くのテストを作成する必要があるか、私にはわかりません。

明らかに、Brainfuck の命令セットは小さいですが、命令が追加されると、テスト コードが指数関数的に大きくなると思わずにはいられません。とにかく、典型的なテストよりもそうです。

さて、私はコンパイラーとインタープリターを書くという点であなたが得ることができるのと同じくらい初心者なので、私の仮定はかなり間違っている可能性があります.

基本的に、このようなもののテストはどこから始めますか?

私はオンラインbrainfuckインタープリターを書きました..!! 問題は、テキスト入力を取得すると、エラーが発生することです!!... HTTP 応答が大きすぎました: 10485810。制限は: 10485760 です。

gae の最大制限は 1MB のようです。どうすれば回避できますか !1

私は最終的にインタプリタを作成するためにBrainfuckパーサーを（BASIC方言で）作成していますが、最初に思ったほど簡単ではないことに気づきました。私の問題は、Brainfuckプログラム内で一致するループ演算子を正確に解析する方法が必要なことです。これはサンプルプログラムです：

'['=ループの開始

']'=ループの終わり

必要に応じてソースをジャンプできるように、一致する各ループ演算子の開始点と終了点を記録する必要があります。一部のループは単独で、一部はネストされています。

これを解析するための最良の方法は何でしょうか？ソースファイルを移動して、一致する各演算子の開始位置と終了位置を記録する2D配列（など）を作成することを考えていましたが、これはソースを「行き来する」ことが多いようです。これはそれを行うための最良の方法ですか？

詳細：Brainfuckホームページ

編集：どの言語のサンプルコードでも大歓迎です。

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

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

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

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

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

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

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

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

'~' は Python で何を意味しますか?

少し前にPythonでこのBFインタープリターを見つけました。

ti 84（およびPF 1）で作成したいので、それが何をするのか知りたいです

BF はhttp://en.wikipedia.org/wiki/Brainfuck で、PF は似たようなものです

私は、brainfuckで大きな整数に対して算術演算を実行することは、おそらくかなり退屈なことですが、完全に可能であることを知っています。

ただし、私が疑問に思っているのは、一般的に受け入れられているベストプラクティスは、大きな整数（または文字列でさえも）を入力として取り込むことです。

ほとんどのコンパイラ/インタプリタでは、入力として一度に完全な文字列を提供できます（その後、各文字はで個別に読み込まれます,）。しかし、私が疑問に思っているのは、これです。入力ストリームがいつ停止するかわからない場合、どのように読み取ることができますか？1つの方法は、特定の文字/文字列を番号に追加して、それが終わったことを示すようにユーザーに指示することだと思いますが、それは少しユーザーフレンドリーではないようです。

移植性を念頭に置いた回答を希望します（実装固有のソリューションに関心がありますが、この質問の主な焦点ではありません）。これを行うための完全に実装にとらわれない方法がない場合、ほとんどの実装で機能し、そうでなければ正常に失敗する方法が次善の策です。

前もって感謝します。

初心者のために説明すると、Brainfuckは 8 つのコマンドしかないチューリング完全言語であり、そのすべてが C で文字どおり同等のものを持っています。

パッケージマネージャーを備えたLinuxディストリビューションでは、Brainfuckインタープリターであるパッケージを見つけてインストールできるはずbeefなので、自宅で遊ぶことができます.

上記のように、Brainfuck には1 つの制御構造しかなく[…]、C に次のように変換されます。

IF VAR = 0 THEN GOTO 10これにより、BASIC からのすべての制御が可能になります。getchar()以下は、返されるまで呼び出します0:

しかし、改行文字だけを読みたい場合はどうすればよい\nでしょうか? これを単純に機能させる方法について頭を悩ますのに苦労ifした後、次のことを思いつきました。

(他に良い方法があれば教えてください)

\rに加えて、そのループから抜け出すことをテストしたいとしましょう\n。ループから抜け出す機会が 1 回しかない場合、どうすればどちらかをテストできますか? switch私の目標は、ネストされたifs またはsをエミュレートできるようにすることif/else ifです。

この小さな関数は、(有限の) Brainfuck 文字列の有効性をチェックします。[とのバランスが取れているかどうかをチェックし]ます。コードは非常に単純で、末尾再帰的に記述されています。

現在、GHC は型付けの問題について不平を言っています。

何がうまくいかなかったのかを理解するには私が愚かすぎるのかもしれませんが、これは私にとって非常に奇妙に見えます。