基本情報のBNF・構文図をやさしく解説

基本情報のBNFと構文図は、基礎理論の中でも「見た瞬間に固まる」人が多いテーマです。かっこや縦棒が並んでいるだけに見えたり、構文図の矢印をどこからたどればよいのか分からなかったりすると、問題文を読む前から苦手意識が出やすいですね。

ただ、BNFも構文図も、やっていることは難しい計算ではありません。ルールに従って、作れる文字列と作れない文字列を分けるだけです。この記事では、基本情報のBNFと構文図を初めて見る人向けに、記号の読み方、構文図との対応、選択肢を削る手順までまとめます。

基本情報のBNFと構文図の読み方

BNFは文法の設計図

BNFは、文字列の作り方をルールとして表す記法です。基本情報では、プログラミング言語そのものを深く作るというより、「この文法から、どの文字列が作れるか」を判断する問題として出てきます。つまり、暗記科目というより、置き換えゲームに近いと考えると入りやすいです。

たとえば、ある規則で「式は項に置き換えられる」「項は数字に置き換えられる」と書いてあれば、式から数字までたどれます。反対に、途中でどの規則にも合わない文字が出てきたら、その文字列は作れません。ここを押さえるだけで、BNFの見た目の怖さはかなり減ります。

BNFは「左側の名前を右側の形に置き換えていく表」です。数式の証明というより、材料から完成品を作るレシピとして読むと分かりやすいですね。

基本情報技術者試験の基礎理論では、形式言語や文法に関連する考え方が問われることがあります。最新の出題範囲は、IPAの試験要綱・シラバスで確認できますが、受験勉強としては、まずBNFの記号を読み、選択肢を一つずつ作れるか確認する練習が現実的です。

見る場所	考えること
左側の名前	これから置き換える対象
右側の形	置き換え後に作れる並び
選択肢の文字列	規則だけで作れるかを確認

最初から全体を一気に理解しようとすると、BNFは難しく見えます。まずは「左から右へ置き換える」「置き換えられない文字列は不正」という二つだけを持って、問題文を読むのがおすすめです。この見方に慣れると、構文図に変わっても考え方はほとんど同じだと分かります。

また、練習では短い例から始めるのが大事です。いきなり長い選択肢を展開せず、まず1文字や2文字の文字列を作ってみると、規則の働きが目で追いやすくなります。

記号の意味を先に押さえる

BNFでつまずく一番の原因は、記号の見た目に振り回されることです。特に、山かっこ、縦棒、二重コロンと等号の組み合わせ、角かっこ、中かっこなどが出てくると、どれが何を意味するのか分からなくなります。けれど、基本情報の問題で必要になる意味はかなり限られています。

山かっこで囲まれたものは、まだ別の規則に置き換えられる名前です。縦棒は「または」を表し、どちらか一方を選びます。中かっこは繰り返し、角かっこは省略可能を表す形で使われることがあります。問題によって記号の定義が明示される場合もあるので、必ず問題文の説明を優先してください。

試験では、記号の呼び名を完璧に言えることより、記号を見て「選ぶ」「繰り返す」「省略できる」と判断できることの方が大切です。

記号	読み方の目安
<名前>	別の規則に置き換える名前
::=	左側は右側で定義される
|	どちらかを選ぶ
{ }	同じ形を繰り返せる
[ ]	あってもなくてもよい

ここで注意したいのは、記号を勝手に一般化しすぎないことです。BNF風の記法は教材や問題によって少し表現が違うことがあります。だから、過去問や模擬問題を解くときは、最初に「この問題では各記号をどう定義しているか」を読んでから選択肢を見る方が安全です。

私は、BNFの問題では最初に記号表を小さくメモするのがよいと思います。「縦棒は選択」「中かっこは繰り返し」のように日本語へ直すだけで、問題文の圧が下がります。暗号を読むのではなく、日本語に翻訳してから解くイメージですね。

特に直前期は、記号の名前を暗記するより、問題文の中でどう動くかを言える状態にしましょう。「この部分は選ぶ」「ここは何回か続ける」と説明できれば、選択肢の照合で迷いにくくなります。

非終端記号と終端記号

BNFでよく出る考え方に、非終端記号と終端記号があります。名前は硬いですが、意味はそこまで難しくありません。非終端記号は、まだ置き換えが続く記号です。終端記号は、もうそれ以上置き換えず、最終的な文字列に残る記号です。

たとえば、<数字> や <式> のように山かっこで囲まれているものは、たいてい非終端記号です。一方で、0、1、+、-、a、b のように実際の文字として残るものは終端記号です。問題を解くときは、非終端記号をどんどん置き換えて、最後に終端記号だけの文字列になるかを見ます。

選択肢の文字列と照合するのは、最終的に終端記号だけになった後です。途中に非終端記号が残っている段階で判断しないようにしましょう。

