文脈ぶんみゃく自由じゆう文法ぶんぽう

文脈ぶんみゃく自由じゆう文法ぶんぽう（ぶんみゃくじゆうぶんぽう、英えい: Context-free Grammar、CFG）は、形式けいしき言語げんごの理論りろん（特とくに、生なま成文法せいぶんほう）において全ぜん生成せいせい規則きそくが以下いかのようである形式けいしき文法ぶんぽうである。

$V\to 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=\emptyset$
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
• 確かく率りつ文脈ぶんみゃく自由じゆう文法ぶんぽう
• 構文こうぶん解析かいせき
• 形式けいしき言語げんごの階層かいそう - チョムスキー階層かいそう
• 生なま成文法せいぶんほう
• 句く構造こうぞう規則きそく
• 構成こうせい素もと