文脈自由文法

文脈自由文法（ぶんみゃくじゆうぶんぽう、Context-free Grammar、CFG）は、形式言語の理論（特に、生成文法）において全生成規則が以下のようである形式文法である。

V → w

ここで V は非終端記号であり、w は終端記号と非終端記号の（0個を含む）任意個の並びである。「文脈自由」という用語は前後関係に依存せずに非終端記号 V を w に置換できる、という所から来ている（「文脈無用」という訳の提案もある）。文脈自由文法によって生成される形式言語を文脈自由言語という。

背景

文脈自由文法はノーム・チョムスキーによる句構造文法の研究の中から、形式言語の類別（形式言語の階層やチョムスキー階層の記事を参照）のひとつとして見出されたものである。

文脈自由文法の形式性は、言語学が伝統的に自然言語の文法を形式的に記述してきた既存の方法（例えばパーニニ）に倣っている。たとえば、入れ子（nesting）を自然に捉えていることや、形式的であることから形式的な手法が使えるという利点がある。一方で問題もあり、たとえば自然言語の文法の重要な機能である一致や参照といった属性は綺麗に表すことができない（自然言語に限らず、プログラミング言語でもしばしば文脈自由文法から「はみ出している」仕様がある）。

文脈自由文法は、（チョムスキーらによって言語学で）提唱されてすぐに、（形式言語と密接な関係にあるオートマトン理論のような理論計算機科学の分野にとどまらず）プログラミング言語 ALGOLの仕様策定において、構文の仕様を示すバッカス・ナウア記法という形でとり入れられ、その後コンピュータ科学一般に、あるいはもっと広く実務にも応用されている。

「文脈自由文法はほとんどのプログラミング言語の文法を記述できるほど強力であり、実際、多くのプログラミング言語は文脈自由文法で構文仕様を定義している。」といった言説がしばしば見られるが（たとえば日本語版ウィキペディアのこの部分にはずっとそう書かれていた）誤りである。本当に実際の所は、yaccで定義されていても、純粋に構文では定義しきれない部分をあれこれと意味規則で補っているのが普通である。

文脈自由文法は効率的な構文解析アルゴリズムを適用できる程度に単純である。つまり、ある文字列が特定の文法による言語に属しているかどうかを判断することができる（例えばアーリー法）。初期の構文解析手法であるLR法やLL法は文脈自由文法のサブセットを扱うものであった。

全ての形式言語が文脈自由であるわけではない。文脈自由でない例として $\{a^{n}b^{n}c^{n}:n\geq 0\}$ がある。この言語は Parsing Expression Grammar (PEG) では生成できる。PEG は文脈自由文法と扱える範囲の文法が異なり文脈自由文法を全て扱えるわけではないがプログラミング言語に適した新たな定式化のひとつである。

形式的定義

文脈自由文法 G は次の 4-タプル で表される。

$G=(V\,,\Sigma \,,R\,,S\,)$ ここで

1. $V\,$ は変数（非終端記号）の有限集合
2. $\Sigma \,$ は終端記号の有限集合で、$\Sigma \cap V=\Phi$
3. $S\,$ は開始記号（変数）
4. $R\,$ は $V$ から $(V\cup \Sigma )^{*}$ への関係であり、$\exists \,w\in (V\cup \Sigma )^{*}:(S,w)\in R$ が成り立つ

$R\,$ のメンバーを文法の規則と呼ぶ。

追加定義1

任意の $(\alpha ,\beta )\in R$ について $P_{\alpha \beta }(u,\,v)=(u\alpha v,\,u\beta v)$ となるような生成写像 $P_{\alpha \beta }:(V\cup \Sigma )^{*}\times (V\cup \Sigma )^{*}\longrightarrow (V\cup \Sigma )^{*}\times (V\cup \Sigma )^{*}$ が存在する。

順序対 $(u\alpha v,\,u\beta v)$ を $G\,$ のプロダクション（生成規則）と呼び、一般に $u\alpha v\rightarrow u\beta v$ のように表記する。

追加定義2

任意の $u,v\in (V\cup \Sigma )^{*}$ について、$u\,$ が $v\,$ を生成することを $u\Rightarrow v$ で表す。ただし、$u\,=u_{1}\alpha u_{2}$ かつ $v\,=u_{1}\beta u_{2}$ で $\exists (\alpha ,\beta )\in R,u_{1},u_{2}\in (V\cup \Sigma )^{*}$ が成り立たねばならない。

追加定義3

