バッカス・ナウア記法

バッカス・ナウア記法（）とは、文脈自由文法を定義するのに用いられるメタ言語のことで、一般にBNFやBN記法と略される。現在はこのBNFを拡張したEBNF (Extended BNF) が一般的に使われている。EBNFでは正規表現を用いてより簡単に記述でき、プロトコル規定言語であるASN.1や、XMLの構文定義にも利用されている。
ジョン・バッカスとピーター・ナウアがALGOL 60 の文法定義のために考案。当初は文脈自由文法の本来の定義に則り or（|）以外の定義はなく、繰り返しは再帰を利用して表現されている。*、?等の量化子はBNFを拡張したEBNFによって導入された。パーサジェネレータを使用して構文解析器を生成する際に、構文を定義するためにも使う。
ISO/IEC 14977:1996においてEBNFの標準が定義されているが、EBNFにもいろいろな亜種や変種がある。例えば、RFC2234にはABNF (Augmented BNF) という変種が定義されている。しかし、ABNFは標準のEBNFとかなり異なる部分がある。
歴史.
ジョン・バッカスは ALGOLの文法を表現するためにこの記法を考案した。1959年、パリで世界初の国際コンピュータ大会議が開催された際、バッカスは論文を発表した。これは後にALGOL 58と呼ばれる IAL の形式記述であった。彼が発表した形式言語は、エミール・ポストの生成システムに基づいたものであった。形式文法は数学における研究課題のひとつであり、例えばノーム・チョムスキーは自然言語の文法への適用を研究していた 。
ピーター・ナウアは、バッカスの記法を単純化し、使用する文字セットを最小化した。この貢献から、ドナルド・クヌースの提案により、Nはナウアにちなむものとされるようになった（この提案は、実際のところその名に反して、この記法が表すものが必ずしも、形式言語理論の用語でいう標準形（正規形とも。normal form）とは限られないためでもある。なお、ナウア本人は、プログラミングに数学的な形式主義を過度に取り入れることを近年は嫌悪している関係でこれを好んでおらず、Backus Normal Formとするほうを好むとしている）。
バッカス・ナウア記法、あるいは BNF 文法は、パーニニの文法規則によく似ている。このため、パーニニ・バッカス記法（）と呼ばれることもある。
基本.
BNF の表記は次のような導出規則の集合である。
<symbol> ::= <expression with symbols>
左辺の<symbol>は単一の記号である。また、codice_1 は記号列、または選択を表すバーティカルバー「codice_2」で区切られた記号列であり、左辺の codice_1 の置換となるものを表している。ある文法における全ての導出規則中で、導出規則群の左辺に現れることがある記号は「非終端記号」であり、いずれの導出規則の左辺にも現れなかった記号は「終端記号」である（終端記号と非終端記号も参照）。
例文.
以下はすべてのBNFに当てはまるわけではない。
<hoge> ::= <hogehoge>
<hoge> は <hogehoge> である。
<hoge> ::= <abc> | <def>
<hoge> は <abc> または <def> である。
具体例.
例として、アメリカ合衆国での住所表記（郵便）をBNFで表現する。
<postal-address> ::= <name-part> <street-address> <zip-part>
<name-part> ::= <personal-part> <last-name> <opt-jr-part> <eol> 
 | <personal-part> <name-part> <eol>
<personal-part> ::= <first-name> | <initial> "." 
<street-address> ::= <opt-apt-num> <house-num> <street-name> <eol>
 <zip-part> ::= <town-name> "," <state-code> <zip-code> <eol>
これを言葉に直すと、次のようになる。
これは非常に単純化しており、定義されていない部分（first-name、apt-num、ZIP-code など）が多々ある点に注意されたい。それらを新たな BNF 規則を追加することで表現することもできる。
BNF の文法.
BNF の文法は BNF 自体を使って以下のように表現できる。ただし、本来の BNF では引用符 （"） は使わない。
<syntax> ::= <rule> | <rule> <syntax>
<rule> ::= <opt-whitespace> "<" <rule-name> ">" <opt-whitespace> "::=" 
 <opt-whitespace> <expression> <line-end>
<opt-whitespace> ::= " " <opt-whitespace> | "" ……… "" は空文字列を表す
<expression> ::= <list> | <list> "|" <expression>
<line-end> ::= <opt-whitespace> <eol> | <line-end> <line-end>
<list> ::= <term> | <term> <opt-whitespace> <list>
<term> ::= <literal> | "<" <rule-name> ">"
<literal> ::= '"' <text> '"' | "'" <text> "'"
ここで、構文規則を正しく翻訳するには空白 (whitespace) が必要であるとしている。<eol> は適当な行末を示す記号（改行コード）である。<rule-name> は宣言された規則の名前またはラベルに、<text> はテキストに置き換えられる。
派生.
BNF には様々な派生と拡張が存在し、一般に単純さと簡潔さのために拡張/修正されるか、特定の用途向けに適用させるべく拡張/修正されている。特によく行われる拡張は codice_4 や codice_5 といった正規表現の繰り返しオペレータの導入である。典型的な例として EBNF（Extended Backus–Naur form）がある。実際、上記の例は ALGOL 60 リポートで使われたオリジナルそのままの形式ではない。"[]" という括弧を使った記法は、IBMのPL/Iの定義で初めて使われ、現在では一般化している。ABNF（Augmented Backus–Naur form）は、IETF の通信プロトコルの定義などに使われている。
Parsing Expression Grammar は BNF と正規表現に基づき、新たな形式文法のクラスを形成したものである。その性質は生成的というよりも基本的に解析的である。
今日、インターネット上で見つかるBNF表現の多くは人間が読むことを重視しており、非形式的である。そのため、以下のような構文規則の拡張をしていることが多い。