Theoretically, is BNF sufficient to describe all file format? [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 11 years ago.

Is there any kind of开发者_高级运维 file format that can't be described by BNF?

---

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 n times a followed by n times b followed by n times c (the same n for 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.

---

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.