目次(まとめ)
- 「バッカス・ナウワ記法」は、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塾 応用情報技術者」技術評論社