種類	見分け方	解くときの扱い
非終端記号	<式> や <項> のような名前	さらに別の規則へ置き換える
終端記号	実際に並ぶ文字や記号	完成した文字列として残す

この区別を知らないまま解くと、「どこまで置き換えればよいのか」が曖昧になります。特に、選択肢に似たような文字列が並ぶ問題では、途中の形だけを見て合っていると判断しがちです。最後まで置き換えた結果、選択肢と完全に同じ並びになるかを確認するのが基本です。

構文図でも同じで、途中の箱や枝分かれは、まだ処理中のルールだと考えます。ゴールまでたどって初めて、文字列として認められるかが決まります。BNFと構文図を別物として覚えるより、「途中の名前を処理して、完成した文字列を確認する」という共通ルールで見る方が定着しやすいです。

選択肢に非終端記号そのものが残ることは通常ありません。だから、最後に残るのは実際の文字だけか、という視点で見ると、途中で展開を止めてしまうミスを防げます。

再帰定義は繰り返し

BNFで急に難しく感じるのが、再帰定義です。再帰定義とは、定義の中に自分自身が出てくる形です。たとえば <リスト> を定義している右側に、また <リスト> が出てくるようなものですね。プログラミングの再帰関数を思い出す人もいるかもしれません。

ただ、試験問題での見方はもっとシンプルで大丈夫です。自分自身が出てきたら、「同じ形をもう一回続けられる」と読みます。つまり、再帰定義は繰り返しの合図です。1個だけ作れるのか、2個以上つなげられるのか、空でもよいのかを確認すると、選択肢をかなり削れます。

再帰定義は、最初から全部展開しようとせず、短い文字列で試すのがコツです。1回、2回、3回と増やして、どんな並びが作れるかを見ると規則が見えてきます。

• 自分自身が右側に出ているかを見る
• 繰り返す部分の前後に固定文字があるかを見る
• 終わるための別ルールが用意されているかを見る

よくある失敗は、再帰を見た瞬間に無限に続くものだと思ってしまうことです。実際には、どこかで再帰しない選択肢を選べば止まります。たとえば「数字」または「数字とリスト」のような定義なら、数字だけで終わることも、数字を何個も並べることもできます。止め方があるかを探すのが大切です。

再帰定義に苦手意識がある人は、基本情報の再帰関数がわからない人向けの解説で再帰の基本イメージを押さえてから戻ると理解しやすいです。BNFの再帰はプログラムを書く問題ではありませんが、「同じ処理を繰り返し、どこかで止まる」という感覚は共通しています。

再帰を展開するときは、途中経過を一列に書くと混乱しにくいです。どの規則を選んだかを残しておけば、後から「どこで止める選択肢を選ぶべきだったか」も確認できます。

構文図は道順で読む

構文図は、BNFを図にしたものだと考えると分かりやすいです。スタート地点から矢印に沿って進み、ゴールまでたどり着ければ、その道中に通った文字列が正しい形になります。分岐があればどちらかを選び、ループがあれば同じ場所を何度か通れる、という読み方です。

問題では、図を見て「この文字列は作れるか」「正しい構文はどれか」を選ぶ形になりやすいです。BNFより視覚的なので簡単そうに見えますが、分岐やループを見落とすと間違えます。特に、矢印の向きと、同じ場所を何回通ってよいのかを確認することが大切です。

構文図では、文字や記号を暗記するより「スタートからゴールまで本当に通れるか」を一筆書きのように確認するのが近道です。

• スタートとゴールを先に確認する
• 分岐ではどちらを選んだかメモする
• ループは0回でも通れるか確認する
• 選択肢の文字列を左から順に道へ対応させる

BNFと構文図は、基礎理論の中では独立した小テーマに見えます。ただ、考え方は基本情報技術者試験の基礎理論が難しい人向けの勉強法と同じで、抽象的な言葉を具体例に落とすことが重要です。図を見たら、まず短い文字列を一つ作ってみると理解が早くなります。

ここまでが読み方の基本です。次からは、実際の選択肢をどう削るかに進みます。BNFでも構文図でも、全部を完全に展開する必要はありません。最初の文字、途中の分岐、最後の終わり方を見れば、かなりの選択肢は早い段階で消せます。

図の問題で迷う人ほど、きれいに一発で読もうとしがちです。実際には、候補の道を一つ選んで、行き止まりなら戻るだけで十分です。試験中は正確に消去できることを優先しましょう。

基本情報のBNFと構文図の解き方

選択肢を文字で分解する

BNFや構文図の問題では、いきなり正解を探すより、選択肢を文字単位や部品単位に分ける方が安定します。たとえば、英数字や演算子が並んでいる選択肢なら、先頭、途中、末尾に分けて、どの規則で作れるかを確認します。長い文字列を一つの塊として見ると、どこが間違っているのか見つけにくいです。

