BNFとは？

BNFの意味

プログラム言語などの構文を形式的に記述する記法。::= の左辺に非終端記号、右辺に定義を書き、| で選択肢を並べる。再帰的な定義によって、繰返しや入れ子構造を表現する。

BNFの具体例

「1個以上の数字の並び」は <数字列> ::= <数字> | <数字列><数字> のように、基底（1文字）と再帰（既存の並びに1文字足す）の形で書ける。

BNFは試験でどう引っ掛けられる？

再帰が左側にあるか右側にあるかで、生成される文字列は同じでも構文木の形（結合の向き）が変わる。

BNFと関連する用語

• 有限オートマトン

BNFが出た過去問

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

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

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

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

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