normalization - 上下文无关语法转换

Question

谁能告诉我是否有任何软件可以将乔姆斯基范式转换为巴科斯-瑙尔范式，反之亦然？

Answer 1

嗯，乔姆斯基范式和巴库斯-瑙尔形式并不是一个真正的概念，所以我真的不这么认为。但是，如果您告诉我们您需要什么软件，我们可能会提供帮助。

现在，根据您的要求，我假设您想要某种代码将 BNF 语法规范化为乔姆斯基范式。据我所知，不存在这样的软件，但有可能存在一些，假设它是一项实际上在计算上可行的任务。

但是，如果您能更具体地了解您的实际需求，我们将能够为您提供有关该任务的有用建议。

编辑：在我的书中挖掘了一下之后，事实证明完全有可能制定一种算法来将任意 CFG 转换为乔姆斯基范式。我没有实际的算法或其复杂性。

Answer 2

也许JFLAP会做你正在寻找的东西。

我自己还没有使用它，但是我的 Automata 教授向我推荐了它。

查看“什么是 JFLAP？” 页面，它似乎可以从“CFG - > CNF”转换，这听起来像你想要做的。

Answer 3

正如所指出的，我最初关于 BNF 已经在 CNF 中的回答是错误的。您可以将任何上下文无关语法转换为 CNF，如此处所述(PDF)。Sipser第 2 版中也说明了转换过程。如果您可以访问第 106-109 页。我不知道是否有现有的软件可以自动化这个过程（但它似乎很容易编写）。