バッカス・ナウア記法

バッカス・ナウア記法（英: 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>

これを言葉に直すと、次のようになる。

住所（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）、改行コードの順となる。

これは非常に単純化しており、定義されていない部分（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 には様々な派生と拡張が存在し、一般に単純さと簡潔さのために拡張/修正されるか、特定の用途向けに適用させるべく拡張/修正されている。特によく行われる拡張は * や + といった正規表現の繰り返しオペレータの導入である。典型的な例として EBNF（Extended Backus–Naur form）がある。実際、上記の例は ALGOL 60 リポートで使われたオリジナルそのままの形式ではない。"[]" という括弧を使った記法は、IBMのPL/Iの定義で初めて使われ、現在では一般化している。ABNF（Augmented Backus–Naur form）は、IETF の通信プロトコルの定義などに使われている。

Parsing Expression Grammar は BNF と正規表現に基づき、新たな形式文法のクラスを形成したものである。その性質は生成的というよりも基本的に解析的である。

今日、インターネット上で見つかるBNF表現の多くは人間が読むことを重視しており、非形式的である。そのため、以下のような構文規則の拡張をしていることが多い。

省略可能なアイテムは角括弧で囲む。例えば、[<item-x>]
0回以上繰り返すアイテムは中括弧で囲む。例えば、<word> ::= <letter> { <letter> }
1回以上繰り返すアイテムには + を後置する。<word> ::= <letter>+
終端記号をボールド体、非終端記号を通常の文字で表し、イタリック体や山括弧を使わない。
アイテムの繰り返しを * を後置することで表すことが多い。
生成時の選択肢を | 記号で区切って列挙する。例えば、<alternative-a> | <alternative-b>
アイテムをグループ化する必要があるときは、普通の括弧で囲む。
セミコロンに続けて註釈を付ける^[6]。

参考文献

この記事は2008年11月1日以前にFree On-line Dictionary of Computingから取得した項目の資料を元に、GFDL バージョン1.3以降の「RELICENSING」(再ライセンス) 条件に基づいて組み込まれている。

脚注

^ 英: World Computer Congress
^ J. W. Backus, The Syntax and Semantics of the Proposed International Algebraic Language of the Zurich ACM-GAMM Conference, 1959.
^ Chomsky, Noam, "Three Models for the Description of Language," IRE Transactions on Information Theory, Vol. 2 No. 2, pp. 113-123, 1956.
^ Chomsky, Noam, Syntactic Structures, Mouton, The Hague, 1957.
^ Knuth, Donald E. Backus Normal Form vs. Backus Naur Form、Communications of the ACM 誌 7(12):735-736, 1964
^ https://www.w3.org/Notation.html

外部リンク

Algol-60 BNF - オリジナルのBNF
BNF Web club^{[リンク切れ]} - サンプルの文法がある。
[1] - news:comp.compilers へのポスト。2つの名称（バッカス・ナウア記法とバッカス・ノーマル記法）の歴史について説明している。
BNF and EBNF: What are they and how do they work? by Lars Marius Garshol.
RFC 4234 Augmented BNF for Syntax Specifications: ABNF
Comparision of different variants of BNF^{[リンク切れ]}
Syntax diagram of EBNF^{[リンク切れ]}
Generation of syntax diagrams from EBNF^{[リンク切れ]}

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

[1] 英: World Computer Congress

[2] J. W. Backus, The Syntax and Semantics of the Proposed International Algebraic Language of the Zurich ACM-GAMM Conference, 1959.

[Chomsky1956-3] Chomsky, Noam, "Three Models for the Description of Language," IRE Transactions on Information Theory, Vol. 2 No. 2, pp. 113-123, 1956.

[Chomsky1957-4] Chomsky, Noam, Syntactic Structures, Mouton, The Hague, 1957.

[5] Knuth, Donald E. Backus Normal Form vs. Backus Naur Form、Communications of the ACM 誌 7(12):735-736, 1964

[6] ttps://www.w3.org/Notation.html

[1]

[2]

[3]

[4]

[5]

[6]

歴史

基本

例文

具体例

BNF の文法

派生

関連項目

参考文献

脚注

外部リンク