基本情報のBNFと構文図の解き方を導出例で理解する

基本情報のBNFと構文図は、どちらも「決められた規則から、その文字列を作れるか」を確かめるための表現です。BNFでは名前を規則の右辺へ置き換え、構文図では入口から出口まで矢印をたどります。最後まで作れた文字列と、候補の文字列が完全に一致すれば正しいと判断できます。

この記事では、小さな教材用の文法を使い、Aの1文字で終わる場合、A01のように数字を追加する場合、AAや01を作れない理由を順に確認します。同じ文法を構文図の経路でも追い、記号の暗記から自分で判定できる段階へ進みましょう。

基本情報のBNFと構文図の読み方を具体例でつかむ

BNFの記号は「定義・選択・連結」で読む

BNFはBackus–Naur Form（バッカス・ナウア記法）の略で、文法を規則として記述する方法です。まずは、左辺の名前を右辺の形へ置き換えると読んでください。計算の等式として値を求めるものではありません。

書き方	この記事での意味	読み方の例
<名前>	規則で置き換える非終端記号	文字列を作る途中の部品名
::=	左辺を右辺で定義する	<英字> ::= A は、<英字>をAにできる
|	選択肢の区切り	A | B は、AまたはBのどちらか
<名前><数字>	左の部品の後ろに右の部品を連結	名前の後ろへ数字を1個足す
A、B、0、1	完成した文字列に残る終端記号	これ以上置き換えない実際の文字

縦棒は完成品の中に書き込む文字ではなく、規則を選ぶための区切りです。部品を横に並べた場合も、並んだ部品を両方使う点が違います。「または」と「続けて」を分けると、規則を読み違えにくくなります。

教材用の文法を3行で定義する

ここからは、次の自作の文法だけを使います。開始記号は<名前>です。実在するプログラミング言語の変数名規則や、試験の過去問をそのまま示したものではありません。

<英字> ::= A | B
<数字> ::= 0 | 1
<名前> ::= <英字> | <名前><数字>

この文法の<英字>はAとBだけ、<数字>は0と1だけです。Cや2まで使えるとは考えません。また、規則を読みやすくする空白は完成する名前に含めず、候補の「A01」は3文字の並びとして扱います。

<名前>の右辺は、<英字>で終える形と、<名前>の後ろに<数字>を足す形の二択です。したがって、作れるのは最初がAまたはBの1文字で、その後ろに0または1が0個以上続く文字列です。数字を追加しないAやBも含まれます。

AとA01を実際に導出する

非終端記号を規則に従って置き換え、文字列を作ることを「導出」といいます。まずAだけを作るなら、<名前>から再帰しない<英字>を選び、その後Aを選べば完成です。

<名前> → <英字> → A

A01を作るときは、数字を二つ置く場所が必要です。ここでは毎回、いちばん左の非終端記号を一つずつ置き換えます。矢印は導出の説明記号で、完成する名前には含めません。

段階	置き換え後の形	選んだ規則
開始	<名前>	開始記号から始める
1	<名前><数字>	数字を1個足す形
2	<名前><数字><数字>	残った<名前>でもう一度、数字を足す形
3	<英字><数字><数字>	<名前>を<英字>にして再帰を終える
4	A<数字><数字>	<英字>をAに置き換える
5	A0<数字>	最初の<数字>を0に置き換える
6	A01	最後の<数字>を1に置き換える

段階2の時点では、まだ非終端記号が残っています。文字数が候補と同じに見えても完成ではありません。段階6で終端記号だけになり、候補のA01と一致して初めて「作れる」と確認できます。

この文法では、再帰側を選んだ回数が、先頭の英字の後ろに付く数字の個数になります。数字を2個付けるA01なら、再帰側を2回選びます。

BNFの再帰とEBNFの省略・反復記号を分ける

今回のBNFでは、自分自身の<名前>を右辺に含む規則で繰り返しを表しました。止めるときは、<名前>を含まない<英字>側を選びます。自分自身が現れるからといって、無限に展開し続けなければならないわけではありません。

一方、EBNF（拡張BNF）などでは、反復や省略を専用の記号で短く書く流儀があります。たとえば「{ X }はXを0回以上繰り返す」と定めた記法なら、今回の<名前>は「<英字> { <数字> }」とも表せます。ただし、[ ]や{ }の意味が、すべての文法で同じとは限りません。

実際に、Python公式リファレンスの記法説明では、[ ]を省略可能、*を0回以上、+を1回以上と定義しています。これはその資料の取り決めです。試験では設問の記号説明を先に読み、BNFの再帰と拡張記法の記号を混ぜずに扱いましょう。

関数の引数や戻り値を追う再帰プログラムは別の学習テーマです。そちらで困っている場合は基本情報の再帰関数の読み方を参照し、ここでは文字列を作る規則の展開に集中してください。

基本情報のBNFと構文図で文字列を判定する

上の図は、先ほどの<名前>を経路で表した教材用の構文図です。左が入口、右が出口です。入口の後にある青い箱は<英字>、下側のループ上にある緑の箱は<数字>を表し、それぞれを通るたびに、その規則で作れる文字を1文字読みます。

同じA01を経路と対応させる

