1

我已经用自己的 BF 解释器在汇编中编写，现在我正在用 Java 编写一个 BF 编译器，它可以编译为汇编代码。

我想实现一个很好的功能，可以检测内存单元数组是否超出范围。数组的一个传统限制是让索引在 中[0, 30000)，否则[0, inf)也是常用的。另一种选择是内存是环绕的，所以在第一种情况下，这可能意味着访问索引 30000 意味着访问索引 0。

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

在尝试为此提出一个结构一段时间后，我发现在 Brainfuck 程序中检测无限循环，连同 BF 的 Wikipedia 页面，我发现带有内存数组的 BF 程序[0, inf)类似于图灵机。

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

额外问题：是否可以检测循环构造[...]循环的次数？

4

1 回答 1

3

BF 具有图灵能力。如果您使用它来计算一个索引，那么您通常无法确定该索引是否具有特定值（例如，30001），因为存在停机问题。因此，一般来说，您无法检测到越界访问。但是，您可能能够在许多单独的程序中检测到这一点；这就是为什么静态分析器在理论上没有用的情况下被构建和使用的原因。

关于循环行程计数：循环构造基于变量是否恰好为零来操作。BF 具有图灵能力意味着通常您无法知道变量在任何特定点是否为零。这意味着您无法知道循环构造工作的次数。同样，您可能能够为许多单独的程序解决这个问题。

对于一些简单案例的程序，您可能能够轻松地实现您的检查。一般来说，进行这种静态分析需要相当多的机器。

于 2016-11-18T14:50:05.947 回答