【応用情報】バッカス・ナウア記法（BNF）の問題を解く！

   

おはようございます。おーみんです。

皆さんはバッカス・ナウア記法というものをご存知でしょうか？

よく応用情報技術者などの情報処理試験に出題される分野なのですが、意外と難しく、理解しにくい内容だと思います。

バッカス・ナウア記法とは？

バッカス・ナウア記法とは、文脈自由文法を定義するのに用いられるメタ言語のことで、一般にBNFやBN記法と略される。（ウィキペディアより引用） 

まあ何言ってるかさっぱりですな（笑）

要はプログラム言語の構文を記述する方法とでも考えておけばいいでしょう。

しかしながら、応用情報の試験問題などを解く際はバッカス・ナウア記法がどういうものなのか知っている必要はありません。

実際の出題例を見てみましょう。

応用情報 平成29年春期 午前問4

【問題】

あるプログラム言語において、識別子（identifier）は、先頭が英字で始まり、それ以降に任意個の英数字が続く文字列である。これをBNFで定義したとき、?に入るものはどれか。

<digit>:: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<letter>:: = A | B | C | ... | X | Y | Z | a | b | c | ... | x | y | z

<identifier>:: = ?

【選択肢】

ア：<letter> | <digit> | <identifier><letter> | <identifier><digit>

イ：<letter> | <digit> | <letter><identifier> | <identifier><digit>

ウ：<letter> | <identifier><digit>

エ：<letter> | <identifier><digit> | <identifier><letter>

【問題の解説】

まずは式の意味から見ていきましょう。

::→定義するという意味

| →論理和（OR）

<>→非終端記号（他のものと置き換えられるいわゆる変数みたいなもの）

式を見ていくと

<digit>::= の式は0～9のどれかを選ぶという意味、

<letter>::= の式はA～zのどれかを選ぶという意味ですね。

<identifier>は先頭が必ず英字で始まらないといけないようなので、この時点で選択肢のアとイは消えます。

なぜならばアとイでは<letter> | <digit> | ...～と、<digit>が論理和要素になってしまっているからです。

先頭に文字を持ってくる際に<digit>を持ってくる可能性だってあるわけです。よってアとイは消えます。

次にウを見てみましょう。ウかエかは正直なところ迷うでしょう。

ウは一見正解のように見えます。

しかしながら<identifier><digit>ということは2文字目以降は全て数字になってしまいます。なぜなら<digit>の要素は数字だけだから。

よって正解はエです。

実際に選択肢を見てみても、<identifier><digit>、<identifier><letter>の2つがあることで文字も数字も取り出せますね。

最後に

という感じで、理論的な内容を知っていれば情報処理試験のバッカス・ナウアー記法の問題は解けます。

考え方が特殊なので、そこはしっかり訓練が必要ですな(;^_^A