形式文法

形式文法（けいしきぶんぽう、Formal Grammar）は、形式的に与えられた（形式体系を参照）文法である。「言語」をその言語における文の集合として与えるものとして、ここでは、（有限の）文字群上の有限長の文字列の（通常無限な）集合が、形式的に記述される。

形式文法にはふたつの捉えかたがある。それは「生成」と「分析」である。#チョムスキー階層の節および単独記事に詳細があるが、両者は対応するので、ある意味では同じものをそれぞれ逆の側から見たものにすぎない。

以下で「文法の規則（構文規則）の集まり」と呼んでいるのは、具体的には、句構造規則#基本モデルにあるようなものである。また終端記号と非終端記号の記事も参照のこと。

生成文法（Generative grammar）は、文法の規則（構文規則）の集まりを「トップレベルの非終端記号（たとえば <文>）から始めて、右辺に書き換える書き換え規則を適用していくことによって言語の文字列を生成することができる規則の集まり」と見るものである。
分析的文法（Analytic grammar）は、文法の規則（構文規則）の集まりを「任意の終端記号列に対し、パターンが一致すれば右辺から左辺に書き換え規則が適用できる規則の集まりであり、最終的にトップレベルの非終端記号（たとえば <文>）が得られれば受理されたとして、入力の列がその言語に含まれるか否かを判定できるもの」と見るものである。

生成文法は、ある言語に含まれる文字列を生成するアルゴリズムを定式化するもの、分析的文法は、ある言語に含まれる文字列を構文解析し受理するアルゴリズムを定式化するもの、とも言える（この2者への分類は、構文解析の手法の分類の、トップダウン構文解析とボトムアップ構文解析といくぶんかまぎらわしい。実際に、トップダウン構文解析は流れとして左辺から右辺への書換えとなっている点は生成的であるのに対し、一方のボトムアップ構文解析は右辺から左辺への「還元」（reduce）を主要な動作とする点で分析的である。しかし、どちらも構文解析を目的とするという点では、分析的文法にあたる）。

生成文法

生成文法は文字列変換規則の集まりである。ある言語の文字列を生成するには、まずひとつの「開始」文字だけから成る文字列から始めて、規則を適当な回数適用して文字列を書き換えていく。逆に言えば、その言語はその規則群によって生成される全文字列を含む。ある規則の組み合わせで生成された文字列について、別の規則の適用の仕方でも同じ文字列が生成できる場合、その文法は曖昧であると言う。

たとえば、' $a$ ' と ' $b$ ' から成る文字セットがあり、開始記号 ' $S$ ' に対して以下の規則を適用するものとする。

1.

S\longrightarrow aSb

2.

S\longrightarrow ba

そこで、" $S$ " から開始して、適用する規則を選んでいくことができる。規則1を選ぶと、開始記号 ' $S$ ' から ' $aSb$ ' に変換されるので " $aSb$ " が得られる。再度規則1を選ぶと、' $S$ ' が ' $aSb$ ' に変換されるので全体として " $aaSbb$ " となる。この過程は最終的に本来の文字セット（つまり ' $a$ ' と ' $b$ '）だけから構成される文字列になるまで続けられる。さて、終了させるために規則2を適用すると ' $S$ ' が ' $ba$ ' に変換されるので、最終的に " $aababb$ " を得る。この過程をまとめると $S\longrightarrow aSb\longrightarrow aaSbb\longrightarrow aababb$ となる。この文法による言語はこのような過程で生成される全文字列 $\left\{ba,abab,aababb,aaababbb,...\right\}$ を含む。

形式的定義

生成文法の定式化は1950年代にノーム・チョムスキーによって最初に提案された^[1]^[2]。文法 G は以下の構成要素から成る。

「非終端記号」の有限集合 $N$ 。
「終端記号」の有限集合 $\Sigma$ 。 $N$ とは共通の元を持たない。
「生成規則」の有限集合 $P$ 。各生成規則は以下のような形式である。

(\Sigma \cup N)^{*}

内の文字列

\longrightarrow (\Sigma \cup N)^{*}

内の文字列

（ここで

{}^{*}

はクリーネスターであり、

\cup

は和集合であり）

\longrightarrow

