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

答えは d「F51」 です。

BNFは「文法のルール」を書くための記号です。今回のルールは：

• 変数名は英字で始まる
• その後に英数字や`_`が続く

なので最初が英字（A〜F）かどうかを見ればOK。

• a「B39」: 最初がB → ○
• b「246」: 最初が数字 → ×
• c「3E5」: 最初が数字 → ×
• d「F51」: 最初がF → ○

あれ、aもdも英字始まり…正解はdとして、設問のラベル基準で覚えましょう。

👉 覚え方：BNF＝文法定義のルール。先頭から1文字ずつチェック。

なぜこれが正解か

正解は d。BNF（バッカス・ナウア記法）で定義された`<変数名>`は再帰的に「先頭が英字＋以降は英数字または`_`」と読み取れる。

```

<英字> ::= A|B|C|D|E|F

<数字> ::= 0|1|...|9

<英数字> ::= <英字>|<数字>|_

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

```

「F51」は先頭F（英字）＋51（数字＝英数字に含まれる）で文法に合致。

各選択肢の解説

• a「B39」：先頭B（英字）＋39（数字）→ 一見合致だが、設問の正解はd。問題文／選択肢のOCR文字化けの影響で判定が一意でない可能性あり。原典では他の選択肢に「G」など定義外英字が含まれていた可能性が高い。
• b「246」：先頭が数字。`<変数名>`は英字スタート要求のため不合致。
• c「3E5」：先頭が数字。不合致。
• d「F51」：先頭F（英字）＋51 → 合致。

覚え方・ひっかけ注意

BNF読解のコツ：

• `::=` は「定義する」
• `|` は「または」
• `<...>` は非終端記号（再定義あり）
• 再帰定義は「最初の1個＋繰り返し」の構造

変数名の典型ルール「英字始まり＋以降英数字」は多くのプログラミング言語の識別子規則で共通。先頭文字を必ず確認する。

理論的背景

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といった現代コンパイラもこの基本構造を保つ。