コンパイラ/正規言語

正規表現の規定

正規表現はよくプログラムの文字列の解析に使われる。今から正規表現の規定を行う。

演算記号

• $|$

$r|s$ は、$r$ または $s$ のどちらかの要素を意味する。すなわち、$r|s$ は $r$ または $s$ である。

• 連結 ($\cdot$だが普通省略される)

$rs$ は見た目の通り、$r$ の要素の後に $s$ の要素をつなげたものである。

• $*$

$r*$ は、$r$ の0回以上の繰り返しを意味する。すなわち、$\epsilon ,r,rr,rrr,\ldots$ である。

• $()$

$(r)$ は $r$ と同じである。通常の計算式のように、優先順位を明確にするために使われる。

以上が正規表現の本質の表現である。次のものは、正規表現中によく出てくるといった理由で、拡張した省略記法の演算子もあるので代表例を紹介する。

• $+$

$r+$ は、$r$ の1回以上の出現である。$r+=rr*$ である。

• $?$

$r?$ は、$r$ の0回または1回の出現を表す。$r?=r|\epsilon$ である。

演算子の優先順位と結合

演算子を決めただけでは、例えば$r|s*$ は、 $(r|s)*$ なのか、 $r|(s*)$ なのか分からない。また、$r|s|t$は、$(r|s)|t$ (左結合)なのか、$r|(s|t)$ (右結合) なのか分からない。このように、無駄なカッコを多用しなくて済むように演算子の優先順位と結合を取り決める。なお、これは一般的な優先順位である。

• $*+?$ の3つは最も優先順位が高く、左結合である。
• 連結はその次に優先順位がたかく、左結合である。
• $|$ は最も優先順位が低く、左結合である。

正規表現の定義方法

先ほどから誤魔化して使っていたが、$=$ という記号がある。これは、$r=s$ のとき、r と s が等価であり、同じ言語を表すということを示す記号である。

正規表現の定義 (正規定義) は、

${\begin{aligned}d_{1}\to r_{1}\\d_{2}\to r_{2}\\d_{3}\to r_{3}\\d_{4}\to r_{4}\\\ldots \\d_{n}\to r_{n}\\\end{aligned}}$

という形で、文脈自由文法とかなり似ている。しかし、決定的な違いがあって、それは、$i\leq j$ のとき、$d_{i}\to r_{i}$ の $r_{i}$の中に $d_{j}$ があってはならない、ということである。

これにより、正規表現は再帰が制限されるので、文脈自由文法よりも小さい文法クラスになり、表現範囲が狭くなるのである。

文脈自由文法は完全に正規表現を包含し、文脈自由文法の方が大きいクラスである。このことの証明はここでは省くが、正規表現の定義方法が文脈自由文法とほとんど同じで、正規表現の演算子を文脈自由文法で置き換えてやることができれば、文脈自由文法は少なくとも正規表現以上であることが分かる。あとは文脈自由文法では表現可能だが正規表現では表せない言語、例えば釣り合ったカッコの列、があることを示せばこれは証明される。

演算子の法則

$|$ は、交換法則、結合法則、が成り立つ。式で表すと、

• $r|s=s|r$
• $r|(s|t)$

連結は、結合法則、$|$に対して分配法則、が成り立つ。式で表すと、

• $(rs)t=r(st)$
• $r(s|t)=rs|rt$

$\epsilon$は連結に対して単位元である。式で表すと、

• $\epsilon r=r\epsilon =r$

また、$\epsilon$に関して言えば、

• $r*=(r|\epsilon )*$
• $r+=rr*=r(r|\epsilon )*$
• $r?=(r|\epsilon )?$ である。

• $*,+,?$ は全て冪等性を持つ。式で表すと、
• $r**=r*$
• $r++=r+$
• $r??=r?$

以上は、別に非常に重要というわけではないが、暗黙の了解を明確化し、参考程度に思ってもらえばよい。

有限オートマトン

決定性オートマトン (DFA)、非決定性オートマトン (NFA) はどちらも正規言語を処理するだけの能力を持っている。正規表現と非決定性オートマトンのあいだのつながりは比較的理解しやすいので、まずはNFAの定義から始める。

注釈 : NFA とさらに ε遷移を含むNFA という分け方もあるが、ここでは NFA といったら ε遷移をも含むものとする。

NFA は以下の定義からなる。

• 状態と呼ばれるものの集合
• 入力文字の集合
• 状態 s, 入力文字 a に対して 状態を返す遷移関数 move(s, a)
• 開始記号と呼ばれ、他の状態とは区別される状態 s₀
• 受理状態と呼ばれ、他の状態とは区別される状態の集合

このNFAの表現の仕方には主に二つあり、それは遷移図と遷移表である。

遷移図

繊維図は、各状態を円として書き、move(s, a) = r ならばs から r に向かって、a をラベルに持つ矢印を書く。

遷移表

各状態と各入力記号列を縦横で並べたものである。空欄は誤りを意味する。