Можно ли определить, доступен ли массив памяти вне границ в программе Brainfuck?
Я написал собственный BF Interpreter в Assembly, и теперь я пишу BF Compiler на Java, который компилируется в ассемблерный код.
Я хотел реализовать небольшую приятную функцию, которая обнаружила, что массив ячеек памяти вышел за пределы. Традиционное ограничение для массива - позволить индексу быть в [0, 30000), иначе [0, inf) также широко используется. Другой вариант заключается в том, что память оборачивается, поэтому в первом случае это может означать, что доступ к индексу 30000 означает доступ к индексу 0.
В моем компиляторе это обнаружение было бы сделано на этапе семантического анализа традиционного компилятора, поэтому мы уже получили наше AST (Абстрактное синтаксическое дерево) на этапе синтаксического анализа.
Попытавшись некоторое время придумать конструкцию для этого, я обнаружил обнаружение бесконечного цикла в программе brainfuck вместе со страницей BF в Википедии, и обнаружил, что программа BF с массивом памяти [0, inf) напоминает машину Тьюринга.
Так что мой вопрос для обоих [0, max) а также [0, inf) В случаях, можно ли определить, опустился ли указатель памяти ниже нуля, а в первом случае ниже максимума? Очевидно, не заканчивая бесконечным циклом при проверке, и я бы предпочел также не устанавливать максимальное время выполнения.
Бонусный вопрос: можно ли определить количество раз, как конструкция цикла [...] петли?
1 ответ
БФ способен Тьюринга. Если вы используете его для вычисления индекса, то в общем случае вы не сможете определить, имеет ли индекс конкретное значение (например, 30001) из-за проблемы остановки. Таким образом, в общем, вы не можете обнаружить вне доступа. Тем не менее, вы можете обнаружить это для многих отдельных программ; Вот почему статические анализаторы создаются и используются, несмотря на то, что они теоретически бесполезны.
Относительно счетчика циклов: конструкция цикла работает в зависимости от того, является ли переменная нулевой или нет. BF, будучи способным к Тьюрингу, означает, что в общем случае вы не можете знать, равна ли переменная нулю или нет в какой-то конкретной точке. Смысл в том, что вы не можете знать, сколько раз работает конструкция цикла. Опять же, вы можете понять это для многих отдельных программ.
Для некоторых программ с простыми случаями вы можете легко реализовать свои проверки. В целом, для проведения такого статического анализа требуется довольно много машин.