理论上，BNF足以描述所有文件格式吗？
有没有一种文件格式是BNF无法描述的？
Is there any kind of file format that can't be described by BNF?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
有没有一种文件格式是BNF无法描述的？
Is there any kind of file format that can't be described by BNF?
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（2）
不，BNF 还不够。 BNF 描述了上下文无关语法，它甚至与所有可以想象的语法都不接近。几乎所有编程语言，大多数（如果不是全部）合理的数据序列化格式等都是上下文无关的，但既然您询问了理论，答案是否定的。对于初学者来说，有上下文相关语法，（如果名称没有提示） you off）无法用上下文无关语法来表达。一个简单的示例是
n乘以a，然后是n乘以b，然后是n> 次c（每个相同的n）。此外，语法仅描述语法或句法。根据文件格式的不同，该格式的某些数据可能需要更多的条件才能有效（格式良好）——例如，考虑编程语言中的类型检查。您无法使用上下文无关语法或大多数语法来描述此类语义约束。理论上可能有一些高度复杂的可以做到这一点。当然，它们相应地是不切实际的。
No, BNF isn't sufficient. BNF describes context-free grammars, which aren't even close to all imaginable grammars. Pretty much all programming languages, most if not all sane data serialization formats, etc. are context-free, but since you asked about theory, the answer is no. For starters, there are context-sensitive grammars, which (if the name didn't tip you off) can't be expressed with context-free grammars. A simple example would be
ntimesafollowed byntimesbfollowed byntimesc(the samenfor each).Also, grammars only describe, well, the grammar or syntax. Depending on the file format, there may be much more required for some data in that format to be valid (well-formed) - think typechecking in programming languages, for instance. You can't describe such semantics constraints with context-free grammars, or most grammars for that matter. There may be some highly complex ones that can do it in theory. They'd be correspondingly impractical, of course.
是的。 BNF仅描述上下文无关语法。如果一个文件包含其自身语法的描述，则读取此类文件的规则无法用 BNF 表示。为此你需要一台图灵机。类似地，如果接受或拒绝文件的决定不能通过下推自动机来表达，那么 bnf 也不起作用。
例如，BNF 无法完美描述英语语法。
Yes. BNF only describes context free grammars. If a file contains a description of its own syntax, the rules for reading such a file couldn't be expressed in BNF. You would need a Turing machine for that. Similarly, if the decision to accept or reject a file can't be expressed by a push down automata then bnf won't work either.
BNF can't perfectly describe English syntax, for example.