読み方：ぶんみゃくじゆうぶんぽう

文脈自由文法

概要

文脈自由文法とは、文字列の構造を規則によって定義する形式文法の一つ。記号の書き換え規則を用いて文字列の構造を定義するもので、プログラミング言語の構文定義やコンパイラの構文解析において広く使われている。

この文法では、記号の集合と生成規則の集合によって言語が定義される。記号は開始記号、非終端記号、終端記号の3つに分かれる。終端記号は実際の文字列に現れる具体的な記号（キーワード、数値、演算子など）で、非終端記号は生成規則によってさらに展開される抽象的な構造を表す記号である。

生成規則は「非終端記号 → 記号列」の形式で書かれ、左辺の非終端記号を右辺の記号列に置き換えることができる。「文脈自由」という名称は、左辺に非終端記号が単独で現れる（周囲の文脈に関係なく置き換えられる）という性質に由来する。極単純な例として、加算（+）と乗算（*）から成る数式の文法を示すと、「E → E + E | E * E | （ E ） | 数値」のような規則で表現できる。この規則を繰り返し適用することで「（ 3 + 4 ） * 2」のような式が生成できる。

応用

文脈自由文法に基づく言語は「プッシュダウンオートマトン」（push-down automaton）と呼ばれる計算モデルで認識される。プログラミング言語のソースコードを機械語のコードに変換するコンパイラでは、ソースコードの構文解析に文脈自由文法を応用している。与えられた文字列が言語の文法に従って生成可能かどうかを判定し、構文木として表現する処理が行われる。

自然言語処理の分野でも文の構造を解析するために文脈自由文法が利用されることがあるが、自然言語の文章を構成する単語は文脈に依存して意味が確定するものが多く、文脈自由文法で表現できない構造も存在するため、確率的文脈自由文法など拡張された手法が研究・使用されている。