コンパイラ/正規言語

Wikipedia

ウィキペディアに正規言語の記事があります。

正規表現の規定[編集]

Wikipedia

ウィキペディアに正規表現の記事があります。

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

演算記号[編集]

$|$

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}$ があってはならない、ということである。

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

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