任意の $u,v\in (V\cup \Sigma )^{*}$ について、$u{\stackrel {*}{\Rightarrow }}v$（あるいは $u\Rightarrow \Rightarrow v$）であるとは、$u\Rightarrow u_{1}\Rightarrow u_{2}\cdots \Rightarrow u_{k}\Rightarrow v$ となるような $\exists u_{1},u_{2},\cdots u_{k}\in (V\cup \Sigma )^{*},k\geq 0$ が成り立つ場合である。

追加定義4

文法 $G=(V\,,\Sigma \,,R\,,S\,)$ の言語は次の集合で表される。

$L(G)=\{w\in \Sigma ^{*}:S{\stackrel {*}{\Rightarrow }}w\}$

追加定義5

言語 $L\,$ は、$L\,=\,L(G)$ となるような文脈自由文法 $G\,$ が存在するとき、文脈自由言語(CFL)であるという。

例

例 1

最初の例を示す。

S → aSb | ε

ここで、 | は「選択」を意味し、ε は空の文字列を意味する。この文法によって生成される言語は以下のようになる。

$\{a^{n}b^{n}:n\geq 0\}$

これは正規言語ではない例でもある。

また、「選択」は文脈自由文法の表現に必ずしも必須ではない。次の2つの規則でも、上の例と同様の言語を定義している。

S → aSb

S → ε

例 2

次は三種類の変数 x, y, z を使った文法的に正しい四則演算の数式を生成する文脈自由文法である。ここで演算子は中置としている。

S → x | y | z | S + S | S - S | S * S | S/S | (S)

この文法に従うと、例えば "( x + y ) * x - z * y / ( x + x )" といった式が生成可能である。

この文法は、構造が異なる構文木から同じ文字列が生成されうるという意味で曖昧である。

例 3

文字セット {a,b} について、異なる個数の a と b から構成される全ての文字列を生成する文脈自由文法は以下のようになる。

S → U | V
U → TaU | TaT
V → TbV | TbT
T → aTbT | bTaT | ε

ここで、T に関する生成規則は a と b が同数の文字列を生成するが、U は a の方が必ず多くなる文字列を生成し、V は b の方が必ず多くなる文字列を生成する。

例 4

次の例は $\{a^{n}b^{m}c^{m+n}:n\geq 0,m\geq 0\}$ である。これは正規言語ではなく文脈自由言語である。以下の生成規則で生成される（この生成規則は文脈自由文法にしたがっている）。

S → aSc | B
B → bBc | ε

その他の例

文脈自由文法は数学的な「形式的」言語だけで利用されるわけではない。例えば、タミル語の詩である Venpa は文脈自由文法で定式化できることが指摘されている。

導出と構文木

ある文法において、開始記号からある文字列が導出される過程を記述する方法は二種類存在する。単純な方法は導出過程の途中の文字列を全て書き出していく方法である。つまり開始記号から始めて、生成規則を一回適用する度に文字列を書き出して、最後に目的の文字列になるまで列挙するのである。例えば「左端に最も近い非終端記号を最初に書き換える」という規則を適用したとすれば、文脈自由文法では適用する生成規則を列挙するだけで十分である。これを文字列の「左端導出」（Leftmost Derivation）と呼ぶ。例えば、以下の文法があるとする。

(1) S → S + S
(2) S → 1
(3) S → a

文字列「1 + 1 + a」を導出する過程は [ (1), (1), (2), (2), (3) ] というリストになる。同様に「右端導出」も定義できる。この例の場合、右端導出での導出過程は [ (1), (3), (1), (2), (2)] というリストになる。

左端導出と右端導出のリストが異なるのは重要なポイントである。構文解析では、文法規則毎にそれを入力文字列に適用する小さなプログラムが存在する。したがって、構文解析が左端導出を行うのか右端導出を行うのかによってそれらのプログラムを適用する順番が変わってくるのである。

導出過程は導出される文字列上にある種の階層構造を描くことでも表される。例として左端導出による「1 + 1 + 1」に対する階層構造を見てみよう。導出過程は以下のようになる。

S→S+S (1)
S→S+S+S (1)
S→1+S+S (2)
S→1+1+S (2)
S→1+1+1 (2)

{ { { 1 }_S + { 1 }_S }_S + { 1 }_S }_S

ここで { ... }_S は S から導出された部分文字列を意味している。これに対応する階層構造は以下のような木構造になる。

     　　　  Ｓ
 　　 　    ／|＼
 　　 　  ／  |　＼
 　　   ／  　|　　＼
   　  Ｓ　　'+'　　Ｓ
  　 ／|＼   　　　 |
  ／　 |　＼ 　　　 |
 Ｓ　 '+'　Ｓ　　　'1'
 |    　 　 |
