コンピュータ

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

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

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

どういう意味ですか?
次のような形式で作られた言語のことをBNF記法といいます。

BNF記法の記号

BNF記法で使用する記号は次のとおりです。

<A>:: = <B>

※意味:<A>は<B>である

「::=」の記号を使うことで「左辺は右辺である」という意味をあらわします。

<A>|<B>

※意味:<A>または<B>

「|」の記号使うことで「または」という意味をあらわします。

<A><B>

※意味:<A>と<B>をつなげたもの

BNF記法の再帰的定義

BNF記法の例文

<文字>::= あ | い

<文字列>::= <文字> | <文字列><文字>

それでは、例文のBNF記法の見方を説明していきます。

<文字>::= あ | い

<文字>は「あ」または「い」であるということを示しています。

<文字列>::= <文字> | <文字列><文字>

<文字列>は<文字>または<文字列><文字>であるということを示しています。

あれ?左側にある<文字列>が右側にも存在している、どういう意味ですか?
定義の中に自分自身を含むことができます。このような手法を再帰的定義といいます。

定義の中に再帰的定義を書くことで、同じパターンの繰り返しを表現することができます。

 

例えば「<文字列>::= <文字> | <文字列><文字>」の定義に「あい」という文字列をあてはめてみると次のようになります。

再帰的定義の例1

再帰的定義の例2

上記図例の流れ

  • 「あい」は2文字なので、<文字> | <文字列><文字> の <文字列><文字> にあてはまる
  • <文字列><文字> に「あい」をあてはめる
  • まずは「あ」
  • <文字列><文字> の <文字列>は再帰的定義なので「<文字> | <文字列><文字>※再帰」の定義に戻る →「あ」は1文字なので、「<文字> | <文字列><文字>※再帰」 の 「<文字>※再帰」 にあてはまる → 結果 <文字列><文字> の <文字列> に「あ」があてはまる
  • 続いて「い」
  • 「い」は文字なので <文字列><文字> の <文字> にあてはまる


チャンネル登録はこちら

フォローはこちら