文脈自由文法
文脈自由文法(ぶんみゃくじゆうぶんぽう、Context-free Grammar、CFG)は、形式言語の理論(特に、生成文法)において全生成規則が以下のようである形式文法である。
V → w
ここで V は非終端記号であり、w は終端記号と非終端記号の(0個を含む)任意個の並びである。「文脈自由」という用語は前後関係に依存せずに非終端記号 V を w に置換できる、という所から来ている(「文脈無用」という訳の提案もある)。文脈自由文法によって生成される形式言語を文脈自由言語という。
文脈自由文法は能力が制限されているため、その操作の一部は決定可能であるが、同時に決定不能な問題もある。最も単純で分かり易い決定不能問題の1つとして、CFG が言語の全文字列を受容するかどうかという問題がある。還元によって、この問題がチューリングマシンの停止問題と同じであることが示される。その還元には、チューリングマシンのあらゆる計算過程を示す「計算履歴」と呼ばれる概念を用いる。あるチューリングマシンがある入力を与えられたとき、それを受容しない計算履歴の文字列を生成するCFGを構築でき、そうすると、そのCFGはマシンが入力を受容しないときだけ文字列を受容(認識)する。
これを応用すると、2つのCFGが同じ言語を記述しているかどうかも判定不能である。なぜなら、言語の全文字列を受理する自明なCFGとの等価性を判定できないためである。
また、文脈依存文法が文脈自由言語を表しているかどうかも決定不能な問題である。
「文脈自由文法はほとんどのプログラミング言語の文法を記述できるほど強力であり、実際、多くのプログラミング言語は文脈自由文法で構文仕様を定義している。」といった言説がしばしば見られるが誤りである。本当に実際の所は、yaccで定義されていても、純粋に構文では定義しきれない部分をあれこれと意味規則で補っているのが普通である。
文脈自由文法は効率的な構文解析アルゴリズムを適用できる程度に単純である。つまり、ある文字列が特定の文法による言語に属しているかどうかを判断することができる(例えばアーリー法)。初期の構文解析手法であるLR法やLL法は文脈自由文法のサブセットを扱うものであった。
全ての形式言語が文脈自由であるわけではない。文脈自由でない例として { a n b n c n : n ≥ 0 } {\displaystyle \{a^{n}b^{n}c^{n}:n\geq 0\}} がある。この言語は Parsing Expression Grammar (PEG) では生成できる。PEG は文脈自由文法と扱える範囲の文法が異なり文脈自由文法を全て扱えるわけではないがプログラミング言語に適した新たな定式化のひとつである。
文脈自由文法の形式性の拡張として、非終端記号に引数を持たせ、規則内で値を渡すということが考えられる。これにより、自然言語の一致や参照といった機能を表現可能となり、プログラミング言語での識別子の定義や正しい用法を自然な形で表現可能となる。例えば、英語の文で、主語と動詞が数において合致しなければならないということを容易に表現できる。
計算機科学では、このようなアプローチの例として接辞文法、属性文法、Van Wijngaarden の two-level grammar などがある。
同様の拡張は言語学にもある。
別の拡張として、規則の左辺に追加の記号を書けるようにする手法がある。これは文脈依存文法に他ならない。