第2章: 文法を記述する — BNF・EBNF・PEGと曖昧性

第1章で、パーサは「文法（grammar）という規則に照らしてトークンを木に組み立てる」と述べました。 では、その文法そのものは、どうやって正確に書き下すのでしょうか。「日本語で説明する」のでは曖昧すぎます。 必要なのは、言語を記述するための言語——メタ言語です。本章では、そのメタ言語の代表である BNF・EBNF・PEGを辿り、最後に文法の「曖昧さ」がいかに厄介で、どう手なずけられてきたかを見ます。

BNFの誕生 — バッカスとナウア

物語は1950年代末に始まります。IBMでFORTRANを設計したジョン・バッカス（John Backus）は、 新しい国際言語ALGOLの設計委員会で、ある課題に直面しました。「言語の構文を、誰が読んでも 一意に解釈できるように、厳密に書き下したい」。そこで彼が1959年に提案したのが、論理学者E.L.ポストの 書き換え規則に着想を得たメタ言語公式でした。

これをデンマークのピーター・ナウア（Peter Naur）が改良し、1960年のALGOL 60報告書で正式に採用します。 ナウアは記号を当時の印刷機で出せる文字に整え、現在おなじみの形——::= と |——を確立しました。

BNFの読み方 — 再帰で世界を記述する

BNFの構成要素はごくシンプルです。<...> で囲まれた非終端記号（さらに展開できる変数）、 クォートされた終端記号（それ以上分解できない実際のトークン）、「〜と定義される」を表す ::=、 そして「または」を表す |。これだけで、算術式のような構造を再帰的に定義できます。

<expr>   ::= <term> "+" <expr> | <term>
<term>   ::= <factor> "*" <term> | <factor>
<factor> ::= "(" <expr> ")" | <number>
<number> ::= <digit> | <digit> <number>
<digit>  ::= "0" | "1" | "2" | "3" | "4"
           | "5" | "6" | "7" | "8" | "9"

注目すべきは再帰です。「数字（number）とは、数字（digit）一つか、あるいは数字（digit）の後ろに 数字（number）が続いたもの」——自分自身を使って自分を定義しています。この再帰の構造が、有限の規則で 無限の表現（任意の長さの数や式）を生み出します。さらに、expr が term を、 term が factor を含むという階層が、そのまま「* は + より優先」という 演算子の優先順位を表現していることにも注目してください。文法の形が、計算の意味を決めているのです。

EBNF — 繰り返しとオプションを直接書く

BNFは美しいですが、「繰り返し」を再帰で書くのは少し冗長です。たとえば「文をセミコロンで区切って並べる」を BNFで書くと再帰定義が要ります。これを解消したのが、Pascalの設計者ニクラウス・ヴィルトが 1977年に作ったEBNF（Extended BNF）です。記号を追加して、繰り返しやオプションを直接表現できます。

先ほどの算術式をEBNFで書き直すと、 のおかげで再帰が消え、ぐっと読みやすくなります。 これはISO/IEC 14977として国際標準化もされています。

expr   = term { ("+" | "-") term } ;
term   = factor { ("*" | "/") factor } ;
factor = "(" expr ")" | number ;
number = digit { digit } ;
digit  = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

Chomsky階層 — 文法にも「強さ」がある

そもそも文法には種類があり、表現できる言語の複雑さに序列があります。言語学者ノーム・チョムスキーが 1950年代に提唱したChomsky階層は、文法を4つのタイプに分類します。そして興味深いことに、 この階層は第1章の「三層」ときれいに対応します。

ポイントは、字句解析は正規文法（Type 3）で十分だが、構文解析には文脈自由文法（Type 2）が要る ということです。括弧の入れ子のような「対応関係」は正規表現では表現できず、スタックを持つプッシュダウンオートマトン＝CFGが必要になります。 そして「変数を使う前に宣言せよ」のような文脈依存のルールはCFGでも書けず、第1章で見た意味解析の領域（Type 1以上）に入る—— これが構文解析と意味解析を分ける理論的な理由です。

曖昧性という落とし穴 — dangling else問題

CFGには弱点があります。| を「どちらに展開してもよい（非決定的）」と解釈するため、 同じ入力から複数の解析木が生まれてしまうことがあるのです。これを曖昧（ambiguous）な文法と呼びます。 もっとも有名な例が、半世紀にわたって言語設計者を悩ませてきたdangling else（ぶら下がりelse）問題です。

if (a)
    if (b)
        s1;
else
    s2;        // この else は、どちらの if に属するのか?

次のような素朴な文法を考えると、上のコードは2通りに解釈できてしまいます。

<stmt> ::= "if" <expr> "then" <stmt>
         | "if" <expr> "then" <stmt> "else" <stmt>
         | <other>

graph TD
  subgraph 解釈A["解釈A: else は内側の if に付く（多数派）"]
    A1["if a"] --> A2["if b"]
    A2 --> A3["s1"]
    A2 --> A4["else s2"]
  end
  subgraph 解釈B["解釈B: else は外側の if に付く"]
    B1["if a"] --> B2["if b"]
    B2 --> B3["s1"]
    B1 --> B4["else s2"]
  end
  style A4 fill:#14b8a6,stroke:#0d9488,color:#fff
  style B4 fill:#f97316,stroke:#ea580c,color:#fff

これは深刻です。s2 が「a が真かつ b が偽のとき」に実行されるのか、 「a が偽のとき」に実行されるのか——プログラムの動作そのものが変わってしまいます。 この曖昧さに対し、言語設計者は主に3つの対処法をとってきました。

PEG — 「順序付き選択」で曖昧性を根絶する

曖昧性は、CFGが | を「非決定的な選択」と捉えることに根があります。ならば、 選択に順序を持たせればよい——この発想の転換を持ち込んだのが、当時MITの大学院生だった ブライアン・フォード（Bryan Ford）が2004年に提案したPEG（Parsing Expression Grammar）です。

PEGの選択演算子は /（順序付き選択）です。e1 / e2 は「まず e1 を試し、 成功したら e2 はもう試さない」という決定的な動作をします。これにより、解析結果は常に一意に定まり、 曖昧性が原理的に生じません。CFGとの思想の違いを並べてみましょう。

PEGには *（0回以上）、+（1回以上）、?（省略可）に加え、 入力を消費せずに先読みする &e（肯定）と !e（否定）という強力な演算子もあります。 先ほどの算術式をPEGで書くと、選択の順序が明示的になります。

Expr   <- Term (('+' / '-') Term)*
Term   <- Factor (('*' / '/') Factor)*
Factor <- '(' Expr ')' / Number
Number <- [0-9]+

まとめ — 言語を記述する言語

本章では、構文を厳密に書き下すメタ言語を辿りました。バッカスとナウアのBNF（ALGOL 60）、 繰り返しを直接書けるEBNF（ヴィルト）、そして順序付き選択で曖昧性を根絶したPEG（フォード）。 Chomsky階層は字句解析（正規文法）と構文解析（文脈自由文法）の役割分担を理論的に裏づけ、 dangling else問題は曖昧性がいかに実害をもたらすか、そしてそれが規則・文法書き換え・構文選択で どう手なずけられるかを教えてくれました。

文法という「設計図」を手にした今、次章ではいよいよ、その設計図から生まれる多種多様な構文の見た目—— 中括弧族、インデント族、S式族、そして「式と文」という根本的な分かれ道——を、同じプログラムの多言語対比で旅します。