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

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

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

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

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

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

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

BNF（バッカス・ナウア記法）と関連する用語

• 構文解析

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

• 次のBNFにおいて非終端記号<A>から生成される文字列はどれか。 <R0> ::= 0 | 3 | 6 | 9 <R1> ::= 1 | 4 | 7 <R2> …

  正解：123

  要点：<A>は桁の和が3の倍数になる数字列を生成する

  このBNFでは<R0>が3で割った余り0の数字、<R1>が余り1、<R2>が余り2の数字を表す。<A>の定義は、生成される数字列の各桁の和を3で割った余りが0になる形だけを許すようになっており、結果として<A>は3の倍数を表す数字列を生成する。123は各桁の和が1+2+3=6で3の倍数なので<A>から導出できる。

  出典：平成29年度 秋期 応用情報技術者試験 午前 問2（IPA）

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

  正解：<letter>｜<identifier><digit>｜<identifier><letter>

  要点：識別子のBNFは英字の基底と末尾に英数字を足す左再帰で表す

  識別子は「英字1文字」から始まり、そこに英字または数字を任意個だけ後ろへ付け足した文字列である。これを左再帰のBNFで書くと、基底が<letter>、再帰規則が「識別子の後ろに数字」と「識別子の後ろに英字」の2つになる。この3つの選択肢をもつ定義が正解である。

  出典：平成29年度 春期 応用情報技術者試験 午前 問4（IPA）

• 次に示す記述は，BNFで表現されたあるプログラム言語の構文の一部である。＜パラメタ指定＞として，適切なものはどれか。 ＜パラメタ指定＞ ::= ＜パラメタ＞|(…

  正解：((abc，def)，ghi)

  要点：BNFの再帰は左側だけ、右側は必ず英字列という制約を読む。

  この構文では、パラメタ指定は単独のパラメタか、または「(パラメタ指定，パラメタ)」の形に限られる。括弧内は必ずカンマで区切られた2要素で、左側だけが再帰的にパラメタ指定になれる点が鍵である。正解の式は、外側が「(パラメタ指定，パラメタ)」で左が入れ子の括弧付き表現、右が英字の並びとなっており、定義に適合する。

  出典：平成30年度 秋期 応用情報技術者試験 午前 問4（IPA）