BNFの解法 （FE過去問）
基本情報技術者試験の過去問題でBNF記法(バッカス・ナウア・フォーム)というのがあります。
問題集の解説を読んでも小難しく書いてあり、わかりにくかったので自分なりの解法手順を載せておきます。
問題の概要はXMLの仕様は、BNF記法で記述されているのでXMLを理解する為にはBNF記法の理解が必要である。との事。
BNF記法の問題
次の規則から生成することができる式はどれか。〔規則〕
＜式＞ ::＝＜変数＞｜(＜式＞＋＜式＞)｜＜式＞＊＜式＞
＜変数＞ ::＝A｜B｜C｜Dア、A＋(B＋C)＊D イ、(A＋B)＋(C＋D)ウ、(A＋B)＊(C＋D) エ、(A＊B)＋(C＊D)
一見だと何か色々記号があって意味がわからないと思いますので、記号の説明します。
:: ・・・定義するという意味
| ・・・「または」「もしくは」。英語で言うと[or]ですね。
<> ・・・非終端記号。他の文字列に置き換える記号です。
〔規則〕
＜式＞ ::＝＜変数＞｜(＜式＞＋＜式＞)｜＜式＞＊＜式＞
＜変数＞ ::＝A｜B｜C｜D
記号の意味がわかったのでこれに説明に付け加えます。
<式>というのは
① <変数>
または
②(<式> ＋ <式>)
または
③ <式> ＊ <式>
という３種類(うちどれでもよい)を定義します。
という意味。
＜変数＞というのは
①A
または
②B
または
③C
または
④D
という４種類(うちどれでもよい)を定義します。
という意味。
なのでもし解答の選択肢に ア、A という解答があれば ア が正解です。
◆ア、Aが正解になる解法
<式> は、<変数> と定義される。
<変数>は、A と定義される。
よって<式> ＝ A
という手順で導き出せます。
しかしそれほど問題は甘くないので(笑)
この４種類から選ばないといけません。
ア、A＋(B＋C)＊D
イ、(A＋B)＋(C＋D)
ウ、(A＋B)＊(C＋D)
エ、(A＊B)＋(C＊D)
それではまず順番にア、からみていきます。
注目するのは演算子の ＋ や ＊ です。
これを基準に<式>に定義を置き換えます。
ア、A＋(B＋C)＊D
Aの次に＋ 記号があるので
(＜式＞＋＜式＞)を当てはまりますが、Aは、()でくくられてないので式の定義の形と一致しません。
よって アは、間違い。
イ、(A＋B)＋(C＋D)
これも + がついてるので(＜式＞＋＜式＞)で表せます。
ではこれを定義の形に直すと
イ、(＜式＞＋＜式＞)＋(＜式＞＋＜式＞)
ですね。
それでは、この形が<式>の定義の形と一致してるか確認します。
＋記号が入ってるので対象となる<式>の定義は②(<式> + <式>)です。
これの<式>の部分に②(<式> ＋ <式>)を置き換えます。
この処理が少しややこしく感じますね。
そして、置き換えた形はこうなります。
② ((<式> ＋ <式>) + (<式> ＋ <式>))
これを比較してみます。
② ((<式> ＋ <式>) + (<式> ＋ <式>))
イ、(<式> ＋ <式>) + (<式> ＋ <式>)
②の両端の()が多いので一致しません。
よってイ は間違い。
ウ、(A＋B)＊(C＋D)
これは、+ と ＊ がありますね。
まず + の部分を(＜式＞＋＜式＞)の定義に直します。
ウ、(＜式＞＋＜式＞) ＊ (＜式＞＋＜式＞)
になります。
次に式の ＊ が入ってる<式>の定義を見ます。
③ <式> ＊ <式>
<式>の部分には、＋の入ってる(＜式＞＋＜式＞)に置き換えます。
③(＜式＞＋＜式＞) ＊ (＜式＞＋＜式＞)となります。
比較すると
ウ、(＜式＞＋＜式＞) ＊(＜式＞＋＜式＞)
③ (＜式＞＋＜式＞) ＊(＜式＞＋＜式＞)
一致しました。
よってウは、正解です。
最後にエを確認の為にチェックします。
エ、（A＊B)＋(C＊D)
＊が入ってるので
＜式＞＊＜式＞ の定義に置き換えます。
(＜式＞＊＜式＞) ＋ (＜式＞＊＜式＞)
次に + の定義の式(<式> ＋ <式>)見ての <式> 部分を ＊ の付いてる <式> ＊ <式>を代入してみます。
(＜式＞＊＜式＞ ＋ ＜式＞＊＜式＞ )
これを比べると
エ、(＜式＞＊＜式＞) ＋ (＜式＞＊＜式＞)
②、(＜式＞＊＜式＞ ＋ ＜式＞＊＜式＞ )
似てますがエは、左辺と右辺を（）でくくってますが②定義は両端に () があるだけなので一致しません。
よって エは間違い。
以上で、正解は、ウとなります。