文脈自由文法のソースを表示

'''文脈自由文法'''（ぶんみゃくじゆうぶんぽう、{{Lang-en-short|Context-free Grammar}}、'''CFG'''）は、[[形式言語]]の理論（特に、[[生成文法]]）において全生成規則が以下のようである[[形式文法]]である。
{{Indent|<math>V \to w</math>}}
ここで <math>V</math> は[[非終端記号]]であり、<math>w</math> は[[終端記号]]と非終端記号の（0個を含む）任意個の並びである。「文脈自由」という用語は前後関係に依存せずに非終端記号 <math>V</math> を <math>w</math> に置換できる、という所から来ている（「文脈無用」という訳の提案もある<ref>『国語学五つの発見再発見』（[[水谷静夫]]）§3.3.5.（p. 83）</ref>）。文脈自由文法によって生成される形式言語を[[文脈自由言語]]という。

== 背景 ==
文脈自由文法は[[ノーム・チョムスキー]]による[[句構造文法]]の研究の中から、[[形式言語]]の類別（[[形式言語の階層]]や[[チョムスキー階層]]の記事を参照）のひとつとして見出されたものである<ref name="chomsky1956">{{cite journal | last = Chomsky | first = Noam | authorlink = | title = Three models for the description of language | journal = Information Theory, IEEE Transactions | volume = 2 | issue = 3 | pages = 113–124 | publisher = | date = 1956年9月 | url = http://ieeexplore.ieee.org/iel5/18/22738/01056813.pdf?isnumber=22738&prod=STD&arnumber=1056813&arnumber=1056813&arSt=+113&ared=+124&arAuthor=+Chomsky%2C+N. | doi = | id = | accessdate =  2007年6月18日}}</ref>。

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

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

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

文脈自由文法は効率的な[[構文解析]][[アルゴリズム]]を適用できる程度に単純である。つまり、ある文字列が特定の文法による言語に属しているかどうかを判断することができる（例えば[[アーリー法]]）。初期の構文解析手法である[[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=\emptyset</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|<math>L(G)=\{w\in\Sigma^{*} : S\stackrel{*}{\Rightarrow} w\} </math>}}

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

== 例 ==
=== 例 1 ===
最初の例を示す。
{{Indent|S &rarr; aSb <nowiki>|</nowiki> &epsilon;}}
ここで、 | は「選択」を意味し、ε は空の文字列を意味する。この文法によって生成される言語は以下のようになる。

<math> \{ a^n b^n : n \ge 0 \} </math>

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

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

=== 例 2 ===
次は三種類の変数 x, y, z を使った文法的に正しい四則演算の数式を生成する文脈自由文法である。ここで演算子は中置としている。
{{Indent|<nowiki>S &rarr; x | y | z | S + S | S - S | S * S | S/S | (S)</nowiki>}}

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

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

=== 例 3 ===
文字セット {a,b} について、異なる個数の a と b から構成される全ての文字列を生成する文脈自由文法は以下のようになる。
{{Indent|
S &rarr; U <nowiki>|</nowiki> V<br />
U &rarr; TaU <nowiki>|</nowiki> TaT<br />
V &rarr; TbV <nowiki>|</nowiki> TbT<br />
T &rarr; aTbT <nowiki>|</nowiki> bTaT <nowiki>|</nowiki> &epsilon;
}}
ここで、T に関する生成規則は a と b が同数の文字列を生成するが、U は a の方が必ず多くなる文字列を生成し、V は b の方が必ず多くなる文字列を生成する。

=== 例 4 ===
次の例は <math> \{ a^n b^m c^{m+n} : n \ge 0, m \ge 0 \} </math> である。これは正規言語ではなく文脈自由言語である。以下の生成規則で生成される（この生成規則は文脈自由文法にしたがっている）。
{{Indent|
S &rarr; aSc <nowiki>|</nowiki> B<br />
B &rarr; bBc <nowiki>|</nowiki> &epsilon;
}}

=== その他の例 ===
文脈自由文法は数学的な「形式的」言語だけで利用されるわけではない。例えば、[[タミル語]]の詩である Venpa は文脈自由文法で定式化できることが指摘されている<ref>{{cite conference | first = BalaSundaraRaman | last = L | authorlink = | first2=Ishwar |last2=S |first3=Sanjeeth Kumar |last3=Ravindranath | date = 2003年8月22日 | title = Context Free Grammar for Natural Language Constructs - An implementation for Venpa Class of Tamil Poetry | book-title = Proceedings of Tamil Internet, Chennai, 2003 | editor = | others = | edition = | publisher = International Forum for Information Technology in Tamil | location = | pages = 128-136 | url = http://citeseer.ist.psu.edu/balasundararaman03context.html | format = | accessdate = 2006年8月24日 | doi = | id = }}</ref>。

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

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

導出過程は導出される文字列上にある種の階層構造を描くことでも表される。例として左端導出による「1 + 1 + 1」に対する階層構造を見てみよう。導出過程は以下のようになる。
{{Indent|
S&rarr;S+S (1)<br />
S&rarr;S+S+S (1)<br />
S&rarr;1+S+S (2)<br />
S&rarr;1+1+S (2)<br />
S&rarr;1+1+1 (2)

{ { { 1 }<sub>S</sub> + { 1 }<sub>S</sub> }<sub>S</sub> + { 1 }<sub>S</sub> }<sub>S</sub>
}}
ここで { ... }<sub>S</sub> は S から導出された部分文字列を意味している。これに対応する階層構造は以下のような[[木構造 (データ構造)|木構造]]になる。

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

この木構造をその文字列の「具象構文木」と呼ぶ（[[抽象構文木]]も参照されたい）。この場合、上述の左端導出も右端導出も同じ構文木になるが、左端導出には以下のような別の導出過程が存在する。
{{Indent|
S&rarr; S + S (1)<br />
S&rarr; 1 + S (2)<br />
S&rarr; 1 + S + S (1)<br />
S&rarr; 1 + 1 + S (2)<br />
S&rarr; 1 + 1 + 1 (2)
}}
これによって定義される構文木は以下のようになる。

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

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

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

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

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

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

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

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

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

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

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

== 言語学的応用 ==
[[ノーム・チョムスキー]]自身は、[[生成文法]]を追加することで文脈自由文法の制限を克服したいと考えていた<ref name="chomsky1956"/>。

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

彼は自然言語が文脈自由でないと考えていたが<ref name="shieber1985">{{cite journal | title=Evidence against the context-freeness of natural language | date=1985年 | last=Shieber | first=Stuart | journal=Linguistics and Philosophy | volume=8 | pages=333–343 | url=http://www.eecs.harvard.edu/~shieber/Biblio/Papers/shieber85.pdf}}</ref>、彼がCFGでは不十分であることを示す証拠として挙げた事例は、後に間違いであることが証明された<ref name="pullum-gazdar1982">{{cite journal | title=Natural languages and context-free languages | date=1982年 | last=Pullum | first=Geoffrey K. | coauthors=Gerald Gazdar | journal=Linguistics and Philosophy | volume=4 | pages=471–504}}</ref>。Gerald Gazdar と Geoffrey Pullum は、一部に文脈自由的でない構造があるものの、自然言語の大部分は文脈自由であると指摘している<ref name="pullum-gazdar1982"/>。文脈自由でない部分とは、例えば、[[スイスドイツ語]]の cross-serial dependencies <ref name="shieber1985"/> や、[[バンバラ語]]の[[畳語]]である<ref name="culy1985">{{cite journal | title=The Complexity of the Vocabulary of Bambara | date=1985 | last=Culy | first=Christopher | journal=Linguistics and Philosophy | volume=8 | pages=345–351}}</ref>。

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
{{Reflist}}

== 参考文献 ==
* {{cite book|author = Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | id = 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]]
* [[確率文脈自由文法]]
* [[構文解析]]
* [[形式言語の階層]] - [[チョムスキー階層]]
* [[生成文法]]
* [[句構造規則]]
* [[構成素]]

{{DEFAULTSORT:ふんみやくしゆうふんほう}}
[[Category:形式言語]]
[[Category:数学に関する記事]]
[[Category:プログラミング言語のトピック]]