文脈自由文法 - 暇つぶしWikipedia

文脈自由文法

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

V → w {\displaystyle V\to w}

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

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

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

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

「文脈自由文法はほとんどのプログラミング言語の文法を記述できるほど強力であり、実際、多くのプログラミング言語は文脈自由文法で構文仕様を定義している。」といった言説がしばしば見られるが [注釈 1]誤りである。本当に実際の所は、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 は文脈自由文法と扱える範囲の文法が異なり文脈自由文法を全て扱えるわけではないがプログラミング言語に適した新たな定式化のひとつである。
形式的定義

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

G = ( V , Σ , R , S ) {\displaystyle G=(V\,,\Sigma \,,R\,,S\,)} ここで
V {\displaystyle V\,} は変数（非終端記号）の有限集合

Σ {\displaystyle \Sigma \,} は終端記号の有限集合で、 Σ ∩ V = ∅ {\displaystyle \Sigma \cap V=\emptyset }

S {\displaystyle S\,} は開始記号（変数）

R {\displaystyle R\,} は V {\displaystyle V} から ( V ∪ Σ ) ∗ {\displaystyle (V\cup \Sigma )^{*}} への関係であり、 ∃ w ∈ ( V ∪ Σ ) ∗ : ( S , w ) ∈ R {\displaystyle \exists \,w\in (V\cup \Sigma )^{*}:(S,w)\in R} が成り立つ

R {\displaystyle R\,} のメンバーを文法の規則と呼ぶ。
追加定義1

任意の ( α , β ) ∈ R {\displaystyle (\alpha ,\beta )\in R} について P α β ( u , v ) = ( u α v , u β v ) {\displaystyle P_{\alpha \beta }(u,\,v)=(u\alpha v,\,u\beta v)} となるような生成写像 P α β : ( V ∪ Σ ) ∗ × ( V ∪ Σ ) ∗ ⟶ ( V ∪ Σ ) ∗ × ( V ∪ Σ ) ∗ {\displaystyle P_{\alpha \beta }:(V\cup \Sigma )^{*}\times (V\cup \Sigma )^{*}\longrightarrow (V\cup \Sigma )^{*}\times (V\cup \Sigma )^{*}} が存在する。

順序対 ( u α v , u β v ) {\displaystyle (u\alpha v,\,u\beta v)} を G {\displaystyle G\,} のプロダクション（生成規則）と呼び、一般に u α v → u β v {\displaystyle u\alpha v\rightarrow u\beta v} のように表記する。
追加定義2

任意の u , v ∈ ( V ∪ Σ ) ∗ {\displaystyle u,v\in (V\cup \Sigma )^{*}} について、 u {\displaystyle u\,} が v {\displaystyle v\,} を生成することを u ⇒ v {\displaystyle u\Rightarrow v} で表す。ただし、 u = u 1 α u 2 {\displaystyle u\,=u_{1}\alpha u_{2}} かつ v = u 1 β u 2 {\displaystyle v\,=u_{1}\beta u_{2}} で ∃ ( α , β ) ∈ R , u 1 , u 2 ∈ ( V ∪ Σ ) ∗ {\displaystyle \exists (\alpha ,\beta )\in R,u_{1},u_{2}\in (V\cup \Sigma )^{*}} が成り立たねばならない。
追加定義3

任意の u , v ∈ ( V ∪ Σ ) ∗ {\displaystyle u,v\in (V\cup \Sigma )^{*}} について、 u ⇒ ∗ v {\displaystyle u{\stackrel {*}{\Rightarrow }}v} （あるいは u ⇒⇒ v {\displaystyle u\Rightarrow \Rightarrow v} ）であるとは、 u ⇒ u 1 ⇒ u 2 ⋯ ⇒ u k ⇒ v {\displaystyle u\Rightarrow u_{1}\Rightarrow u_{2}\cdots \Rightarrow u_{k}\Rightarrow v} となるような ∃ u 1 , u 2 , ⋯ u k ∈ ( V ∪ Σ ) ∗ , k ≥ 0 {\displaystyle \exists u_{1},u_{2},\cdots u_{k}\in (V\cup \Sigma )^{*},k\geq 0} が成り立つ場合である。
追加定義4

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

L ( G ) = { w ∈ Σ ∗ : S ⇒ ∗ w } {\displaystyle L(G)=\{w\in \Sigma ^{*}:S{\stackrel {*}{\Rightarrow }}w\}}
追加定義5

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

最初の例を示す。

S → aSb 。ε

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

{ a n b n : n ≥ 0 } {\displaystyle \{a^{n}b^{n}:n\geq 0\}}