Brainf ** kプログラムでメモリ配列が範囲外にアクセスされているかどうかを調べることはできますか？

Question

私はBFインタプリタをアセンブリで作成しましたが、今はアセンブリコードにコンパイルするJavaでBFコンパイラを作成しています。

メモリセルの配列が範囲外だったかどうかを検出するちょっとした機能を実装したかったのです。アレイの従来の制限は、インデックスを[0, 30000)にすることです。それ以外の場合は、[0, inf)もよく使用されます。もう1つの選択肢は、メモリがラップされるということです。最初のケースでは、インデックス30000にアクセスするとインデックス0にアクセスすることを意味する可能性があります。

私のコンパイラでは、この検出は従来のコンパイラのセマンティック解析フェーズで行われます。すでに構文解析段階からAST（抽象構文木）を取得しています。

私はDetecting infinite loop in brainfuck programとBFのウィキペディアのページを見つけましたが、メモリ配列[0, inf)と同じBFプログラムがチューリングマシンに似ていることが分かりました。

私の質問は、[0, max)と[0, inf)の両方のケースでは、メモリポインタがゼロ以下になるかどうかを検出できますか？明らかにそれをチェックしている間無限ループに終わることなく、最大実行時間を設定するのをやめてしまいます。

ボーナスの質問：ループ構成の回数を検出することは可能ですか[...]ループ？

Answer 1

BFはチューリング可能です。索引を使用して索引を計算すると、停止問題のために索引に特定の値（たとえば30001）があるかどうかを一般的に判断することはできません。だから一般的に、あなたは境界を越えたアクセスを検出することはできません。しかし、これを多くの個々のプログラムで検出できる可能性があります。理論的に役に立たないにもかかわらず、スタティック・アナライザが構築され、使用される理由です。

ループトリップ数について：ループ構成は、変数がゼロかどうかに基づいて動作します。 BFはチューリング可能であるということは、一般に、変数が特定の時点でゼロであるかどうかを知ることができないことを意味します。その意味は、ループ構造が動作する回数を知ることができないということです。繰り返しますが、多くの個々のプログラムでこれを理解することができます。

単純なケースのプログラムの中には、小切手を簡単に実装できるものがあります。一般に、これらの種類の静的解析を行うには、かなり多くの機械が必要です。