目次
BNF（バッカス・ナウア記法）
バッカス・ナウア記法（英：Backus-Naur form）とは、文脈自由文法を定義するのに用いられるメタ言語のことで、BNFやBN記法と略されて使用されています。
文脈自由文法やメタ言語っと聞きなれない言葉で難しく感じますが、ある一定のルールによって作られた文法のことであり、代表的なメタ言語にはXMLがあります。
バッカス・ナウア記法では、次の記号を用いて文法の定義を行います。
| 記号 | 意味 |
| ::= | 「左辺は右辺である」という意味をあらわす |
| | | 「または」という意味をあらわす |
| <記号> | 置き換え可能である（非終端記号）ことをあらわす |
BNF（バッカス・ナウア記法）の記号
記号1「::=」(左辺は右辺である)
バッカス・ナウア記法で使用する記号「::=」は「左辺は右辺である」という意味をあらわします。
例えば、次のバッカス・ナウア記法は<A>は<B>であるという意味です。
<A>:: = <B>
記号2「|」(または)
バッカス・ナウア記法で使用する記号「|」は「または」という意味をあらわします。
例えば、次のバッカス・ナウア記法は<A>または<B>という意味です。
<A>|<B>
記号3「<記号>」(置き換え可能である)
バッカス・ナウア記法で使用する記号「<記号>」は「置き換え可能である」ということを意味します。
例えば、次のバッカス・ナウア記法は<文字>は<あ>または<い>に置き換えることができる（<文字>は<あ>または<い>である）という意味です。
<文字>::= あ | い
BNF（バッカス・ナウア記法）の再帰的定義
バッカス・ナウア記法では、定義の中に自分自身を含むことができます。このような手法を再帰的定義といいます。
スポンサーリンク
例えば、次のようなバッカス・ナウア記法があるとします。
BNFの例文
<文字>::= あ | い
<文字列>::= <文字> | <文字列><文字>
左辺に<文字列>があり、右辺の中にも<文字列>があります。このように定義の中に自分自身を含むことを再帰的定義といいます。
再帰的定義の<文字列>は自分自身をあらわしているため、自分自身の定義である「<文字> | <文字列><文字>」に展開することができます。
再帰的定義の例題
BNFの例文
次のバッカス・ナウア記法で定義される＜英数字＞に合致するものはどれか。
<数字> :: = 1 | 2
<英字> :: = A | B
<英数字> :: = <英字> | <英数字><数字>
ア：1AA イ：AA2 ウ：2BB エ：A12
解答のア～エは3文字です。この問題は<英数字>がどういうルールで定義されているか、<英数字>のルールで3文字を作るにはどうすればよいか考えます。
<英数字> :: = <英字> | <英数字><数字>
<英数字>のルールで3文字を作るには、次のような流れで作成します。
1. <英数字><数字>を選択する
まずは「<英字>または<英数字><数字>」の条件で<英数字><数字>を選択します。（<英字>を選ぶと1文字で終了してしまうので、<英数字><数字>を選択する）
2. 再帰的定義を展開する
<英数字>は再帰的定義なので「<英字> | <英数字><数字>」に置き換えます。
3. 再び<英数字><数字>を選択する
再帰的定義の部分は「<英字>または<英数字><数字>」の条件になっているので<英数字><数字>を選択します。（<英字>を選ぶと<英字><数字>の2文字になってしまうので、ここでは<英数字><数字>を選択する）
4. 再び再帰的定義を展開する
<英数字>は再帰的定義なので「<英字> | <英数字><数字>」に置き換えます。
5. <英字>を選択する
再帰的定義の部分は「<英字>または<英数字><数字>」の条件になっているので<英字>を選択します。（<英数字><数字>を選ぶと4文字以上になってしまうので、ここでは<英字>を選択する）
上記より、3文字の場合は<英字><数字><数字>という文字列になることがわかります。
結果、解答エの「A12」が正解です。