理論上，BNF是否足以描述所有文件格式？

Question

有沒有BNF無法描述的任何種類的文件格式？

Answer 1

沒有，BNF是不夠的。 BNF描述了context-free grammars，它甚至不接近所有可以想象的語法。幾乎所有的編程語言，如果不是所有理智的數據序列化格式等是上下文，但既然你問到理論，答案是否定的。對於初學者，有context-sensitive grammars，這（如果名稱不提示你）不能用上下文無關文法表示。一個簡單的例子是n倍a隨後n倍b隨後n倍c（相同n每個）。

另外，語法只描述，以及，語法或句法。根據文件格式的不同，這種格式的某些數據可能有更多的要求是有效的（格式良好） - 比如說，在編程語言中進行類型檢查。你無法用上下文無關的語法或大多數語法來描述這種語義約束。可能有一些非常複雜的理論上可以做到。當然，它們相應地不切實際。

Answer 2

是。 BNF只描述上下文無關語法。如果一個文件包含它自己語法的描述，讀取這樣一個文件的規則就不能用BNF表示。你需要一臺圖靈機。同樣，如果接受或拒絕文件的決定不能通過下推自動機來表示，那麼bnf也不會起作用。

BNF不能很好地描述英語語法，例如。