文脈自由文法

文脈自由文法（ぶんみゃくじゆうぶんぽう、Context-free Grammar、CFG）とは、言語学や情報工学において全生成規則が以下の形式である形式文法のひとつである。テンプレート:Indent ここで V は非終端記号であり、w は終端文字と非終端記号から構成される文字列である。「文脈自由」という用語は前後関係に依存せずに非終端記号 V を w に置換できることを意味している。文脈自由文法によって生成される形式言語を文脈自由言語という。

背景

文脈自由文法はノーム・チョムスキーが言語学で今も使われる「句構造文法（Phrase-Structure Grammar）」として最初に記述した^[1]。

文脈自由文法の形式性は、言語学が伝統的に自然言語の文法を厳密な数学として記述してきた既存の方法（例えばパーニニ）に倣っている。自然言語文の「ブロック構造」を自然に捉えている。その単純性から、数学的な研究手法が使えるが、問題もある。自然言語の文法の重要な機能である一致や参照といった属性をそのまま表すことができないのである。

ブロック構造はALGOLプロジェクトによってプログラミング言語に持ち込まれた。すなわち、ALGOL の文法を文脈自由文法として記述することになった。これがその後のコンピュータ言語にも採用され、コンピュータ言語の文法の形式的記述方法がバッカス・ナウア記法として知られるようになった。

文脈自由文法の「ブロック構造」は文法上非常に基本的であり、特に計算機科学では構文や文法は文脈自由文法を利用することが多い。文法によって表せない形式上の制約は、言語の意味論の一部と考えられるようになった。

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

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

形式的定義

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

<math>G = (V\,, \Sigma\,, R\,, S\,)</math> ここで

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

<math>R\,</math> のメンバーを文法の規則と呼ぶ。

追加定義1

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

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

追加定義2

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

追加定義3

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

追加定義4

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

テンプレート:Indent

追加定義5

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

例

例 1

最初の例は非常に単純な以下の規則で表される。テンプレート:Indent ここで | は論理和を意味し、S を置換可能な文字列を併記するのに使われる。ε は空の文字列を意味する。この文法によって生成される言語は以下のようになる。 <math> \{ a^n b^n : n \ge 0 \} </math> これは正規言語ではない。

例 2

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

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

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

例 3

文字セット {a,b} について、異なる個数の a と b から構成される全ての文字列を生成する文脈自由文法は以下のようになる。テンプレート:Indent ここで、T に関する生成規則は a と b が同数の文字列を生成するが、U は a の方が必ず多くなる文字列を生成し、V は b の方が必ず多くなる文字列を生成する。

例 4

次の例は <math> \{ a^n b^m c^{m+n} : n \ge 0, m \ge 0 \} </math> である。これは正規言語ではなく文脈自由言語である。以下の生成規則で生成される（この生成規則は文脈自由文法にしたがっている）。テンプレート:Indent

その他の例

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

導出と構文木

ある文法において、開始記号からある文字列が導出される過程を記述する方法は二種類存在する。単純な方法は導出過程の途中の文字列を全て書き出していく方法である。つまり開始記号から始めて、生成規則を一回適用する度に文字列を書き出して、最後に目的の文字列になるまで列挙するのである。例えば「左端に最も近い非終端記号を最初に書き換える」という規則を適用したとすれば、文脈自由文法では適用する生成規則を列挙するだけで十分である。これを文字列の「左端導出」（Leftmost Derivation）と呼ぶ。例えば、以下の文法があるとする。テンプレート:Indent 文字列「1 + 1 + a」を導出する過程は [ (1), (1), (2), (2), (3) ] というリストになる。同様に「右端導出」も定義できる。この例の場合、右端導出での導出過程は [ (1), (3), (1), (2), (2)] というリストになる。

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

導出過程は導出される文字列上にある種の階層構造を描くことでも表される。例として左端導出による「1 + 1 + 1」に対する階層構造を見てみよう。導出過程は以下のようになる。テンプレート:Indent ここで { ... }_S は S から導出された部分文字列を意味している。これに対応する階層構造は以下のような木構造になる。

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

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

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

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

標準形

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

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

非決定性

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

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

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

拡張

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

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

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

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

言語学的応用

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

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

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

脚注

テンプレート:Reflist

参考文献

テンプレート:Cite book 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.