分解するときは、問題文の規則に出てくる単位に合わせます。<数字>、<英字>、<識別子>、<項> のような名前があるなら、選択肢の文字列をそれらに対応させてみます。対応できない部分が出たら、その選択肢は候補から外せます。

選択肢の上に小さく区切り線を入れるつもりで読むと、BNFの右側と照合しやすくなります。頭の中だけで処理しないのがコツです。

分解する場所	確認すること
先頭	開始記号として許されるか
途中	繰り返しや分岐に合うか
末尾	正しい終わり方になっているか

この考え方は、科目Bの擬似言語にも近いです。擬似言語では処理を一行ずつ追いますが、BNFでは文字列を一部ずつ追います。読み方の練習をしたい人は、基本情報の擬似言語対策でトレースの感覚も押さえておくと、構文問題の分解にも役立ちます。

選択肢を分解する目的は、正解をすぐ当てることではありません。間違いを見つけやすくすることです。作れない文字、余計な記号、足りない終わり方を一つ見つければ、その選択肢は落とせます。残った候補だけを丁寧に展開すれば、時間を使いすぎずに済みます。

もし分解の単位が分からないときは、問題文で名前が付いている部分を手がかりにします。名前が付いている部分は、出題者がそこを一つのまとまりとして見てほしいという合図になりやすいです。焦らず確認しましょう。

最初の文字で候補を削る

BNFと構文図の問題で効くのが、最初の文字を見る方法です。多くの文法では、開始直後に選べる文字や記号が限られています。選択肢の先頭が、その文法で最初に出られない文字なら、そこで不正と判断できます。全部を展開する前に削れるので、時間短縮になります。

たとえば、識別子が「英字で始まり、その後に英字または数字が続く」と定義されているなら、数字で始まる選択肢はその時点で不正です。数値が「符号はあってもなくてもよい、その後に数字が続く」と定義されているなら、先頭の符号や数字を確認します。先頭条件は、もっとも見落としにくい削りポイントです。

迷ったら、まず「この文字列は何で始まれるのか」を確認します。先頭条件に合わない選択肢は、後ろがどれだけ合っていても正解になりません。

• 開始記号から最初に出せる文字を確認する
• 省略可能な部分が先頭にあるか確認する
• 先頭が合わない選択肢を先に消す
• 残った候補だけを詳しく展開する

注意点は、省略可能な部分です。角かっこや空文字を許す規則があると、最初に見える文字が一つ先へ進むことがあります。たとえば、符号が省略できるなら、+ や – で始まる場合も、数字で始まる場合もあります。省略できる部分を飛ばしたとき、次に何が来るかまで見ると安全です。

構文図でも同じです。スタート直後に通れる枝を見て、選択肢の先頭文字がその枝に存在するかを確認します。通れる枝がなければ不正です。複雑な図でも、スタート直後だけなら見る範囲は狭いので、焦って全体を追う前に先頭条件で削るのがおすすめです。

先頭条件で候補が一つに絞れなくても問題ありません。二つ残ったなら、その二つだけを次の文字で比べればよいです。全選択肢を同じ深さまで読む必要はありません。

繰り返しは末尾から見る

先頭条件の次に見たいのが、末尾です。繰り返しを含む文法では、途中が長くなっても、終わり方には特徴が残ります。たとえば、区切り記号の後には必ず項目が必要なのに、選択肢が区切り記号で終わっているなら不正です。末尾を見るだけで消せる選択肢は意外と多いです。

再帰定義やループがあると、中央部分は何回も増えます。そこを全部展開しようとすると大変です。だから、まず最後の1文字や最後の部品を見ます。文法が「数字の列」を作るなら末尾は数字になりやすいですし、「閉じかっこ」で終わる形なら、最後に閉じかっこが必要です。

繰り返し部分だけに注目しすぎると、最後に必要な終端記号を忘れやすいです。ループを抜けた後に何が必要かまで確認しましょう。

末尾の状態	判断の目安
区切り記号で終わる	次の要素が足りない可能性がある
閉じ記号がない	対応する開始記号と合わない可能性がある
余計な文字が残る	どの規則でも消化できない可能性がある

この方法は、特に選択肢が長い問題で効果があります。先頭は合っている、途中もそれっぽい、でも末尾だけ文法と合わないというひっかけがあるからです。最初から順に読んでいると疲れて見落としますが、末尾を別枠で確認すると気づきやすくなります。

私なら、BNFの問題を解くときは「先頭、末尾、中央」の順で見ます。先頭と末尾で消せる選択肢を落とし、残ったものだけ中央の繰り返しを確認します。全部を正面から展開するよりも、試験時間の中ではかなり現実的な解き方かなと思います。

