【基本情報技術者試験】BNF記法

本日のテーマはBNF記法、次の問題は基本情報技術者試験で出題された過去問です。

BNF記法？聞いたことない言葉ですね・・・

基本情報技術者試験や応用情報技術者試験で出題される問題であるBNF記法。基本情報技術者試験の過去問をみると難しく感じる問題です。

ただ、BNF記法の文法を覚えればそこまで難しい問題ではありません。

本記事では、BNF記法について図解で分かりやすく解説していきます。

BNF記法

BNF記法とは、バッカス・ナウア記法（英：Backus-Naur form）を略した言葉であり、文脈自由文法を定義するのに用いられるメタ言語（言語を記述するための言語）のことです。

BNF記法では次の記号を用いて文法の定義を行います。

BNF記法で使用する記号

スポンサーリンク

例えば次のようなBNF記法の定義があるとします。

上記の例では、<数字>は「1」または「2」であるということをあらわしています。

上記の例では<数字>は「1」または「2」、<英字>は「A」または「B」、<英数字>は <英字><数字>であるということをあらわしています。

<英数字>の<英字><数字>は（「A」または「B」）（「1」または「2」）のことであり「A1」「A2」「B1」「B2」の英数字を表現することができます。

BNF記法の再帰的定義

BNF記法では次のように定義の中に自分自身を含むことができます。このような手法を再帰的定義といいます。

上記の例の<英字> | <英数字><数字>は（「A」または「B」）または（<英字> | <英数字><数字>）（「１」または「２」）のことをあらわしています。（<英数字>は自分自身なので<英字> | <英数字><数字>をあらわす）

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

基本情報技術者試験 過去問の解説

スポンサーリンク

基本情報技術者令和元年秋期 午前問7

この問題は<変数名>がどういうルールで定義されているかを考えます。

解答のア～エは3文字か4文字です。ということは「＜変数名＞＜英数字＞」の条件に2回もしくは3回入ることがわかります。

そして、先頭は必ず<英字>になることもわかります。(＜英字＞｜＜変数名＞＜英数字＞で繰り返しにならない条件は<英字>を選んだときしかない。）

答えは「エ」の「F5_1」です。

基本情報技術者平成23年秋期 午前問4

この問題は解答のア～エを問題の規則に従って変換していき<式>の形式になるものを探します。

解答ア　A＋(B＋C)＊D

解答アを規則に従って変換していきます。

解答イ　(A＋B)＋(C＋D)

解答イを規則に従って変換していきます。

解答ウ　(A＋B)＊(C＋D)

解答ウを規則に従って変換していきます。

解答エ　(A＊B)＋(C＊D)

解答エを規則に従って変換していきます。

上記より＜式＞ ::＝＜変数＞｜(＜式＞＋＜式＞)｜＜式＞＊＜式＞の規則から生成できる式は「ウ」の(A＋B)＊(C＋D)ということが分かりました。