入口から進むと、青い箱は必ず通ります。A01なら、ここでAを読みます。その後は出口へ進むか、緑の箱を通って戻るかを選べます。緑の箱を最初に通るときに0、2回目に通るときに1を読み、戻ったところから出口へ進めばA01が完成します。

作る文字列	経路	数字のループ
A	入口→青い箱でA→出口	0回
B1	入口→青い箱でB→緑の箱で1→出口	1回
A01	入口→青い箱でA→緑の箱で0→緑の箱で1→出口	2回

線だけの区間を進むときは、文字を読みません。箱が<数字>のような部品名なら、その部品に対応する規則を使います。今回の<数字>は1文字ですが、別の文法の箱まで必ず1文字とは考えず、設問で定義された単位を確認してください。

分岐で一つの道が行き止まりになっても、別の道で候補を最後まで読めるなら、その候補は作れます。逆に「作れない」と判断するときは、他の経路が残っていないかを確認します。今回の図では、英字の後ろで選べるのが数字だけなので、候補との対応を絞りやすいですね。

ループは0回でもよいか、必ず1回通るかを見る

同じ「戻る矢印」があっても、繰り返す箱を一度も通らず出口へ進める図なら0回を許します。一方、その箱を最初に必ず通り、通過後に戻るか出口へ進むかを選ぶ図なら、最低1回は必要です。戻る線の存在だけで回数を決めないでください。

今回の<名前>は、英字を読んだ後、数字の箱を通らずに出口へ進めます。そのため、数字は0個でもよく、Aは正しい候補です。ただし、英字の箱を避ける経路はありません。数字0個を許すことと、文字列全体が空でもよいことは違います。

空文字は「文字が一つもない文字列」です。この文法には<名前>全体を空にする規則がないため、空文字は作れません。再帰を使わない場合もAかBの1文字が残ります。

作れない候補は、違反する場所を示す

候補を調べるときは、最初の文字、残りに使える文字、最後まで読み切れるかの順に照合します。「なんとなく違う」ではなく、どの規則に反するかを一つ言えるようにしましょう。

候補	判定	BNFと構文図での理由
A、B	作れる	<英字>だけで終えられる。青い箱の後に出口へ進む
A01、B1	作れる	英字の後ろへ、規則内の数字を必要な個数追加できる
01	作れない	先頭にはAかBが必要。入口から数字の箱へ直接進めない
AA	作れない	2文字目以降に英字を足す規則がない。青い箱を再度通れない
A2	作れない	2は<数字>の選択肢にない。緑の箱で2を読めない
空文字	作れない	開始記号から必ず英字が残る。青い箱を飛ばせない

AAの文字はどちらも<英字>ですが、それだけでは正しくなりません。文字の種類だけでなく、その位置で使える規則かどうかが必要です。同様に、A2をAまで読んで出口へ進んでも、2が余るため候補全体を読めたことにはなりません。

先頭と末尾の確認は、誤った候補を早く見つける助けになります。ただし、その2か所が合うだけで正解とは限りません。たとえばA01B1は先頭がA、末尾が1でも、途中のBを追加できないので不正です。

3問で、自分の判定を確かめる

次の3問は、すべてこの記事の自作文法を使う確認問題です。答えを見る前に、作れるものには導出か経路を、作れないものには違反する位置を書いてみてください。

1. B00は作れるか
2. A1Bは作れるか
3. 数字を必ず1個以上付けたいとき、<名前>の規則をどう変えるか

1の答えは「作れる」です。<名前> → <名前><数字> → <名前><数字><数字> → <英字><数字><数字> → B<数字><数字> → B0<数字> → B00と導出できます。構文図では、青い箱でBを読み、緑の箱を2回通って0を一つずつ読みます。

2の答えは「作れない」です。A1までは作れますが、最後のBを追加する規則がありません。構文図でも青い箱へ戻れないので、3文字目のBを読む経路がありません。

3は、最短形を<英字><数字>へ変える方法があります。<英字>と<数字>の規則はそのままにして、<名前>を次のように定義し直します。この確認問題だけの変更で、上の判定表には適用しません。

<名前> ::= <英字><数字> | <名前><数字>

変更後はAやBだけでは終われず、最短でもA0やB1の2文字になります。構文図なら、英字の箱の後に数字の箱を必ず1回通り、そこから数字を繰り返せる形に変えます。規則のどこを変えると、許される最短文字列が変わるかまで確かめると理解が深まります。

基本情報のBNFと構文図は、規則と経路を対応させて解く

BNFでは、開始記号から終端記号だけになるまで規則を展開します。構文図では、候補の文字を順に読みながら矢印を進み、文字を余らせず出口まで到達できるかを確認します。この二つを同じ候補で試すと、再帰とループの対応が見えます。

• 最初に、開始記号と設問独自の記号説明を確認する
• 再帰を終える規則を見つけ、最短の文字列を一つ作る
• 繰り返すたびに、どの文字をどこへ追加するかを追う
• 先頭・途中・末尾を照合し、候補全体が一致したことを確かめる

次は、数字を一つ追加した候補と、途中に英字を追加した候補を自分で作って比べてみてください。基礎理論全体の学習順も整理したい場合は、基本情報の基礎理論を学ぶ順番と勉強法が参考になります。