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

BNF（バッカス・ナウア記法）の意味

プログラミング言語などの構文規則を形式的・再帰的に定義する記法。「::=」で定義を表し、複数の候補は「|」で区切る。基本情報では、与えられたBNF規則から生成できる文字列を判定する問題が出る。

BNF（バッカス・ナウア記法）の具体例

<数字列> ::= <数字> | <数字列><数字> という規則は、「数字1文字」または「数字列の後ろにさらに数字を1文字続けたもの」を数字列と定義しており、これにより任意の桁数の数字列が再帰的に表現できる。

BNF（バッカス・ナウア記法）は試験でどう引っ掛けられる？

「::=」の左辺は非終端記号で、「|」は選択肢の区切りであり「かつ」ではない。自分自身を含む再帰的定義は長さ無制限の文字列を生成できる。候補の文字列を1つずつ規則に当てはめて導出できるか確かめるのが確実。

BNF（バッカス・ナウア記法）が出た過去問

• 次のBNFで定義される＜変数名＞に合致するものはどれか。 ＜数字＞::=0｜1｜2｜3｜4｜5｜6｜7｜8｜9 ＜英字＞::=A｜B｜C｜D｜E｜F ＜英数字＞…

  正解：F5_1

  要点：BNFの再帰定義は「先頭要素」と「繰り返し可能な要素」を分けて読む

  この定義では＜変数名＞は必ず＜英字＞（A〜F）から始まり、2文字目以降は＜英数字＞（A〜F、0〜9、アンダースコア）を何文字でも続けられる再帰構造になっている。したがって「先頭が A〜F のいずれか」「2文字目以降は A〜F・数字・アンダースコアのみ」という2条件を同時に満たす文字列だけが合致する。先頭が英字 F で、以降が数字・アンダースコア・数字である文字列がこれを満たす。

  出典：令和1年度 秋期 基本情報技術者試験 午前 問7（IPA）