目次（まとめ）
- 「バッカス・ナウワ記法」は、2人の学者によって発明された言語
- 「バッカス・ナウワ記法」とは、非終端記号と終端記号からなる文法を定義するための言語
- 「再帰」を理解して「バッカス・ナウワ記法」の問題を理解する
- 参考文献



こんにちは、みっちゃんです。

今回の記事では、情報処理試験で問われる「バッカス・ナウワ記法」を紹介したいと思います。

「バッカス・ナウワ記法」の理解には、「再帰」という概念の理解が必要です。

「バッカス・ナウワ記法」は、2人の学者によって発明された言語

「バッカス・ナウワ記法（BNF記法: Backus-Naur form）」は、アメリカ人数学者のジョン・ワーナー・バッカス（John Warner Backus）さんと、デンマーク人のコンピュータ科学者のピーター・ナウア（Peter Naur）さんによって、発明されました。

バッカスさんは、昔のプログラミング言語であるFORTRANの発明者としても知られています。

「バッカス・ナウワ記法」とは、非終端記号と終端記号からなる文法を定義するための言語

「バッカス・ナウワ記法」にしたがうと、私たちが普段つかっている「数字」は以下のように表現することができます。

＜数字＞::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

ここで、"< >"で囲まれている記号（ここでは「数字」）は「非終端記号」と呼ばれ、右辺にある0〜9で置き換えられます。

一方で、右辺の0〜9は、置き換えられることがないので「終端記号」と呼ばれます。

置き換えられることがないというのは、例えば、0が5になったりしないということです。

また、"|"は「または」という意味を表しています。

したがって、この表現で表しているのは「<数字>という記号は、0〜9のいずれかの数字で表される」ということです。

「再帰」を理解して「バッカス・ナウワ記法」の問題を理解する

ここでは、平成29年度秋期応用処理技術者試験で出題された問題を取り上げて、解説します。

【問題】
次のBNFにおいて非終端記号<A>から生成される文字列はどれか。

<R0> ::= 0 | 3 | 6 | 9
<R1> ::= 1 | 4 | 7
<R2> ::= 2 | 5 | 8

<A> ::= <R0> | <A><R0> | <B><R2> | <C><R1>
<B> ::= <R1> | <A><R1> | <B><R0> | <C><R2>
<C> ::= <R2> | <A><R2> | <B><R1> | <C><R0>

【選択肢】
ア　123          イ　124          ウ　127          エ　128

問われているのは「非終端記号<A>から生成される文字列」なので、まずは<A>で生成される文字列を考えます。

<A>は、 <R0> か <A><R0> か <B><R2> か <C><R1> です。

(i) <A>が<R0>の場合
<A>は0, 3, 6, 9のどれかになるので不適です。

(ii) <A>が<A><R0>の場合
この時に「再帰」について考える必要があります。

<A>は、 <R0> か <A><R0> か <B><R2> か <C><R1> なので、以下に示すような可能性があります。

<R0><R0> か <A><R0><R0> か <B><R2><R0> か <C><R1><R0>

選択肢をみると、どれも"12"から始まる3文字なので、2文字しか生成されない<R0><R0>は除外できます。

また、問題文から、<A>は<R0>に、<B>は<R1>に、<C>は<R2>に置き換えられるということがわかります。

数字を照らし合わせると、<B><R2><R0>で、選択肢アの"123"が生成されることがわかります。

したがって、答えは（ア）になります。

参考文献

きたみりゅうじ「キタミ式イラストIT塾 応用情報技術者」技術評論社