'1' 　 　  '1'

この木構造をその文字列の「具象構文木」と呼ぶ（抽象構文木も参照されたい）。この場合、上述の左端導出も右端導出も同じ構文木になるが、左端導出には以下のような別の導出過程が存在する。

S→ S + S (1)
S→ 1 + S (2)
S→ 1 + S + S (1)
S→ 1 + 1 + S (2)
S→ 1 + 1 + 1 (2)

これによって定義される構文木は以下のようになる。

    　　Ｓ 
  　  ／|＼
  　／  |　 ＼
  ／  　| 　  ＼
 Ｓ　　'+'  　 Ｓ
 |   　 　　 ／ |＼
 |   　　  ／　 |  ＼
'1' 　　  Ｓ　 '+'  Ｓ
    　　  |   　　 　|
    　　 '1'  　　　'1'

この文法のように、ある文字列を導出する構文木が複数考えられる文法を「曖昧な文法」（Ambiguous Grammar）と呼ぶ。このような文法の構文解析は、生成規則の適用順序を毎回決定しなければならないため難しい。

標準形

空の文字列を生成しない文脈自由文法は等価なチョムスキー標準形かグライバッハ標準形に変換できる。ここでいう「等価」とは同じ言語を生成するという意味である。

チョムスキー標準形文法は生成規則が単純なので、この標準形は理論的にも実用上も密接な関係がある。例えば、ある文脈自由文法についてチョムスキー標準形を使うことで多項式時間のアルゴリズムで入力された文字列がその文法で生成されるものか否かを判定できる（CYKアルゴリズム）。

非決定性

文脈自由文法は能力が制限されているため、その操作の一部は決定可能であるが、同時に決定不能な問題もある。最も単純で分かり易い決定不能問題の1つとして、CFG が言語の全文字列を受容するかどうかという問題がある。還元によって、この問題がチューリングマシンの停止問題と同じであることが示される。その還元には、チューリングマシンのあらゆる計算過程を示す「計算履歴」と呼ばれる概念を用いる。あるチューリングマシンがある入力を与えられたとき、それを受容しない計算履歴の文字列を生成するCFGを構築でき、そうすると、そのCFGはマシンが入力を受容しないときだけ文字列を受容（認識）する。

これを応用すると、2つのCFGが同じ言語を記述しているかどうかも判定不能である。なぜなら、言語の全文字列を受理する自明なCFGとの等価性を判定できないためである。

また、文脈依存文法が文脈自由言語を表しているかどうかも決定不能な問題である。

拡張

文脈自由文法の形式性の拡張として、非終端記号に引数を持たせ、規則内で値を渡すということが考えられる。これにより、自然言語の一致や参照といった機能を表現可能となり、プログラミング言語での識別子の定義や正しい用法を自然な形で表現可能となる。例えば、英語の文で、主語と動詞が数において合致しなければならないということを容易に表現できる。

計算機科学では、このようなアプローチの例として接辞文法、属性文法、Van Wijngaarden の two-level grammar などがある。

同様の拡張は言語学にもある。

別の拡張として、規則の左辺に追加の記号を書けるようにする手法がある。これは文脈依存文法に他ならない。

言語学的応用

ノーム・チョムスキー自身は、生成文法を追加することで文脈自由文法の制限を克服したいと考えていた。

そのような規則も言語学によく見られる。例えば、英語における受動態化である。しかし、それらは強力すぎるため（チューリング完全）、変換の適用は制限される必要がある。生成文法の大部分は、句構造文法と変換規則の記述機構を改善し、自然言語が表現できることを正確に表せるようにすることを目的としている。

彼は自然言語が文脈自由でないと考えていたが、彼がCFGでは不十分であることを示す証拠として挙げた事例は、後に間違いであることが証明された。Gerald Gazdar と Geoffrey Pullum は、一部に文脈自由的でない構造があるものの、自然言語の大部分は文脈自由であると指摘している。文脈自由でない部分とは、例えば、スイスドイツ語の cross-serial dependencies や、バンバラ語の畳語である。

参考文献

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X  Section 2.1: Context-Free Grammars, pp.91–101. Section 4.1.2: Decidable problems concerning context-free languages, pp.156–159. Section 5.1.1: Reductions via computation histories: pp.176–183.

関連項目

• 文脈依存文法
• 形式文法
• Parsing Expression Grammar
• 確率文脈自由文法
• 構文解析
• 形式言語の階層 - チョムスキー階層
• 生成文法
• 句構造規則
• 構成素