文脈自由文法

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

文脈自由文法（ぶんみゃくじゆうぶんぽう、Context-free Grammar、CFG）とは、言語学や情報工学において全生成規則が以下の形式である形式文法のひとつである。

V → w

ここで V は非終端記号であり、w は終端文字と非終端記号から構成される文字列である。「文脈自由」という用語は前後関係に依存せずに非終端記号 V を w に置換できることを意味している。文脈自由文法によって生成される形式言語を文脈自由言語という。

文脈自由文法はほとんどのプログラミング言語の文法を記述できるほど強力である。実際、多くのプログラミング言語は文脈自由文法で構文仕様を定義している。また、文脈自由文法は効率的な構文解析アルゴリズムを適用できる程度に単純である。つまり、ある文字列が特定の文法による言語に属しているかどうかを判断することができる。初期の構文解析手法であるLR法やLL法は文脈自由文法のサブセットを扱うものであった。

BNF（バッカス・ナウア記法）は文脈自由文法を記述する方法として広く使われている。

全ての形式言語が文脈自由ではない。文脈自由でない例として $\{ a^n b^n c^n : n \ge 0 \}$ がある。この言語は Parsing Expression Grammar（PEG）で生成できる。PEG はプログラミング言語に適した新たな定式化のひとつである。

[編集] 形式的定義

形式文法として、文脈自由文法 G は以下の 4要素から構成される。

$G = (V t, V n, P, S)$ ここで

$V t$ は終端文字の有限集合
$V n$ は非終端記号の有限集合
$P$ は生成規則の有限集合
$S$ は $V n$ の要素で、開始記号である。
$P$ に含まれる各生成規則は以下の形式である。

$V_n \longrightarrow (V_t \cup V_n)^*$

[編集] 例

[編集] 例 1

最初の例は非常に単純な以下の規則で表される。

S → aSb | ε

ここで | は論理和を意味し、S を置換可能な文字列を併記するのに使われる。ε は空の文字列を意味する。この文法によって生成される言語は以下のようになる。 $\{ a^n b^n : n \ge 0 \}$ これは正規言語ではない。

[編集] 例 2

次は三種類の変数 x, y, z を使った文法的に正しい四則演算の数式を生成する文脈自由文法である。ここで演算子は中置としている。

S → x | y | z | S + S | S - S | S * S | S/S | (S)

この文法に従うと、例えば "( x + y ) * x - z * y / ( x + x )" といった式が生成可能である。

[編集] 例 3

文字セット {a,b} について、異なる個数の a と b から構成される全ての文字列を生成する文脈自由文法は以下のようになる。

S → U | V

U → TaU | TaT

V → TbV | TbT

T → aTbT | bTaT | ε

ここで、T に関する生成規則は a と b が同数の文字列を生成するが、U は a の方が必ず多くなる文字列を生成し、V は b の方が必ず多くなる文字列を生成する。

[編集] 例 4

次の例は $\{ a^n b^m c^{m+n} : n \ge 0, m \ge 0 \}$ である。これは正規言語ではなく文脈自由言語である。以下の生成規則で生成される（この生成規則は文脈自由文法にしたがっている）。

S → aSc | B

B → bBc | ε

[編集] その他の例

文脈自由文法は数学的な「形式的」言語だけで利用されるわけではない。古代インドの言語学者パーニニはサンスクリットを文脈自由文法で記述した。タミル語の詩である Venpa は文脈自由文法で定式化できることが最近指摘されている。

[編集] 導出と構文木

ある文法において、開始記号からある文字列が導出される過程を記述する方法は二種類存在する。単純な方法は導出過程の途中の文字列を全て書き出していく方法である。つまり開始記号から始めて、生成規則を一回適用する度に文字列を書き出して、最後に目的の文字列になるまで列挙するのである。例えば「左端に最も近い非終端記号を最初に書き換える」という規則を適用したとすれば、文脈自由文法では適用する生成規則を列挙するだけで十分である。これを文字列の「左端導出」（Leftmost Derivation）と呼ぶ。例えば、以下の文法があるとする。

(1) S → S + S

(2) S → 1

文字列「1 + 1 + 1」を導出する過程は [ (1), (1), (2), (2), (2) ] というリストになる。同様に「右端導出」も定義できる。この例の場合右端導出での導出過程は [ (1), (2), (1), (2), (2)] というリストになる。

左端導出と右端導出のリストが異なるのは重要なポイントである。構文解析では、文法規則毎にそれを入力文字列に適用する小さなプログラムが存在する。したがって、構文解析が左端導出を行うのか右端導出を行うのかによってそれらのプログラムを適用する順番が変わってくるのである。

導出過程は導出される文字列上にある種の階層構造を描くことでも表される。例として左端導出による「1 + 1 + 1」に対する階層構造を見てみよう。導出過程は以下のようになる。

S→S+S (1)

S→S+S+S (1)

S→1+S+S (2)

S→1+1+S (2)

S→1+1+1 (2)

{ { { 1 }_S + { 1 }_S }_S + { 1 }_S }_S

ここで { ... }_S は S から導出された部分文字列を意味している。これに対応する階層構造は以下のような木構造になる。

            S
          /|\
         / | \
        /  |  \
       S  '+'  S
      /|\      |
     / | \     |
    S '+' S   '1'
    |     |
   '1'   '1'

この木構造をその文字列の「具象構文木」と呼ぶ（抽象構文木も参照されたい）。この場合、上述の左端導出も右端導出も同じ構文木になるが、左端導出には以下のような別の導出過程が存在する。

S→ S + S (1)

S→ 1 + S (2)

S→ 1 + S + S (1)

S→ 1 + 1 + S (2)

S→ 1 + 1 + 1 (2)

これによって定義される構文木は以下のようになる。

            S 
          /|\
         / | \
        /  |  \
       S  '+'  S
       |      /|\
       |     / | \
      '1'   S '+' S
            |     |
           '1'   '1'

この文法のように、ある文字列を導出する構文木が複数考えられる文法を「曖昧な文法」（Ambiguous Grammar）と呼ぶ。このような文法の構文解析は、生成規則の適用順序を毎回決定しなければならないため難しい。

[編集] 標準形

空の文字列を生成しない文脈自由文法は等価なチョムスキー標準形かグライバッハ標準形に変換できる。ここでいう「等価」とは同じ言語を生成するという意味である。

チョムスキー標準形文法は生成規則が単純なので、この標準形は理論的にも実用上も密接な関係がある。例えば、ある文脈自由文法についてチョムスキー標準形を使うことで多項式時間のアルゴリズムで入力された文字列がその文法で生成されるものか否かを判定できる（CYKアルゴリズム）。

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