・BNF記法って何??
・例題を用いて分かりやすい説明が欲しい
・簡易的な解説だとわからなかった
今回の記事では、上記のような方に有意義な記事です。基本・応用情報技術者試験の過去問を用いて丁寧すぎる解説をしていきます。
BNF(バッカスナウア記法)とは
BNFは「文脈自由文法を定義するのに使われる文法」のことです。
BNF記法で使われる記号
まずは、BNF記法に出てくる記号の意味を確認しておきましょう。
非終端記号 ‘ < > ‘
< > で囲まれた記号が、非終端記号であることを示す記号です。
<ワイン> のように使用します。
※非終端記号や開始記号等の意味が分からない方は、【形式言語】文脈自由文法を例題を用いて丁寧に解説 をご確認ください。
論理和記号 ‘ | ‘
‘または’ を意味する記号です。
yes | no のように使用します。
定義記号 ‘ ::= ‘
定義するための記号です。
<ワイン> ::= <白ワイン> | <赤ワイン> のように使用します。
これは、<ワイン>は<白ワイン>か<赤ワイン>のどちらかに置き換え可能という意味になります。
BNFの例題
それでは、いよいよ例題を見ていきましょう。
問題の意味
ここで、<> ::= 〇| 〇〇|×× みたいな部分が全て定義式であることを表し、選択肢の ‘ア~エ’ はその定義式から生成された文字列であることを意味します。
この問題では、<A>を開始記号としたとき、「選択肢のどの文字列なら生成されうるか」を問うています。
解答
選択肢の変換
まずは、ア~エの選択肢を非終端記号に変換してみます。すると、
- ア : 123 → <R1><R2><R0>
- イ : 124 → <R1><R2><R1>
- ウ : 127 → <R1><R2><R1>
- エ : 128 → <R1><R2><R2>
のようになりますね。(この作業は数秒で出来る)
選択肢を絞る
ここで、イ, ウ の変換結果が同一であることがわかりますね。答えは一つしか存在しないので、イ, ウは間違いであるとわかります。
選択肢の確認(答えの確定)
では、順に選択肢を確かめていきましょう。今回のBNF記法では、一番右側の記号から順に確定されます。(<A> , <B> , <C>のどの変換も右側が終端記号になっているため。(確かめてもらえばわかります) )
なので、ア の選択肢を確認する場合は、まずは<〇><R0>になる変換を選び、次に<〇><R2>になる変換を選べばいいという訳です。すると、
<A> → <A><R0> → <B><R2><R0> → <R1><R2><R0>
となり、無事に変換できたということになります。
ゆえに、答えは ア です。
他の選択肢の確認
理解を深めるため、エ も一応見ておきましょう。
エ の選択肢を確認する場合は、まずは<〇><R2>になる変換を選び、次も<〇><R2>になる変換を選ばばいいです。すると、
<A> → <B><R2> → <C><R2><R2> → <R2><R2><R2>
となり、変換できませんので、生成不可となります。
まとめ
BNF記法の問題は慣れてしまえば、短時間で解けるものが多いです。問題を何問かこなして、得点源にしていきましょう。
コメント
いつも拝見させていただいております。
大変わかりやすい説明で、いつもとても助かっているのですが、下記部分の書いてある内容が、私の理解力不足のためによくわかりませんでした。
選択肢の確認(答えの確定)の
「( , , のどの変換も右側が終端記号になっているため。(確かめてもらえばわかります) )」
どの変換も右側が終端記号というのは、どういう意味なのでしょうか。
詳説頂けるとありがたいです。
よろしくお願い致します。
嬉しいお言葉誠にありがとうございます。
質問についてですが、
<A><B><C>の変換先の右側(例えば、<A>::=<A><R0>の場合は、<R0>を指す)である「<R1>, <R2>, <R0>」の変換先は、いずれも、0 ~ 9 いずれかの数字であり、数字ということはこれ以上変換のしようがない終端記号です。
そのため、「<R1>, <R2>, <R0>」は実質的に終端記号のようであるといえます。
この場合、ア.123 を確認したい場合、3から見ていき、3に変換可能なのは<R0>なので、アが正解なのであれば、まず<〇><R0>になる変換が選ばれる必要があります。
そのため、「ア の選択肢を確認する場合は、まずは<〇><R0>になる変換を選び、次に<〇><R2>になる変換を選べばいいという訳です。」
と解説させていただいております。
BNFについて調べていてこのページに辿り着きました。
大変わかりやすく感謝しております。
一点疑問なのですが「他の選択肢の確認」のところで2回目の変換後、と
なっていますが、最後のはどこから得られるのでしょうか?
初学者以前の状態なので素人すぎる質問なのかもしれませんが、お時間ありましたら
教えていただければ幸いです。引き続き、他のページでも勉強させていただきます。
ありがとうございました。
上記コメントさせていただきましたが、記号が読めなかったようで
記号部分コピペで再送いたします。
*該当部分の「あーるゼロ」に関する質問です。
以下、再送
一点疑問なのですが「他の選択肢の確認」のところで2回目の変換後、
となっていますが、最後の<R0>はどこから得られるの
でしょうか?
コメントありがとうございます。
お役に立ててよかったです。
大変申し訳ございません。R0ではなく、R2の間違いです。
間違えてしまっていた箇所修正させて頂きました。
ご迷惑をお掛けしました💦
迅速な回答ありがとうございました。
引き続き、楽しみに閲覧させていただきます!
こちらこそ、ご覧頂きありがとうございます!