形式文法

形式文法は、形式的に与えられた文法である。「言語」をその言語における文の集合として与えるものとして、ここでは、文字群上の有限長の文字列の集合が、形式的に記述される。 形式文法にはふたつの捉えかたがある。それは「生成」と「分析」である。#チョムスキー階層の節および単独記事に詳細があるが、両者は対応するので、ある意味では同じものをそれぞれ逆の側から見たものにすぎない。

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

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

1. 生成文法
-------

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

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

1. 2. そこで、"" から開始して、適用する規則を選んでいくことができる。規則1を選ぶと、開始記号 '' から '' に変換されるので "" が得られる。再度規則1を選ぶと、'' が '' に変換されるので全体として "" となる。この過程は最終的に本来の文字セットだけから構成される文字列になるまで続けられる。さて、終了させるために規則2を適用すると '' が '' に変換されるので、最終的に "" を得る。この過程をまとめると となる。この文法による言語はこのような過程で生成される全文字列 を含む。

1.1. 形式的定義
----------

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

「非終端記号」の有限集合 。
「終端記号」の有限集合 。 とは共通の元を持たない。
「生成規則」の有限集合 。各生成規則は以下のような形式である。 内の文字列 内の文字列 の左側には少なくともひとつ以上の非終端記号を含まなければならない。
内の記号は「開始記号」である。一般にこのような形式文法 は 4要素 で要約される。

形式文法 の言語は と記述され、開始記号 に の規則を非終端記号が無くなるまで適用して得られる全ての文字列として定義される。

1.2. 例
------

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

, の文法 について、生成規則 が以下の規則から構成される。

1. 2. 3. 4. また、非終端記号 は開始記号である。 における文字列生成の実例は以下のようになる。

以上のようにこの言語は、 という形式を表している。従って、この言語は正数個の 'a' を含み、その後に同じ個数の 'b' とさらに同じ個数の 'c' を並べた全ての文字列から構成される。

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

1.3. チョムスキー階層
-------------

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

1.3.1. 文脈自由文法
-------------

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

前述の例で定義された言語は文脈自由言語ではない。これは文脈自由言語の反復補題を使って厳密に証明可能である。 で表される言語を定義する文法 を例として考えよう。 は , から成り、開始記号 と以下の生成規則で定義される。

1. 2. 文脈自由言語はアーリー法のようなアルゴリズムを使って の時間で認識可能である。すなわち、全ての文脈自由言語について、任意の文字列を入力とし、それが特定の言語に含まれるかどうかを の時間内に決定する機械を構築できる。ここで、 は入力文字列長である。さらに、文脈自由言語の重要なサブセットは他のアルゴリズムを使って線形時間で認識可能である。

1.3.2. 正規文法
-----------

正規文法でも生成規則の左側はひとつの非終端記号だけが置かれるが、さらに右側も制限が加えられ、ひとつの終端文字か、ひとつの終端文字とひとつの非終端記号から成る文字列のいずれかしか許されない。

で表される言語を定義する文法 を例として考える。 は , から成り、開始記号 と以下の生成規則で定義される。

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

1.3.3. 正規言語と文脈自由言語
------------------

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

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

1.4. 生成文法のその他の形式
----------------

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

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

2. 分析的文法
--------

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

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

3. 関連項目
-------

抽象構文木
バッカス・ナウア記法
曖昧な文法
文脈自由言語の反復補題
構文木
句構造規則
L-system
ロジバン

4. 脚注
-----

5. 外部リンク
--------

[2]