バッカス・ナウア記法
ジョン・バッカスは ALGOLの文法を表現するためにこの記法を考案した。1959年、パリで世界初の国際コンピュータ大会議が開催された際、バッカスは論文を発表した。これは後にALGOL 58と呼ばれる IAL の形式記述であった。彼が発表した形式言語は、エミール・ポストの生成システムに基づいたものであった。形式文法は数学における研究課題のひとつであり、例えばノーム・チョムスキーは自然言語の文法への適用を研究していた 。
ピーター・ナウアは、バッカスの記法を単純化し、使用する文字セットを最小化した。この貢献から、ドナルド・クヌースの提案により、Nはナウアにちなむものとされるようになった(この提案は、実際のところその名に反して、この記法が表すものが必ずしも、形式言語理論の用語でいう標準形(正規形とも。normal form)とは限られないためでもある。なお、ナウア本人は、プログラミングに数学的な形式主義を過度に取り入れることを近年は嫌悪している関係でこれを好んでおらず、Backus Normal Formとするほうを好むとしている)。
バッカス・ナウア記法、あるいは BNF 文法は、パーニニの文法規則によく似ている。このため、パーニニ・バッカス記法(英: Panini–Backus form)と呼ばれることもある。
BNF の表記は次のような導出規則の集合である。
左辺の<symbol>は単一の記号である。また、<expression with symbols> は記号列、または選択を表すバーティカルバー「|」で区切られた記号列であり、左辺の <symbol> の置換となるものを表している。ある文法における全ての導出規則中で、導出規則群の左辺に現れることがある記号は「非終端記号」であり、いずれの導出規則の左辺にも現れなかった記号は「終端記号」である(終端記号と非終端記号も参照)。