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
記号の意味がわかったのでこれに説明に付け加えます。
<式>というのは
① <変数>
または
②(<式> + <式>)
または
③ <式> * <式>
という3種類(うちどれでもよい)を定義します。
という意味。
<変数>というのは
①A
または
②B
または
③C
または
④D
という4種類(うちどれでもよい)を定義します。
という意味。
なのでもし解答の選択肢に ア、A という解答があれば ア が正解です。
◆ア、Aが正解になる解法
<式> は、<変数> と定義される。
<変数>は、A と定義される。
よって<式> = A
という手順で導き出せます。
しかしそれほど問題は甘くないので(笑)
この4種類から選ばないといけません。
ア、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)
*が入ってるので
<式>*<式> の定義に置き換えます。
(<式>*<式>) + (<式>*<式>)
次に + の定義の式(<式> + <式>)見ての <式> 部分を * の付いてる <式> * <式>を代入してみます。
(<式>*<式> + <式>*<式> )
これを比べると
エ、(<式>*<式>) + (<式>*<式>)
②、(<式>*<式> + <式>*<式> )
似てますがエは、左辺と右辺を()でくくってますが②定義は両端に () があるだけなので一致しません。
よって エは間違い。
以上で、正解は、ウとなります。