前のページ 1/2 次のページ

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

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

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

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

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

◆ 生成文法

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

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

: 1. $S\; \backslash longrightarrow\; aSb$

: 2. $S\; \backslash longrightarrow\; ba$

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

◇ 形式的定義

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

・ 「非終端記号」の有限集合 $N$。

・ 「終端記号」の有限集合 $\backslash Sigma$。$N$ とは共通の元を持たない。

・ 「生成規則」の有限集合 $P$。各生成規則は以下のような形式である。

:: $(\backslash Sigma\; \backslash cup\; N)^$ 内の文字列 $\backslash longrightarrow\; (\backslash Sigma\; \backslash cup\; N)^$ 内の文字列

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

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

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

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

◇ 例

$N\; =\; \backslash left\; \backslash$, $\backslash Sigma\; =\; \backslash left\; \backslash$ の文法 $G$ について、生成規則 $P$ が以下の規則から構成される。

: 1. $S\; \backslash longrightarrow\; aBSc$

: 2. $S\; \backslash longrightarrow\; abc$

: 3. $Ba\; \backslash longrightarrow\; aB$

: 4. $Bb\; \backslash longrightarrow\; bb$

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

・ $\backslash boldsymbol\backslash longrightarrow\; (2)\; abc$

・ $\backslash boldsymbol\backslash longrightarrow\; (1)\; aB\backslash boldsymbolc\; \backslash longrightarrow\; (2)\; a\backslash boldsymbolbcc\; \backslash longrightarrow\; (3)\; aa\backslash boldsymbolcc\; \backslash longrightarrow\; (4)\; aabbcc$

・ $\backslash boldsymbol\backslash longrightarrow\; (1)\; aB\backslash boldsymbolc\; \backslash longrightarrow\; (1)\; aBaB\backslash boldsymbolcc\; \backslash longrightarrow\; (2)\; a\backslash boldsymbolBabccc\; \backslash longrightarrow\; (3)\; aaB\backslash boldsymbolbccc\backslash longrightarrow\; (3)\; aa\backslash boldsymbolBbccc$$\backslash longrightarrow\; (3)\; aaaB\backslash boldsymbolccc\; \backslash longrightarrow\; (4)\; aaa\backslash boldsymbolbccc\; \backslash longrightarrow\; (4)\; aaabbbccc$

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

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

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

◇ チョムスキー階層

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

  文脈自由文法

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

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

: 1. $S\; \backslash rightarrow\; aSb$

前のページ 1/2 次のページ

・形式文法 page1

・形式文法 page2