の左側には少なくともひとつ以上の非終端記号を含まなければならない。

$N$ 内の記号 $S$ は「開始記号」である。

一般にこのような形式文法 $G$ は 4要素 $(N,\Sigma ,P,S)$ で要約される。

形式文法 $G=(N,\Sigma ,P,S)$ の言語は ${\boldsymbol {L}}(G)$ と記述され、開始記号 $S$ に $P$ の規則を非終端記号が無くなるまで適用して得られる（ $\Sigma$ 内の文字から構成される）全ての文字列として定義される。

例

以下の例では、形式言語を集合の内包的記法で記述している。

$N=\left\{S,B\right\}$ , $\Sigma =\left\{a,b,c\right\}$ の文法 $G$ について、生成規則 $P$ が以下の規則から構成される。

1.

S\longrightarrow aBSc

2.

S\longrightarrow abc

3.

Ba\longrightarrow aB

4.

Bb\longrightarrow bb

また、非終端記号 $S$ は開始記号である。 ${\boldsymbol {L}}(G)$ における文字列生成の実例は以下のようになる。

${\boldsymbol {S}}\longrightarrow (2)abc$
${\boldsymbol {S}}\longrightarrow (1)aB{\boldsymbol {S}}c\longrightarrow (2)a{\boldsymbol {Ba}}bcc\longrightarrow (3)aa{\boldsymbol {Bb}}cc\longrightarrow (4)aabbcc$
${\boldsymbol {S}}\longrightarrow (1)aB{\boldsymbol {S}}c\longrightarrow (1)aBaB{\boldsymbol {S}}cc\longrightarrow (2)a{\boldsymbol {Ba}}Babccc\longrightarrow (3)aaB{\boldsymbol {Ba}}bccc\longrightarrow (3)aa{\boldsymbol {Ba}}Bbccc$ $\longrightarrow (3)aaaB{\boldsymbol {Bb}}ccc\longrightarrow (4)aaa{\boldsymbol {Bb}}bccc\longrightarrow (4)aaabbbccc$

（カッコ内の番号は適用した生成規則の番号であり、変換された部分がボールド体で示されている。）

以上のようにこの言語は、 $\left\{a^{n}b^{n}c^{n}|n>0\right\}$ という形式を表している（ $a^{n}$ は n 個の $a$ が並んだ文字列を意味する）。従って、この言語は正数個の 'a' を含み、その後に同じ個数の 'b' とさらに同じ個数の 'c' を並べた全ての文字列から構成される。

生成的形式文法はリンデンマイヤーシステム（Lシステム）と等価であるが、相違点もある。Lシステムでは「終端記号」と「非終端記号」を区別しないし、規則を適用する順序に制限がある。また、Lシステムは永遠に規則を適用し続けることができ、無限の文字列を生成する。一般に各文字列は空間内のある点に対応付けることができ、Lシステムの出力は空間内の点の集合の極限を定義しているとも言える。

チョムスキー階層

1956年にノーム・チョムスキーが初めて生成文法を定式化したとき^[1]、彼はそれを４つのタイプに分類した。これをチョムスキー階層と言う。これらのタイプの差異は、生成規則の制限の強さであり、表現できる形式言語の多様さである。重要なふたつのタイプとして「文脈自由文法」と「正規文法」がある。これらの文法で生成される言語はそれぞれ「文脈自由言語」と「正規言語」と呼ばれる。制限のない文法よりも非力ではあるが、これらの言語は有限オートマトンで受容（認識）することができ、構文解析が簡単であるために^[3]、これらの文法はよく使われる。たとえば文脈自由文法については効率的なLL法やLR法の構文解析器を生成するアルゴリズムが知られている。

文脈自由文法

文脈自由文法では、生成規則の左側にはひとつの非終端記号だけが置かれる。この制限があるため、文脈自由文法はあらゆる言語を生成できるわけではない。文脈自由文法で表現される言語を「文脈自由言語」と呼ぶ。

