バッカス・ナウア記法(英: Backus?Naur form)とは、文脈自由文法を定義するのに用いられるメタ言語のことで、一般に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年、パリで世界初の国際コンピュータ大会議[1]が開催された際、バッカスは論文[2]を発表した。これは後にALGOL 58と呼ばれる IAL の形式記述であった。彼が発表した形式言語は、エミール・ポストの生成システムに基づいたものであった。形式文法は数学における研究課題のひとつであり、例えばノーム・チョムスキーは自然言語の文法への適用を研究していた[3] [4]。 ピーター・ナウアは、バッカスの記法を単純化し、使用する文字セットを最小化した。この貢献から、ドナルド・クヌースの提案により[5]、Nはナウアにちなむものとされるようになった(この提案は、実際のところその名に反して、この記法が表すものが必ずしも、形式言語理論の用語でいう標準形(正規形とも。normal form)とは限られないためでもある。なお、ナウア本人は、プログラミングに数学的な形式主義を過度に取り入れることを近年は嫌悪している関係でこれを好んでおらず、Backus Normal Formとするほうを好むとしている[要出典])。 バッカス・ナウア記法、あるいは BNF 文法は、パーニニの文法規則によく似ている。このため、パーニニ・バッカス記法(英: Panini?Backus form)と呼ばれることもある。 BNF の表記は次のような導出規則の集合である。<symbol> ::= <expression with symbols> 左辺の<symbol>は単一の記号である。また、<expression with symbols> は記号列、または選択を表すバーティカルバー「|」で区切られた記号列であり、左辺の <symbol> の置換となるものを表している。ある文法における全ての導出規則中で、導出規則群の左辺に現れることがある記号は「非終端記号」であり、いずれの導出規則の左辺にも現れなかった記号は「終端記号」である(終端記号と非終端記号も参照)。 以下はすべての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 では引用符 (") は使わない。<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 には様々な派生と拡張が存在し、一般に単純さと簡潔さのために拡張/修正されるか、特定の用途向けに適用させるべく拡張/修正されている。
歴史
基本
例文
具体例
住所(postal-address)は、名前(name-part)の後に通りの住所(street-address)があり、その後に郵便番号(zip-part)がある。
name-part は個人名(personal-part)の後に姓(last-name)が続き、さらにオプションの "jr-part"(Jr. や Sr. 、あるいは○世など)があり、改行コードがある。あるいは、個人名の後に name-part がある(こちらの規則は再帰的定義になっている。ミドルネームが続く場合を表している)。
個人名(personal-part)はファーストネームか、イニシャルにドットが付いたものである。
通りの住所(street-address)は、オプションのアパート指定があり、番地(house-number)、通りの名前(street-name)、改行コードの順となる。
郵便番号(zip-part)は、タウン名(town-name)、カンマ、州コード(state-code)、郵便番号(ZIP-code)、改行コードの順となる。
BNF の文法
派生
Size:20 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef