Ist es möglich zu bestimmen, ob das Speicherarray in einem Brainf ** k-Programm außerhalb der Grenzen zugegriffen wird?

Question

Ich habe von eigenen BF Interpreter in Assembly geschrieben, und jetzt schreibe ich einen BF Compiler in Java, der Assembler-Code kompiliert.

Ich wollte ein kleines nettes Feature implementieren, das erkannte, wenn das Array von Speicherzellen außerhalb der Grenzen war. Eine traditionelle Einschränkung für das Array besteht darin, den Index in [0, 30000) zu lassen, ansonsten wird auch [0, inf) verwendet. Eine andere Option ist, dass der Speicher umgebrochen wird, im ersten Fall könnte es bedeuten, dass der Zugriff auf den Index 30000 den Zugriff auf den Index 0 bedeutet. In meinem Compiler würde diese Erkennung in der Semantic Analysis-Phase eines traditionellen Compilers erfolgen, also wir haben bereits unseren AST (Abstract Syntax Tree) aus der Syntax-Analyse-Phase erhalten.

Nachdem ich einige Zeit lang versucht habe, ein Konstrukt zu finden, habe ich Detecting infinite loop in brainfuck program gefunden, zusammen mit BFs Wikipedia-Seite habe ich herausgefunden, dass ein BF-Programm mit einer Speichermatrix [0, inf) einer Turing-Maschine ähnelt.

Also ist meine Frage, sowohl für die [0, max) und [0, inf) Fällen, ist es möglich zu erkennen, wenn der Speicherzeiger unter Null geht, und im ersten Fall unter Max? Offensichtlich, ohne in einer Endlosschleife zu enden, während ich es überprüfe, und ich würde es auch vermeiden, eine maximale Ausführungszeit zu setzen.

Bonus Frage: Ist es möglich zu erkennen, wie oft ein Loop-Konstrukt [...] Schleifen?

Answer 1

BF ist Turing-fähig. Wenn Sie es verwenden, um einen Index zu berechnen, können Sie nicht allgemein bestimmen, ob der Index einen bestimmten Wert (z. B. 30001) wegen des Halteproblems hat. Daher können Sie im Allgemeinen keinen Zugriff außerhalb des Zugriffs erkennen. Möglicherweise können Sie dies jedoch für viele einzelne Programme feststellen. Aus diesem Grund werden statische Analysatoren gebaut und verwendet, obwohl sie theoretisch nutzlos sind.

In Bezug auf Loop Trip Count: Das Loop-Konstrukt arbeitet basierend darauf, ob eine Variable zufällig Null ist oder nicht. BF, das Turing-fähig ist, bedeutet, dass Sie im Allgemeinen nicht wissen können, ob eine Variable an einem bestimmten Punkt Null ist oder nicht. Die Implikationen sind, dass Sie nicht wissen, wie oft ein Schleifenkonstrukt funktioniert. Auch dies können Sie für viele einzelne Programme herausfinden.

Für einige Programme mit einfachen Fällen können Sie Ihre Überprüfungen leicht implementieren. Im Allgemeinen machen diese statischen Analysen eine Menge Maschinen.