最終更新日:2026年10月27日
fe fe-technology programming pseudocode
まず結論
BNF(バッカス・ナウア記法)は、プログラム言語などの文法上、どんな並びが許されるかを表す記法です。
科目Aでは、記号を読んで文字列が規則に合うかを判定します。特に先頭に使える文字と後ろに追加できる文字を分けて見ると、選択肢を切りやすくなります。
直感的な説明
例えば、架空の言語で使う変数名を「最初はA〜Fの英字、その後はA〜F・数字・アンダースコアを追加できる」と決めたとします。
次の図は、規則に合う名前を少しずつ作るイメージです。
変数名を1文字ずつ作る
最初のFは英字。後ろの5・_・1は、いずれも追加可能な文字です。
反対に、_B39 や 3E5 は、最初の文字が規則に合わないため不適切です。
定義・仕組み
BNFでは、次の記号を使います。
| 記号 | 意味 | 読み方 |
|---|---|---|
::= |
定義する | 左辺は右辺の形で表せる |
| |
選択肢(または) | いずれかを選べる |
<英字> など |
非終端記号 | さらに別の規則へ展開できる名前 |
例えば、次の規則を考えます。
<数字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<英字> ::= A | B | C | D | E | F
<英数字> ::= <英字> | <数字> | _
<変数名> ::= <英字> | <変数名><英数字>
<変数名> の定義には、<変数名> 自身が登場します。これは再帰的な定義です。
<変数名> ::= <英字>:英字1文字で名前を作れる<変数名> ::= <変数名><英数字>:すでにできた名前の後ろに、英数字を1文字付け足せる
この2つを合わせると、英字1文字で始まり、後ろに0文字以上の英数字を続けられるという意味になります。ここでの「英数字」には、定義に従って _ も含まれます。
Pythonで同じ規則を判定する
次は、この例で決めたBNFの規則をPythonで確かめるコードです。Python言語そのものの変数名の規則とは異なります。
def valid_name(name):
first = "ABCDEF"
following = "ABCDEF0123456789_"
if not name:
return False
return name[0] in first and all(
char in following for char in name[1:]
)
for name in ["_B39", "246", "3E5", "F5_1"]:
print(name, valid_name(name))
_B39 False
246 False
3E5 False
F5_1 True
見るポイント: 先頭の1文字だけ判定条件が異なります。
科目Aでどう出る?
構文規則と候補文字列が与えられたら、次の順番で調べます。
- 開始部分を確認する:
<変数名>は何から始まれるか。 - 追加可能な部分を確認する:後ろには何を続けられるか。
- 先頭から順に照合する:途中で規則に合わなければ、その候補を除外する。
この例では、先頭がA〜Fでない候補はすぐ除外できます。
| 候補 | 判定 | 理由 |
|---|---|---|
_B39 |
× | 先頭がアンダースコア |
246 |
× | 先頭が数字 |
3E5 |
× | 先頭が数字 |
F5_1 |
○ | 先頭がF、残りも許可文字 |
「途中で使える文字」と「先頭に使える文字」は同じとは限らない、という点が判断の中心です。
式を組み立てる規則では、括弧も規則どおり
変数名だけでなく、複数の式を組み合わせるBNFもあります。次は説明用に作った独立した例です。
<式> ::= <変数> | (<式>-<式>) | <式>/<式>
<変数> ::= P | Q | R | S
この規則では、引き算は (<式>-<式>) の形で全体を括弧で囲み、割り算は <式>/<式> の形で組み合わせます。
例えば、(P-Q)/(R-S) は次の順番で生成できます。
式を1段ずつ生成する
<式>
↓ 割り算の規則を選ぶ
<式>/<式>
↓ 左右とも引き算の規則を選ぶ
(<式>-<式>)/(<式>-<式>)
↓ 変数をP・Q・R・Sに展開
(P-Q)/(R-S)
見るポイント: 規則を選ぶたびに、<式> がどの形へ展開されたかを確認します。括弧は引き算の規則に含まれているので、この位置に現れます。
| 候補 | 生成できる? | 判断 |
|---|---|---|
(P-Q)/(R-S) |
○ | 括弧付きの引き算を2つ作り、割り算で結ぶ |
P/Q |
○ | 割り算の規則をそのまま使う |
P-(Q-R) |
× | 引き算全体を囲む括弧がない |
(P/Q) |
× | 割り算全体だけを括弧で囲む規則がない |
数式として計算できる形でも、BNFにない括弧を自由に追加したり、省略したりはできません。
実際に触ってみる:再帰規則を展開する
次は、平成20年春期の科目A相当の過去問で扱われた、別のBNF規則です。
<S> ::= 01 | 0<S>1
01 を選ぶと展開終了、0<S>1 を選ぶと左右に0と1を一つずつ増やせます。スライダーを動かして、途中の <S> がどう変わるか確認しましょう。
展開回数を変えて確認
生成される文字列
0001110が3個 + 1が3個
展開の流れ
<S> → 0<S>1 → 00<S>11 → 000111
青い <S> が、まだ置き換えられる部分です。最後に 01 を選んで終了します。
選択肢を切る基準: この規則では、0と1が同数であるだけでは不十分です。0が先に連続し、その後に同じ個数の1が連続する必要があります。例えば 0101 は0と1が2個ずつですが、生成できません。
どんな場面で使う?
BNFは、プログラミング言語の構文や、入力文字列の形式を定義するときに使われます。
例えば、言語の仕様書では「式」「命令」「識別子」などが、どのような要素の組合せでできているかを表せます。
なお、BNFで表すのは文法上の形です。書かれたプログラムの計算結果が正しいか、変数の型が適切か、といった意味的な正しさをBNFだけで保証するわけではありません。
よくある誤解・混同
| は文字列にそのまま入る?
いいえ。ここでは「または」を表す記号です。A | B は、AまたはBを選べるという意味です。
<変数名><英数字> は、必ず2文字だけ?
いいえ。<変数名> 自体を再び展開できるため、3文字、4文字と長くできます。
アンダースコアが使えるなら、先頭にも置ける?
いいえ。今回の規則ではアンダースコアは追加する文字には使えますが、最初の英字の代わりにはなりません。
式に括弧を自由に付けてもよい?
いいえ。そのBNFが許す位置にしか括弧を付けられません。上の式の例では、P/Q は生成できますが、(P/Q) は生成できません。一方、引き算は (P-Q) の形が必要です。
BNFの再帰と、再帰関数は同じ?
どちらも自分自身を参照する形ですが、役割は異なります。BNFの再帰は文法を定義する方法、再帰関数は関数が自分自身を呼び出して処理する方法です。後者は再帰処理の解説で確認できます。
まとめ(試験直前用)
- BNFは許される文字列の構造を定義する記法
::=は定義、|は「または」- 右辺に自分自身が出てきたら、再帰的に繰り返せる形を確認する
- 選択肢は先頭文字の制約から調べると速い
- 式の規則では括弧の有無や位置も照合する。普段の数式の書き方で補わない
- BNFの文法チェックと、プログラムの意味的な正しさは別