情報処理技術者試験の問題を解いているとBNF記法について出てきます。今回は文脈自由文法を定義するのに用いられるメタ言語であるBNF記法についてお勉強しましょう。
BNF/BN記法/バッカス・ナウア記法/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>をつなげたもの」である。
基本情報技術者試験の過去問で攻略
基本情報技術者試験の過去問で確認してみましょう。
問題
次のBNFで定義される<変数名>に合致するものはどれか。
<数字>::= 0|1|2|3|4|5|6|7|8|9
<英字>::= A|B|C|D|E|F
<英数字>::=<英字>|<数字>|_
<変数名>::=<英字>|<変数名><英数字>
イ 246
ウ 3E5
エ F5_1
解答
<数字>:「1~9」までの1文字
<英字>:「A~F」までの1文字
<英数字>:「1~9,A~F,_」の一文字
<変数名>:「A~F」までの1文字、または「A~F」から始まり、後ろに「1~9,A~F,_」が付いたもの
「_」から始まっているので、<変数名>の定義にあてはまりません。
「A~F」から始まっていないので、<変数名>の定義にあてはまりません。
「A~F」から始まっていないので、<変数名>の定義にあてはまりません。
<変数名>の定義である、「A~F」から始まり、後ろに「1~9,A~F,_」が付いたものにあてはまるので正解です。
答え エ
応用情報技術者試験の過去問で攻略
問題
あるプログラム言語において,識別子(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>|<letter><identifier>|<identifier><digit>
ウ <letter>|<identifier><digit>
エ <letter>|<identifier><digit>|<identifier><letter>
解答
2つ目の項に<digit>があり、1文字の数字のみである文字列が含まれるので誤りです。
アと同様に、2つ目の項に<digit>があり、1文字の数字のみである文字列が含まれるので誤りです。
1つ目の項に<letter>があり、先頭は英字となる。2つ目の項は<identifier><digit>であるので、先頭の英字の後に数字が任意個続きます。すなわち、英字が先頭にしか使えないので誤りです
1つ目の項に<letter>があり、先頭は英字となる。2つ目の項は<identifier><digit>、3つ目の項は<identifier><letter>であるので、先頭の英字の後に英字または数字が任意個続きます。すなわち、条件に合致するので正解です。
答え エ
まとめ
情報処理技術者試験試験で覚えないといけない内容は以下になります。
- <X>:: = <Y> <X> は <Y> である。
- <A><B> <A> と <B> をつなげたもの。
- <A>|<B> <A> または <B>
以上の記法を覚えておきましょう。