theory - 从理论上讲，BNF 是否足以描述所有文件格式？

Question

有没有 BNF 无法描述的文件格式？

Answer 1

不，BNF 是不够的。BNF 描述了上下文无关的语法，它甚至不接近所有可以想象的语法。几乎所有的编程语言，如果不是所有健全的数据序列化格式等，大多数都是上下文无关的，但既然你问了理论，答案是否定的。对于初学者来说，有上下文相关的语法，（如果名字没有提示你的话）不能用上下文无关的语法来表达。一个简单的例子是n时间a后跟n时间，b然后是n时间c（n每个都相同）。

此外，语法仅描述语法或句法。根据文件格式的不同，该格式的某些数据可能需要更多才能有效（格式正确） - 例如，考虑编程语言中的类型检查。您无法使用上下文无关语法或大多数语法来描述此类语义约束。理论上可能有一些高度复杂的可以做到。当然，它们相应地是不切实际的。

Answer 2

是的。BNF 仅描述上下文无关文法。如果一个文件包含对它自己的语法的描述，那么读取这样一个文件的规则就不能用 BNF 来表达。为此，您需要一台图灵机。同样，如果接受或拒绝文件的决定不能通过下推自动机表达，那么 bnf 也将不起作用。

例如，BNF 不能完美地描述英语语法。