是否有可能在Brainfuck程序中确定内存数组是否被越界访问?



我已经用汇编语言编写了自己的BF解释器,现在我正在用Java编写一个BF编译器,可以编译成汇编代码。

我想实现一个小功能,如果内存单元数组越界检测。数组的传统限制是让索引在[0, 30000)中,否则也通常使用[0, inf)。另一种选择是内存被封装,所以在第一种情况下,它可能意味着访问索引30000意味着访问索引0。

在我的编译器中,这种检测将在传统编译器的语义分析阶段完成,因此我们已经从语法分析阶段获得了AST(抽象语法树)。

在尝试了一段时间后,我发现在脑操程序中检测无限循环,与BF的维基百科页面一起,我发现一个BF程序与内存数组[0, inf)类似于图灵机。

所以我的问题是,对于[0, max)[0, inf)的情况下,是否有可能检测到内存指针是否低于零,而在前一种情况下低于最大值?显然,在检查它时不会以无限循环结束,而且我宁愿避免设置最大执行时间。

附加问题:是否有可能检测一个循环构造[...]循环的次数?

BF具有图灵能力。如果使用它来计算索引,那么由于暂停问题,通常无法确定索引是否具有特定值(例如,30001)。一般来说,你无法检测出越界访问。但是,您可以在许多单独的程序中检测到这一点;这就是构建和使用静态分析器的原因,尽管它在理论上是无用的。

关于循环次数:循环构造基于变量是否恰好为零来操作。BF具有图灵能力意味着一般来说,你不能知道一个变量在任何特定点是否为零。其含义是,您无法知道循环结构工作的次数。同样,您可以在许多单独的程序中找出这一点。

对于一些简单情况的程序,您可能能够轻松地实现检查。一般来说,做这类静态分析需要相当多的机器。

相关内容

  • 没有找到相关文章

最新更新