応用情報技術者試験

BNF/バッカス・ナウア記法とは?

BNF記法とは

応用情報技術者試験の問題を解いているとBNF記法について出てきます。今回は文脈自由文法を定義するのに用いられるメタ言語であるBNF記法についてお勉強しましょう。

ペンちゃん
ペンちゃん
今回はBNF記法についてお勉強しよう!

応用情報技術者試験攻略

情報処理技術者試験の一区分である応用情報技術者試験を攻略するためのシリーズになります。今回はBNFについて学習していきましょう。

BNF/BN記法/バッカス・ナウア記法/BNF記法とは

バッカス・ナウア記法(Backus-Naur form)とは、文脈自由文法を定義するのに用いられるメタ言語(言語を記述するための言語)の一つです。

記号の意味は次のようになります。

  • <X>:: = <Y>

<X> は <Y> である。

  • <A><B>

<A> と <B> をつなげたもの。

  • <A>|<B>

<A> または <B>

となります。

例文

<hoge>:: = <123><456>|<abc><def>

<hoge>は 「<123>と<456>をつなげたもの」または「<abc>と<def>をつなげたもの」である。

過去問で攻略

問題

応用情報技術者試験 H29年春 問4

あるプログラム言語において,識別子(identifier)は,先頭が英字で始まり,それ以降に任意個の英数字が続く文字列である。これをBNFで定義したとき,a に入るものはどれか。
<digit>::=0|1|2|3|4|5|6|7|8|9
<letter>::=A|B|C|…|X|Y|Z|a|b|c|…|x|y|z
<identifier>::= a

<letter>|<digit>|<identifier><letter>|<identifier><digit>
<letter>|<digit>|<letter><identifier>|<identifier><digit>
<letter>|<identifier><digit>
<letter>|<identifier><digit>|<identifier><letter>

解答

<letter>|<digit>|<identifier><letter>|<identifier><digit>

2つ目の項に<digit>があり、1文字の数字のみである文字列が含まれるので誤りです。

<letter>|<digit>|<letter><identifier>|<identifier><digit>

と同様に、2つ目の項に<digit>があり、1文字の数字のみである文字列が含まれるので誤りです。

<letter>|<identifier><digit>

1つ目の項に<letter>があり、先頭は英字となる。2つ目の項は<identifier><digit>であるので、先頭の英字の後に数字が任意個続きます。すなわち、英字が先頭にしか使えないので誤りです

<letter>|<identifier><digit>|<identifier><letter>

1つ目の項に<letter>があり、先頭は英字となる。2つ目の項は<identifier><digit>、3つ目の項は<identifier><letter>であるので、先頭の英字の後に英字または数字が任意個続きます。すなわち、条件に合致するので正解です。

答え 

まとめ

応用情報技術者試験で覚えないといけない内容は以下になります。

応用情報技術者試験を攻略
  • <X>:: = <Y>  <X> は <Y> である。
  • <A><B>  <A> と <B> をつなげたもの。
  • <A>|<B>  <A> または <B>

以上の記法を覚えておきましょう。

ペンちゃん
ペンちゃん
今回はBNF記法についてお勉強したよ!