BNFの解法 (FE過去問)

2019年7月15日

基本情報技術者試験の過去問題で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)
*が入ってるので
<式>*<式> の定義に置き換えます。
(<式>*<式>) + (<式>*<式>)
 
次に + の定義の式(<式> + <式>)ての <式> 部分を * の付いてる <式> * <式>を代入してみます。
(<式>*<式> + <式>*<式> )
これを比べると
(<式>*<式>) + (<式>*<式>) 
②、(<式>*<式> + <式>*<式> )
似てますがは、左辺と右辺を()でくくってますが②定義は両端に () があるだけなので一致しません。
よって は間違い。
 
以上で、正解は、ウとなります。
 
 
 
 
 
 
 

日記

Posted by syunsuke-go