BNF（Backus-Naur form）

分類

テクノロジ系 基礎理論

出る試験

基本情報応用情報

重要度

★★★☆☆

もう少し詳しい説明

BNFは、「正しい書き方」を文字で定義するための記法です。バッカス・ナウア記法ともいい、プログラミング言語の文法を説明するときに使われます。

読むのに必要な記号は3つだけです。

• ::= … 「左辺とは、右辺のことである」と定義する記号
• | … 「または」。右辺に当てはまる形を並べる
• < > … 囲まれたものはまだ分解できるもの。囲まれていないものは、それ以上分解しない文字そのもの

いちばん短い例です。

<数字> ::= 0 | 1 | 2

「<数字> とは、0 または 1 または 2 のことである」と読みます。<数字> は囲まれているので、まだ中身がある。0 や 1 は囲まれていないので、それが答えそのものです。

実際の試験では 9 まで並びますが、ここでは短くするため 3つにしています。

自分自身を使って定義する

BNFの山場はここです。定義の右辺に、定義しようとしているもの自身を書けます。

変数名のような「名前」を定義してみます。使う部品は <文字> と <数字> の2つです。

<文字> ::= a | b | c
<数字> ::= 0 | 1 | 2
<名前> ::= <文字> | <名前> <数字>

3行目をそのまま読み下すと、こうなります。

<名前> とは、<文字> 1つ。または、<名前> のうしろに <数字> を1つ足したもの。

自分の定義に自分が出てきます。堂々めぐりに見えますが、| の左側に逃げ道（<文字> 1つだけの形）があるので止まります。

この3行が表しているのは「文字1つで始まり、そのうしろに数字が何個か続く」という決まりです。

• 作れる … a ／ a1 ／ a12 ／ c201
• 作れない … 1a（数字で始まっている）／ ab（2文字目に文字を置く形が定義に無い）

長さの決まっていないものを、たった1行で書き切れる。 これが自分自身を使って定義することの値打ちです。

1手ずつ展開してみる

「a12」が <名前> から作れるかを確かめます。<名前> から出発して、1回に1か所だけ置きかえます。

枠の幅が、その記号が最後に受け持つ文字数です。そのため、置きかえられた記号の真下に、それがなった記号が並びます。

1手目を見てください。1行目の <名前> は3文字ぶんの幅があり、2行目ではそれが <名前>（2文字ぶん）と <数字>（1文字ぶん）に分かれています。上の1つが、下の2つになったということです。右端の <数字> はそれ以降ずっと同じ列にいるので、動いていないことも見て分かります。

色の決まりは2つです。

• オレンジの太枠に下線 … 次の手で置きかえる記号
• 緑の枠 … その手で新しくできた記号

3手目で逃げ道を使っています。ここで止めなければ <名前> がいつまでも残り、終わりません。逃げ道をいつ使うかで、数字が何個付くかが決まります。

木の形で書くとこうなる

「どの記号から、どの記号ができたか」を線でつなぐと、木の形になります。これが構文木で、応用情報ではこの形で問われることもあります。

<名前>
 ├ <名前>
 │ ├ <名前>
 │ │ └ <文字> → a
 │ └ <数字> → 1
 └ <数字> → 2

枝分かれ1回が、置きかえ1回です。いちばん外側の <名前> が <名前> と <数字> の2つに分かれ、その内側の <名前> がまた2つに分かれ、最後は <文字> 1つで止まっています。

いちばん下の端（葉）を左から読むと a・1・2 で、できあがる文字列になります。

左へ左へ降りていくと、必ず <文字> に行き着きます。これが「先頭は必ず文字になる」ということを、形で見たものです。

数字が何個付くかは、いつ止めるかで決まる

<名前> を何回ふくらませてから逃げ道を使うか。違いはそれだけです。

逃げ道を使わないかぎり <名前> が残り続けるので、何手でも続けられます。これが「長さの決まっていないものを、たった1行で書ける」ということです。

なぜ先頭が必ず文字になるのか

<名前> の右辺は <文字> と <名前> <数字> の2つですが、どちらも左端が <文字> か <名前> です。<名前> をまた開いても同じことが起きるので、何回たどっても、いちばん左には <文字> が残り続けます。

多くのプログラミング言語で変数名を数字で始められないのは、文法がこの形で決められているからです。

このことは、解くときにそのまま使えます。当てはまらないことを示すのに、全部展開する必要はありません。1a なら、いちばん左に来られるのは <文字> だけなので、先頭の1文字を見た時点で終わりです。

書く側と、読む側

BNFが正しいものの作り方を書くのに対して、オートマトンは与えられたものが正しいかを判定する機械です。同じことを逆から見ています。

コンパイラは、この両方を使っています。書かれたプログラムを1文字ずつ読んで単語に切り分け（オートマトンの仕事）、その単語の並びが文法どおりかを調べる（BNFで定義された決まりとの照合）。文法エラーは、この照合で行き止まったという報告です。

試験ではこう出る

科目A（旧・午前）の基礎理論で出ます。ほとんどが、BNFを与えて「これに当てはまる（当てはまらない）ものはどれか」を選ばせる形です。

解くときは、選択肢を1つずつ定義に当てはめて展開します。順番としては、先頭の文字 → 定義に出てこない文字が混じっていないか → 長さや並びの条件の順に見ると、たいてい展開する前に絞れます。全部を丁寧に追うのは、最後に残った1つか2つだけで十分です。

応用情報では、構文図式（同じ決まりを矢印の図で表したもの）との読み替えや、再帰的な定義（定義の中で、自分自身をもう一度使う書き方）がどこまでの範囲を表すかを問う形に広がります。

関連する用語

オートマトン

文字列を1文字ずつ読んで正しいかを判定する機械。BNFとは、作る側と判定する側の関係にある

正規表現

文字列の形を短い式で表す書き方。BNFより表せる範囲は狭いが、書くのは手短で済む

逆ポーランド記法

式の書き方の一つ。式の構文をBNFで定義すると、かっこの要る形と要らない形の違いが見える

コンパイラ

原始プログラムを機械語に翻訳するソフトウェア。構文の決まりに合っているかを、この形の定義に照らして調べる

ミニクイズ

この分野をまとめて解く → 基礎理論と情報メディアのミニテスト（全39問）

最終更新：2026-10-04