末尾確認は、閉じかっこや区切り記号が出る問題で特に有効です。最後の一手だけを見れば、途中のループを完全に数えなくても、文法として終われない選択肢を見つけられます。

構文図は通れる道を探す

構文図の問題は、図を眺めるだけでは解けません。選択肢の文字を左から順に読み、図の上で同じ順番に通れるかを確認します。通れるなら候補に残し、途中で行き止まりになるなら不正です。図の見た目が複雑でも、やることは通行チェックです。

まず、スタート位置を指で押さえるつもりで確認します。次に、選択肢の先頭文字に対応する道へ進みます。分岐では、どちらを選んだかを軽くメモしておくと戻りやすいです。ループがある場合は、同じ場所に戻って次の文字を消化できるかを見ます。

構文図では、選択肢を一文字読むたびに現在地を動かすとミスが減ります。頭の中だけでワープしないようにしましょう。

よくある間違いは、途中まで通れた時点で正解だと思ってしまうことです。構文図では、最後にゴールまで到達できなければ正しい文字列とはいえません。選択肢の文字をすべて消化した後、出口へ進めるかを必ず確認してください。逆に、文字をすべて消化する前に出口へ着いてしまう場合も不正です。

BNFの置き換えと構文図の道順は、表現が違うだけで同じ判断をしています。BNFでは規則で文字列を作り、構文図では道を通って文字列を作ります。どちらも「作れるか、作れないか」を確認しているだけなので、別々に暗記するより、共通の解き方で整理する方が効率的です。

BNFと構文図で多いミスは、記号の意味を取り違えること、繰り返しの回数を決めつけること、そしてゴール条件を確認しないことです。特に、縦棒を「両方必要」と読んでしまったり、中かっこを「必ず1回以上」と思い込んだりすると、正解から外れやすくなります。

また、問題文に書かれた定義を読まず、普段の教材で見た記号の意味だけで解くのも危険です。BNF風の表記は、問題ごとに補足が付くことがあります。角かっこや中かっこの意味が明示されているなら、その問題の定義に従うのが最優先です。

「見たことがある記号だから大丈夫」と飛ばすのが一番危ないです。試験では、記号の説明文を先に読む癖を付けてください。

• 縦棒を両方必要な条件だと読む
• 省略可能な部分を必須だと思う
• 繰り返しを1回だけに限定する
• 最後に出口へ到達できるか確認しない

ミスを減らすには、解く順番を固定するのが効果的です。問題文の記号説明を読む、開始条件を見る、末尾条件を見る、残った選択肢を一つずつたどる。この順番にすると、毎回同じ手順で判断できます。難問をひらめきで解くより、普通の問題を落とさない方が得点につながります。

BNFや構文図は、得意な人でも一瞬で答えが出るテーマではありません。だからこそ、選択肢を削る根拠を自分で説明できる状態にすることが大切です。「この先頭文字は作れない」「この末尾は出口に行けない」と言えるようになると、迷いがかなり減ります。

基本情報のBNFと構文図まとめ

基本情報のBNFと構文図は、見た目こそ難しそうですが、考え方はかなりシンプルです。BNFは文法ルールに従って文字列を作る表で、構文図はスタートからゴールまで通れる道を表す図です。どちらも、選択肢の文字列がルールどおりに作れるかを確認する問題だと考えましょう。

最初に押さえるべきなのは、記号の意味です。山かっこは置き換える名前、縦棒は選択、中かっこは繰り返し、角かっこは省略可能というように、日本語へ直してから読むと理解しやすくなります。問題文で記号の意味が定義されている場合は、その定義を必ず優先してください。

解くときは、先頭条件、末尾条件、通れる道の順で確認します。全部を展開しなくても、作れない理由を見つければ選択肢は削れます。

• BNFは左側を右側へ置き換える
• 非終端記号はさらに置き換える
• 再帰定義は繰り返しの合図として見る
• 構文図はスタートからゴールまで通れるか確認する
• 選択肢は先頭と末尾から削る

似た図の読み取りが苦手な人は、基本情報のオートマトンと状態遷移図の解き方も合わせて読むと、矢印をたどる感覚がつかみやすいです。BNF、構文図、状態遷移図は分野名こそ違いますが、「ルールに従って進めるか」を見る点ではつながっています。

基本情報のBNFと構文図は、短時間でも点を取りやすくなるテーマです。記号を日本語に直す、短い文字列で試す、通れる道を一つずつ確認する。この3つを意識して、過去問や予想問題で数問だけでも練習してみてください。見た目の難しさより、手順の固定が大切です。

苦手な人は、問題を解いた後に「どの文字で候補を消したか」を一言で書いておくと復習しやすいです。正解番号だけを見るより、消去の理由を残す方が次の問題で再現しやすくなります。