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

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 be 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.

– new_perl Aug 1 at 2:17 No. Definitely not PE (and probably not elf). Reading a PE file requires dereferencing pointers.

I imagine an ELF file would too (I know for certain because I've written PE readers / writers, but I haven't looked at the ELF format in depth). That can't be expressed in BNF. You can pretty easily write hand written recursive descent to do most the reading of a PE file though.

– Scott Wisniewski Aug 1 at 2:26 You mentioned You can pretty easily write hand written recursive descent to do most the reading of a PE file though. ,but how? – new_perl Aug 1 at 2:56 Take a look at the PE/Coff spec.

You can download it here: msdn.microsoft. Com/en-us/windows/hardware/gg463119.It describes the binary format of a PE file. Start by reading the headers, then the section table, etc. The code to read that looks very similar to the implementation of a parser.... – Scott Wisniewski Aug 1 at 3:01.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.