1

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

メモリ セルの配列が範囲外かどうかを検出するちょっとした便利な機能を実装したかったのです。配列の従来の制限は、インデックスを in[0, 30000)にすることでした。それ以外の場合[0, inf)も一般的に使用されます。もう 1 つのオプションは、メモリをラップアラウンドすることです。したがって、最初のケースでは、インデックス 30000 へのアクセスはインデックス 0 へのアクセスを意味する可能性があります。

私のコンパイラでは、この検出は従来のコンパイラのセマンティック分析フェーズで行われるため、構文分析フェーズから AST (抽象構文ツリー) を既に取得しています。

しばらくの間、このための構造を考え出そうとした後、私はDetecting infinite loop inbrainfuck programを見つけました.BFのウィキペディアページと一緒に、メモリ配列としてのBFプログラムが[0, inf)チューリングマシンに似ていることがわかりました.

だから私の質問は、[0, max)と[0, inf)ケースの両方で、メモリポインターがゼロを下回ったかどうか、前者の場合は最大を下回ったかどうかを検出することは可能ですか? 明らかに、チェック中に無限ループに陥ることはありません。また、最大実行時間の設定も避けたいと思います。

おまけの質問: ループ構造[...]がループする回数を検出することは可能ですか?

4

1 に答える 1

3

BF はチューリング可能です。これを使用してインデックスを計算する場合、通常、停止の問題により、インデックスが特定の値 (30001 など) を持っているかどうかを判断できません。したがって、一般に、境界外アクセスを検出することはできません。ただし、多くの個々のプログラムでこれを検出できる場合があります。これが、理論的には役に立たないにもかかわらず、静的アナライザーが構築され、使用される理由です。

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

単純なケースの一部のプログラムでは、チェックを簡単に実装できる場合があります。一般に、この種の静的分析を行うには、かなり多くの機械が必要です。

于 2016-11-18T14:50:05.947 に答える