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

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

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

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

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

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

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

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

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

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

  要点：BNFの再帰は基底＋末尾に1文字追加の形で書き下す

  識別子は先頭が英字で、その後ろに英字か数字が任意個続く。再帰的に書くと、基底は英字1文字だけの場合であり、既にできている識別子の末尾に英字または数字を1つ付け足す規則を加えればよい。先頭に数字が来る形や、後ろに識別子を置く形は定義に合わない。

  出典：平成29年度 春期 高度共通_午前I試験 am1 問2（IPA）