BNF / Backus-Naur Form / バッカス・ナウア記法

BNF（バックウス・ナウア記法、Backus–Naur Form）は、形式言語―特にプログラミング言語やデータ形式―の「構文（文法）」を記述するための記法です。1960年代にジョン・バックウス（John Backus）とピーター・ナウア（Peter Naur）によって考案され、言語の設計やコンパイラの実装において、文法の仕様を明確にし、その正しさを保証するための強力な手法となっています。以下、その詳細を分解して解説します。

1. 基本概念
2. BNFの記法の要素
1. 2.1 生成規則の例：四則演算
2. 2.2 再帰性と入れ子構造
3. 拡張BNF（EBNF）とその派生
4. BNFの応用と意義
5. ASCIIによる視覚的な文法の例
6. まとめ

1. 基本概念

1.1 形式文法とBNFの位置付け

形式文法 言語のすべての文（文字列）がどのような規則で生成されるかを定義するシステムです。特に文脈自由文法（CFG）は、BNFで典型的に記述される文法の一種です。
BNFの役割 BNFは、その文法規則を抽象的な記号（非終端記号と終端記号）と、生成規則（プロダクションルール）を使って明文化します。これにより、仕様を曖昧さなく伝達でき、機械が解析可能な形にできます。

1.2 非終端記号と終端記号

非終端記号 まだ展開可能な構造を持つ記号で、通常 <式> や <文>、<項> などの角括弧（< >）で囲まれる。プログラミング言語でいうところの「文法の構造部分」や「構文要素」に該当します。
終端記号 これ以上分解できない基本要素。識別子（identifier）、キーワード、記号（+、-、*、/ など）、数字など、最終的にソースコードに現れる具体的な文字列。

1.3 プロダクションルール

各ルールは以下のような形式で表現されます：

<非終端記号> ::= 生成される要素のパターン

右辺には、他の非終端記号や終端記号が現れ、代替が存在する場合は縦棒（|）で区切られます。たとえば、

<式> ::= <項> | <式> "+" <項>

は、<式> が単一の <項> であるか、または <式> に "+" と <項> が続く形で表されることを示しています。

2. BNFの記法の要素

記号	意味
`<...>`	非終端記号を囲む。
`"..."` or `'...'`	終端記号（リテラル文字列）を表す。例："if", "+" など。
`::=`	定義記号。左辺の非終端記号が右辺の形に展開される。
`	`	オルタネーション（選択肢）を示す。右辺に複数の生成候補がある場合に使用する。

2.1 生成規則の例：四則演算

以下は、簡単な算術表現の文法をBNFで記述した一例です：

<式>    ::= <項> | <式> "+" <項> | <式> "-" <項>
<項>    ::= <因子> | <項> "*" <因子> | <項> "/" <因子>
<因子>  ::= 数字 | "(" <式> ")"

この文法は、演算の優先順位（掛け算・割り算が加減算より先に評価される）を自然に表現しており、括弧を用いたグルーピングもサポートしています。

2.2 再帰性と入れ子構造

BNFの大きな特徴は再帰性です。例えば、<式> の定義の中で <式> 自身が現れることで、任意に長い（もしくはネストした）表現を生成できるようになります。これは、言語の中で繰り返しの構文を表すのに非常に役立ちます。

3. 拡張BNF（EBNF）とその派生

BNF自体はシンプルで強力ですが、更なる表現力や簡潔さを求めるために、拡張BNF（Extended Backus–Naur Form; EBNF）という改良版も考案されました。EBNFでは以下のような追加の記述子が導入されています：

角括弧 [ ... ] → オプション（存在してもよいが、省略可能）例: [ "+" <項> ] は、"+" と <項> があってもなくてもよい。
中括弧 { ... } → 繰り返し（0回以上の繰り返し）例: { <桁> } は、連続する桁の列として数字を表現する。
括弧 ( ... ) → 明示的なグループ化のため

EBNFは、より読みやすく、コンパクトな文法を記述できるため、現代の言語仕様書やツールではこちらが採用されることが多いです。

4. BNFの応用と意義

4.1 プログラミング言語の設計

BNFは、プログラミング言語の文法仕様を明確にするために使われます。例えば、アルゴリズム言語 Algol 60 や Pascal、さらには C や Java のような現代の言語の大部分は、BNFまたはその変種を使って構文が定義されています。これにより、コンパイラやインタプリタが正確にコードを解析・翻訳できるようになります。

4.2 自動生成ツールとの連携

BNFで定義された文法は、パーサージェネレータ（例: YACC、ANTLR、Bison など）の入力として利用され、これらのツールによって自動的にパーサー（構文解析器）が生成されます。これにより、人手で複雑な解析ルーチンを書く労力が大幅に削減され、言語設計の変更も容易になります。

4.3 教育と理解のためのツール

また、BNFは形式言語理論やコンパイラ設計の教育においても重要な役割を果たします。文法の規則や構造を明文化することで、プログラミング言語の概念や抽象構文木（AST）の理解が深まります。

5. ASCIIによる視覚的な文法の例

以下は、シンプルな算術表現の文法を視覚的に示すフローチャート風のASCII図です：

          +----------------------------+
          |           <式>           |
          +----------------------------+
                    /    \
                   /      \
         [単項]  <項>        "+"  <項>
                   \      /
                    \    /
          +----------------------------+
          |         <項>            |
          +----------------------------+
                    /    \
                   /      \
          [単項] <因子>       "*"  <因子>
                   \      /
                    \    /
          +----------------------------+
          |        <因子>            |
          +----------------------------+
                    |
        -------------------------
        |         |           |
       数字      "(" <式> ")"   ...

この図は、文法の再帰性や選択肢をシンプルに表現したもので、各ノードが「式」や「項」、「因子」といった構文要素に対応します。