解释上下文无关文法（CFG）是否能被非确定性下推自动机识别。

上下文无关文法（CFG）肯定可以被非确定性下推自动机（NPDA）识别，但编程语言是通过确定性下推自动机（PDA）转换为二进制（机器码）的。

这是因为这具有以下影响：

  • 如果编程语言应该通过NPDA进行转换，那么对于一个给定的程序实例，我们将生成多个版本的二进制（机器码）用于同一个程序，这在理想情况下不应该发生。
  • 对于一个给定的程序，应该只生成一个版本的二进制代码，并且该代码应该在所有操作系统平台上保持一致。
  • 输出将有很大差异：如果我们有多个目标文件，那么在一个情况下输出可能是预期的，而在再次运行程序时，输出将会有所不同，因为由于NPDA编译过程发生了变化，因此目标代码的生成也发生了变化。因此，输出是变化的，在许多情况下会导致错误的输出。
  • 语法的多重解释可能导致无限循环：考虑一个具有终止条件的循环体的情况。通过多种编译方式，许多关键字可能会被错误地解释，如果未评估正确的终止条件，这可能会导致无限循环。例如，对于循环 (i = 0; i< n ; i++)，如果它被编译为 (i = n; i >0; i++)，这将导致无限循环。
  • 难以调试 - 由于NPDA过程生成了多个版本的obj文件，因此我们将发现很难调试代码中的bug以修复它们。

更新于： 2021年6月16日

512 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告