正規表現とチョムスキー階層に関する簡単なまとめ

テキスト検索などに利用される正規表現は、チョムスキーのタイプ-3文法(正規文法)に由来する。チョムスキーは句構造文法をタイプ-0からタイプ-3までの4つの階層に分類した。

タイプ-0	-	制限なし
タイプ-1	文脈依存文法	αAβ→αγβ
タイプ-2	文脈自由文法	A→γ
タイプ-3	正規文法	A→aおよびA→aBまたはA→Ba

おおまかに言って、タイプ-1は左辺が複数ノードの場合もある句構造文法、タイプ-2は左辺が単一ノードの句構造文法、タイプ-3は二股枝分かれの句構造文法に相当する。このうち、正規表現はタイプ-3の正規文法に由来する。

(2012.8.5追記: タイプ-3は単なる二股枝分かれではなく、どちらか一方の枝が終端記号であるような二股枝分かれ)

実際に、簡単な正規表現を例にとって、それが正規文法でどのように表現されるか考えてみることにしよう。/ABC/という正規表現は、次のような句構造文法に対応する。

S1→A+S2
S2→B+S3
S3→C

正規表現でよく使われる繰り返し記号/*/、/+/、/?/などは次のような句構造文法で表現することができる。

/A*B/
S1→A+S1
S1→B

/A+B/
S1→A+S2
S2→A+S2
S2→B

/A?B/
S1→A+S2
S1→B
S2→B

実際には、最近の処理系で用いられる正規表現は、正規文法が本来表現できる範囲を超える文字列を表現できるとされる。が、大雑把な仕組みとしてはこんな感じである。