theory - 理論的には、BNF はすべてのファイル形式を記述するのに十分ですか?

Question

BNFで記述できないファイル形式はありますか?

Answer 1

いいえ、BNF では不十分です。BNF は文脈自由文法を記述していますが、これは想像できるすべての文法に近いものではありません。ほぼすべてのプログラミング言語、すべてではないにしてもほとんどのデータのシリアル化形式などはコンテキストフリーですが、理論について尋ねたので、答えはノーです。手始めに、文脈依存文法がありますが、これは (名前からヒントを得ていなければ) 文脈自由文法では表現できません。簡単な例としては、n時間のa後にn時間と時間(それぞれ同じ)bが続きます。ncn

また、文法は文法または構文のみを記述します。ファイル形式によっては、その形式の一部のデータが有効 (整形式) であるためには、さらに多くのことが必要になる場合があります。たとえば、プログラミング言語での型チェックを考えてみてください。このようなセマンティクスの制約は、文脈自由文法やほとんどの文法では記述できません。理論的にはそれを行うことができる非常に複雑なものがいくつかあるかもしれません. もちろん、それらはそれに対応して非現実的です。

Answer 2

はい。BNF は文脈自由文法のみを記述します。ファイルに独自の構文の記述が含まれている場合、そのようなファイルを読み取るための規則は BNF で表現できませんでした。そのためにはチューリングマシンが必要です。同様に、ファイルを受け入れるか拒否するかの決定がプッシュ ダウン オートマトンで表現できない場合、bnf も機能しません。

たとえば、BNF は英語の構文を完全に記述することはできません。