コンピュータ

BNF記法(バッカス・ナウア記法)とは

BNF記法(バッカス・ナウア記法)

バッカス・ナウア記法(英:Backus-Naur form)とは、文脈自由文法を定義するのに用いられるメタ言語(代表的なメタ言語にはXMLがある)のことで、BNF記法やBN記法と略される言葉です。

バッカス・ナウア記法では、次の記号を用いて文法の定義を行います。

記号 意味
::= 「左辺は右辺である」という意味をあらわす
| 「または」という意味をあらわす
<記号> 置き換え可能である(非終端記号)ことをあらわす

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文字を作るには次のような流れで作成します。

1. <英数字><数字>を選択する

まずは「<英字>または<英数字><数字>」の条件で<英数字><数字>を選択します。(<英字>を選ぶと1文字で終了してしまうので、<英数字><数字>を選択する)

再帰的定義の問題 手順1

2. 再帰的定義を展開する

<英数字>は再帰的定義なので「<英字> | <英数字><数字>」に置き換えます。

再帰的定義の問題 手順2

3. 再び<英数字><数字>を選択する

再帰的定義の部分は「<英字>または<英数字><数字>」の条件になっているので<英数字><数字>を選択します。(<英字>を選ぶと<英字><数字>の2文字になってしまうので、ここでは<英数字><数字>を選択する)

再帰的定義の問題 手順3

4. 再び再帰的定義を展開する

<英数字>は再帰的定義なので「<英字> | <英数字><数字>」に置き換えます。

再帰的定義の問題 手順4

5. <英字>を選択する

再帰的定義の部分は「<英字>または<英数字><数字>」の条件になっているので<英字>を選択します。(<英数字><数字>を選ぶと4文字以上になってしまうので、ここでは<英字>を選択する)

再帰的定義の問題 手順5

上記より、3文字の場合は<英字><数字><数字>という文字列になることがわかります。

結果、解答エの「A12」が正解です。

YouTubeでも解説しています。チャンネル登録と高評価よろしくお願いします!
ITを分かりやすく解説

チャンネル登録はこちら

フォローはこちら