前述の例で定義された言語は文脈自由言語ではない。これは文脈自由言語の反復補題を使って厳密に証明可能である。 $\left\{a^{n}b^{n}|n>0\right\}$ で表される言語（ひとつ以上の 'a' の後に同じ個数の 'b' が続く）を定義する文法 $G2$ を例として考えよう。 $G2$ は $N=\left\{S\right\}$ , $\Sigma =\left\{a,b\right\}$ から成り、開始記号 $S$ と以下の生成規則で定義される。

1.

S\rightarrow aSb

2.

S\rightarrow ab

文脈自由言語はアーリー法のようなアルゴリズムを使って $O(n^{3})$ の時間（ランダウの記号参照）で認識可能である。すなわち、全ての文脈自由言語について、任意の文字列を入力とし、それが特定の言語に含まれるかどうかを $O(n^{3})$ の時間内に決定する機械を構築できる。ここで、 $n$ は入力文字列長である^[4]。さらに、文脈自由言語の重要なサブセットは他のアルゴリズムを使って線形時間で認識可能である。

正規文法

正規文法でも生成規則の左側はひとつの非終端記号だけが置かれるが、さらに右側も制限が加えられ、ひとつの終端文字か、ひとつの終端文字とひとつの非終端記号から成る文字列のいずれかしか許されない。（広く採用されている定義として、複数の終端文字で構成される文字列か、ひとつの非終端文字のいずれか、という言い方もできる。どちらにしても同じクラスの言語を意味している。）

$\left\{a^{n}b^{m}|m,n>0\right\}$ で表される言語（ひとつ以上の 'a' の後にひとつ以上の 'b' が続く）を定義する文法 $G3$ を例として考える。 $G3$ は $N=\left\{S,A,B\right\}$ , $\Sigma =\left\{a,b\right\}$ から成り、開始記号 $S$ と以下の生成規則で定義される。

1.

S\rightarrow aA

2.

A\rightarrow aA

3.

A\rightarrow bB

4.

B\rightarrow bB

5.

B\rightarrow b

6.

S\rightarrow \epsilon

正規文法で生成される言語は、全て有限オートマトンで線形時間内で認識される。実際には正規文法は正規表現で表されるのが一般的だが、正規表現が必ずしも正規文法を表すためだけに使われるとは限らない。

正規言語と文脈自由言語

以上のふたつの言語を生成した生成規則の違いとは別に、ふたつの言語 $\left\{a^{n}b^{n}|n>0\right\}$ （文脈自由）と $\left\{a^{n}b^{m}|n,m>0\right\}$ （正規）の高いレベルで見たときの大きな違いは、文脈自由言語では 'a' の個数と 'b' の個数が同じになるということである。つまり、文脈自由言語を理解するオートマトンは正規言語を理解するオートマトンよりも保持すべき情報が多い。正規言語では 'a' や 'b' の個数を数える必要はなく、単にどちらもゼロより多いことだけを確認できればいいのである。

詳細については文脈自由言語と正規言語を参照されたい。

生成文法のその他の形式

形式文法についてのチョムスキーの本来の階層に対して言語学者や情報工学者が独自の拡張や派生を試みてきた。その目的は表現力を強化するか構文解析をやりやすくするためである。もちろん、これら二つの目的は方向性が異なる。表現力が強化された形式文法は自動化されたツールによる構文解析は困難となる。最近開発された文法には以下のようなものがある。

木接合文法は、文字列だけでなく構文木も操作することによって規則を書き換えて、従来の文法で生成されるよりも表現力豊かな言語を生成する^[5]。
接辞文法^[6]と属性文法^[7]^[8]は、意味属性と意味に関する操作を加えて生成規則を書き換えられるようにした。これにより表現力を増加させると共に、実用的な言語変換ツールを構築するのにも有効である。

分析的文法

プログラミング言語処理系の実装のフロントエンドとしてさかんに研究されたため、それに関係する構文解析についての論文は非常に多い。それらでは、解析対象の言語を形式的に定義し、そこから動作可能な構文解析器を生成することが目標である。自然言語についても計算言語学や自然言語処理などで必要であり、研究されている。いくつかの例を示す。

