形式文法

出典: フリー百科事典『ウィキペディア（Wikipedia）』

情報工学における形式文法（けいしきぶんぽう、Formal Grammar）は、形式言語を正確に記述するものである。すなわち、（有限の）文字群上の有限長の文字列の（通常無限な）集合を数学的に詳述する規則の集まりである。形式文法は自然言語の文法との類推から文法と名づけられた。

形式文法はふたつのカテゴリに分類される。それは「生成」と「分析」である。

生成文法は、ある特定の開始文字から書き換え規則を適用していくことによって言語の文字列を生成することができる規則の集まりである。生成文法は、ある言語に含まれる文字列を生成するアルゴリズムを定式化するものである。

分析的文法（Analytic grammar）は、任意の入力文字列に適用する規則の集まりであり、それによって最終的に真理値が得られ、入力文字列がその文法で表される言語に含まれるか否かを判定するものである。分析的文法は、ある言語の構文解析を定式化したものである。

端的に言えば、分析的文法は言語の読み方を記述したもので、生成文法は言語の書き方を記述したものと言える。

[編集] 生成文法

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

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

1. $S \longrightarrow aSb$

2. $S \longrightarrow ba$

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

[編集] 形式的定義

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

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

$(\Sigma \cup N)^{*}$ 内の文字列 $\longrightarrow (\Sigma \cup N)^{*}$ 内の文字列

（ここで

*

はクリーネスターであり、 $\cup$ は和集合であり） $\longrightarrow$ の左側には少なくともひとつ以上の非終端記号を含まなければならない。

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

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

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

[編集] 例

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

$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' が続く）を定義する文法 $G 2$ を例として考えよう。 $G 2$ は $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' が続く）を定義する文法 $G 3$ を例として考える。 $G 3$ は $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]は、意味属性と意味に関する操作を加えて生成規則を書き換えられるようにした。これにより表現力を増加させると共に、実用的な言語変換ツールを構築するのにも有効である。

形式文法に関する学会が毎年開催されている。[1]

[編集] 分析的文法

構文解析アルゴリズムについての論文は非常に多い。それらは解析対象の言語を生成文法で定義し、それを動作可能な構文解析器に変換することが目標である。別の手法として、分析的文法で言語を定式化して直接的に構文解析の構造に対応させる場合がある。分析的文法としては以下のものがある。

The Language Machine は制限のない分析的文法を直接実装したものである。置換規則は入力を変換して出力とふるまいを生成する。このシステムは、制限のない分析的文法の規則を適用したときに何が起きているかを図示することもできる。
下降型解析言語（Top-Down Parsing Language、TPDL)：1970年代初期に開発された高度なミニマリスト分析的文法であり、下降型構文解析のふるまいを研究することがその目的である^[9]。
解析表現文法（Parsing expression grammar、PEG）：TPDLをさらに汎用化したもので、プログラミング言語やコンパイラ作成者が実用的な表現をするために設計したものである^[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

"http://ja.wikipedia.org/wiki/%E5%BD%A2%E5%BC%8F%E6%96%87%E6%B3%95" より作成

カテゴリ: 形式言語 | 数学に関する記事

wiki-net.info - Encyklopedia Internetowa