基本情報 令和元年度 秋期 問7｜テクノロジ系に関する問題

答えは d「`F5_1`」 です。

BNFは「文字の並べ方のルール」を書く記法です。このルールを読むと、

• ＜英字＞はA〜Fのどれか、＜数字＞は0〜9のどれか
• ＜英数字＞は英字・数字・下線 `_` のどれか
• ＜変数名＞は「英字1文字」から始まり、そのあとに英数字を何個でもつなげたもの

つまり先頭が英字（A〜F）なら合格です。

• a `_B39`：先頭が下線 → ×
• b `246`：先頭が数字 → ×
• c `3E5`：先頭が数字 → ×
• d `F5_1`：先頭がF、続く 5・`_`・1 はどれも英数字 → ○

👉 覚え方：再帰の定義は「一番最初に来られるもの」を見る。ここでは＜英字＞だけ。

なぜこれが正解か

正解は d。`<変数名> ::= <英字> | <変数名><英数字>` は再帰的な定義で、次のように読める。

• ＜英字＞1文字だけでも＜変数名＞になる（例：`F`）。
• すでにある＜変数名＞の後ろに＜英数字＞を1文字つなげたものも＜変数名＞になる。

したがって＜変数名＞は「先頭が＜英字＞（A〜F）で、2文字目以降は＜英字＞・＜数字＞・下線のどれか」という文字列。`F5_1` は `F` → `F5` → `F5_` → `F5_1` と、英字から始めて英数字を1文字ずつ足していけるので合致する。

各選択肢の解説

• a `_B39`：下線は＜英数字＞には含まれるが＜英字＞ではないので、先頭には置けない。合致しない。
• b `246`：先頭が＜数字＞。合致しない。
• c `3E5`：先頭が＜数字＞。合致しない。
• d `F5_1`：先頭がF（＜英字＞）、続く 5・`_`・1 はすべて＜英数字＞。合致する（正解）。

覚え方・ひっかけ注意

BNF読解のコツ：

• `::=` は「左辺を右辺で定義する」
• `|` は「または」
• ＜…＞は非終端記号（さらに定義される記号）
• `<X> ::= <A> | <X><B>` の形は「A で始まり、B が0個以上続く」と読む

下線のように、2文字目以降には使えても先頭には使えない文字を選択肢に紛れ込ませるのが定番のひっかけ。英字がA〜Fに限られる点（GやZは使えない）も見落とさない。

理論的背景

BNF（Backus-Naur Form）はJohn BackusとPeter Naurが1960年のALGOL 60規格で導入した形式文法記法。文脈自由文法（Context-Free Grammar：CFG）の表現法で、コンパイラ・インタプリタの構文定義に標準的に用いられる。Chomsky階層ではType 2（文脈自由文法）に位置づけられる。

BNFの拡張記法

• EBNF（Extended BNF）：ISO/IEC 14977標準。`{...}`（繰り返し）、`[...]`（省略可）、`(...)`（グループ化）、`+`（1回以上）等を追加
• ABNF（Augmented BNF）：RFC 5234で規定。インターネット標準仕様の記述に使用（HTTP、SMTP、URI等）
• W3C XML Productions：XML仕様で使われるBNF風記法

構文解析との関係

BNF定義から構文解析器（パーサ）を生成：

• トップダウン構文解析：LL(k)文法 → 再帰下降パーサ、ANTLR
• ボトムアップ構文解析：LR(k)、LALR(1)文法 → yacc／bison、CUP
• PEG（Parsing Expression Grammar）：曖昧性のない代替記法。Packratパーサ

実務での使われ方

• プログラミング言語仕様：C言語規格、Java言語仕様、Pythonリファレンス全てBNFまたは類似記法で構文規定
• プロトコル仕様：HTTP（RFC 7230のABNF）、URI（RFC 3986）、SMTP、SIP、JSON（RFC 8259）
• DSL（Domain Specific Language）：自作言語の構文設計
• 設定ファイル：YAML、TOML、HCL等の構文定義
• コード生成：parser combinator（Haskell Parsec、JavaScript PEG.js）

試験での位置づけ

基本情報・応用情報の基礎理論／コンパイラ分野で頻出。応用情報・データベーススペシャリストではSQL文法、ITスペシャリスト（システム）ではプロトコル仕様読解で使う。

選択肢の発展補足

BNFと類似する形式記法：

• 正規表現（Regex）：Chomsky階層Type 3（正規文法）。文脈自由文法より弱いが、トークン化（字句解析）に最適
• 構文図（Syntax Diagram／Railroad Diagram）：BNFを視覚化
• 正規言語と文脈自由言語の境界：括弧の入れ子マッチは正規表現で表現不可、CFG必須
• 形式言語理論：オートマトン（DFA、NFA、PDA、TM）との対応

字句解析（lex／flex）で正規表現、構文解析（yacc／bison）でBNFを使う2段階パーサ構成がコンパイラの古典的設計。LLVM／Clang／GCCといった現代コンパイラもこの基本構造を保つ。