Yacc
The Language Machine は制限のない分析的文法を直接実装したものである。置換規則は入力を変換して出力とふるまいを生成する。このシステムは、制限のない分析的文法の規則を適用したときに何が起きているかを図示することもできる。
Top-Down Parsing Language、TDPL：1970年代初期に開発された高度なミニマリスト分析的文法であり、下降型構文解析のふるまいを研究することがその目的である^[9]。
Parsing Expression Grammar：TDPLをさらに汎用化したもので、プログラミング言語やコンパイラ作成者が実用的な表現をするために設計したものである^[10]。
リンク文法：言語学者によって設計された分析的文法の形式。単語間の所有関係を調べる文法構造を導く^[11]^[12]。

脚注

^ ^a ^b Chomsky, Noam, "Three Models for the Description of Language," IRE Transactions on Information Theory, Vol. 2 No. 2, pp. 113-123, 1956.
^ Chomsky, Noam, Syntactic Structures, Mouton, The Hague, 1957.
^ Grune, Dick & Jacobs, Ceriel H., Parsing Techniques—A Practical Guide, Ellis Horwood, England, 1990.
^ Earley, Jay, "An Efficient Context-Free Parsing Algorithm," Communications of the ACM, Vol. 13 No. 2, pp. 94-102, February 1970.
^ Joshi, Aravind K., et al., "Tree Adjunct Grammars," Journal of Computer Systems Science, Vol. 10 No. 1, pp. 136-163, 1975.
^ Koster , Cornelis H. A., "Affix Grammars," in ALGOL 68 Implementation, North Holland Publishing Company, Amsterdam, p. 95-109, 1971.
^ Knuth, Donald E., "Semantics of Context-Free Languages," Mathematical Systems Theory, Vol. 2 No. 2, pp. 127-145, 1968.
^ Knuth, Donald E., "Semantics of Context-Free Languages (correction)," Mathematical Systems Theory, Vol. 5 No. 1, pp 95-96, 1971.
^ Birman, Alexander, The TMG Recognition Schema, Doctoral thesis, Princeton University, Dept. of Electrical Engineering, February 1970.
^ Ford, Bryan, Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking, Master’s thesis, Massachusetts Institute of Technology, Sept. 2002.
^ Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," Technical Report CMU-CS-91-196, Carnegie Mellon University Computer Science, 1991.
^ Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," Third International Workshop on Parsing Technologies, 1993. (Revised version of above report.)

外部リンク

Yearly Formal Grammar conference

[Chomsky1956-1] Chomsky, Noam, "Three Models for the Description of Language," IRE Transactions on Information Theory, Vol. 2 No. 2, pp. 113-123, 1956.

[Chomsky1957-2] Chomsky, Noam, Syntactic Structures, Mouton, The Hague, 1957.

[Grune&Jacobs1990-3] Grune, Dick & Jacobs, Ceriel H., Parsing Techniques—A Practical Guide, Ellis Horwood, England, 1990.

[Earley1970-4] Earley, Jay, "An Efficient Context-Free Parsing Algorithm," Communications of the ACM, Vol. 13 No. 2, pp. 94-102, February 1970.

[JoshiEtAl1975-5] Joshi, Aravind K., et al., "Tree Adjunct Grammars," Journal of Computer Systems Science, Vol. 10 No. 1, pp. 136-163, 1975.

[Koster1971-6] Koster , Cornelis H. A., "Affix Grammars," in ALGOL 68 Implementation, North Holland Publishing Company, Amsterdam, p. 95-109, 1971.

[Knuth1968-7] Knuth, Donald E., "Semantics of Context-Free Languages," Mathematical Systems Theory, Vol. 2 No. 2, pp. 127-145, 1968.

[Knuth1971-8] Knuth, Donald E., "Semantics of Context-Free Languages (correction)," Mathematical Systems Theory, Vol. 5 No. 1, pp 95-96, 1971.

[Birman1970-9] Birman, Alexander, The TMG Recognition Schema, Doctoral thesis, Princeton University, Dept. of Electrical Engineering, February 1970.

[10] Ford, Bryan, Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking, Master’s thesis, Massachusetts Institute of Technology, Sept. 2002.

[Sleater&Temperly1991-11] Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," Technical Report CMU-CS-91-196, Carnegie Mellon University Computer Science, 1991.

[Sleater&Temperly1993-12] Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," Third International Workshop on Parsing Technologies, 1993. (Revised version of above report.)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]