上下文无关语法转换
can anyone let me know if there is any software to convert Chomsky normal form to Backus–Naur Form and vice versa?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
can anyone let me know if there is any software to convert Chomsky normal form to Backus–Naur Form and vice versa?
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（3）
嗯，乔姆斯基范式和巴科斯-诺尔范式实际上并不是同一种概念，所以我真的不这么认为。 但如果您告诉我们您需要该软件做什么，我们可能会提供帮助。
现在，根据您的要求，我假设您需要某种代码将 BNF 语法规范化为乔姆斯基范式。 据我所知，不存在这样的软件，但假设这是一项实际上在计算上可行的任务，则可能存在一些软件。
但是，如果您能更具体地了解您的实际需要，我们将能够为您提供有关该任务的有用建议。
编辑：在我的书中深入研究后，事实证明完全有可能制定一种算法将任意 CFG 转换为乔姆斯基范式。 但我没有实际的算法或其复杂性。
Well, Chomsky Normal Form and Backus-Naur Form aren't really the same kind of concept, so I don't really think so. But if you told us what you needed this software for we might be able to help.
Now, going from what you asked, I'm assuming you want some kind of code to normalize a BNF grammar to Chomsky Normal Form. As far as I know, no such software exists, but it's possible some exists, assuming that it's a task that's actually computationally feasible.
But, if you can be more concrete about what you actually need we'll be able to give you useful advice about that task.
EDIT: After digging a bit in my books, it turns out that it's entriely possible to formulate an algorithm to convert an arbitrary CFG to Chomsky Normal Form. I don't have the actual algorithm or its complexity though.
也许 JFLAP 会满足您的需求。
我自己还没有使用过它，但我的自动机教授向我推荐了它。
查看“什么是 JFLAP？” 页面，它似乎可以从“CFG -> CNF”转换，这听起来像是您想要做的。
Maybe JFLAP will do what you're looking for.
I've not used it yet myself, but it was recommended to me by my Automata professor.
Looking on the "What is JFLAP?" page, it appears that it can convert from "CFG -> CNF" which sounds like what you're looking to do.
正如所指出的，我最初的答案“BNF 已经在 CNF 中”是错误的。 您可以将任何上下文无关语法转换为 CNF，如下所述 此处 (PDF)。 Sipser 第二版中也说明了转换过程。 第 106-109 页（如果您有权访问）。 我不知道是否有现有的软件可以自动执行此过程（但编写起来似乎很简单）。
As was pointed out, my original answer that BNF is already in CNF was wrong. You can convert any context-free grammar to CNF as explained here (PDF). The conversion process is also illustrated in Sipser 2nd Ed. pages 106-109 if you have access to it. I don't know if there's existing software that automates this process (but it would seem simple to write).