北海道苫小牧市出身の初老PGが書くブログ

永遠のプログラマを夢見る、苫小牧市出身のおじさんのちらしの裏

正規表現エンジンを作ろう(6)

連載最終回では、主にNFAエンジンについて説明しました。鬼車等の正規表現エンジンも記事で紹介したエンジンのようにNFAをバイトコードに変換して処理を行っています*1ので、今回の記事が少しでもソースを読む際の助けになればと思います。

さて、記事中で紹介したregexですが、こいつはキャプチャも対応しています。連載の中では一切キャプチャに触れませんでしたので、どのように行っているのか簡単にソースを追っかけてみましょう。

*1:当然もっと色々やってて複雑ですけど。

続きを読む

正規表現エンジンを作ろう(5)

連載第五回にして、ようやく正規表現エンジンが完成しました。それとも、逆にあっけなく完成してしまって拍子抜けと言ったほうがいいでしょうか??(笑) こんなに簡単に実装できたのは、今回のエンジンではキャプチャを実装してないことが大きいでしょう。キャプチャを実装するとなると、同時に「最長一致*1」を実現しなければならなくなりますので、実装は複雑になります。

さて、今回作ったエンジンはDFAエンジンでしたが、こちらのエントリで作った深さ優先のNFA評価器を使うと、NFAエンジンもどきを作ることができます。

*1:greedy match

続きを読む

正規表現エンジンを作ろう(4)

連載も第四回となりました。今回が正規表現エンジンを作る上で一番重要な部分で*1正規表現とNFAの関係を説明しています。結局は当たり前のことしか言ってないんですが、そこはコロンブスの卵でして、知ってるのと知らないのとでは大違いです。

さて、この連載ではNFAをPythonで定義通りに忠実に実装しています。

この連載ではその数学的な概念をPythonを使って表現しながら、実際に動作する正規表現エンジンを作り上げます。

第一回

この実装は概念を理解するのには有用なのですが、実用的な正規表現エンジンとしては明らかにオーバースペックです。Regular Expression Matching Can Be Simple And FastでのC++での実装を見ながら、現実的なNFA表現の落としどころを簡単に見てみましょう。

*1:DFAエンジンに関して言えば、次回の部分集合構成法も超重要です。

続きを読む

正規表現エンジンを作ろう(3)

第三回の公開です。今回は字句解析と構文解析を自作しました。

本格的な構文解析器は、通常 yacc 等のツールを利用して自動で作ることが多いですが、今回の正規表現の文法は単純なので自作してしまいます。

じゃあ、ツールを利用するとどうなるの? ってのをやってみましょう。PLYを使って今回の記事の処理を作ってみます。PLYは、lexとyaccPythonで実装し直したツールです。

続きを読む

正規表現エンジンを作ろう(2)

CodeZineさん第ニ回が公開されました。今回は最も底辺の部分である、NFAとDFAを実装しています。ただし、NFAの実行部に関しては以下の通り実装しませんでした。

このためNFAを実行するソースはDFAに比べてかなり複雑になります。

ただし、今回はNFAを実行することはないので、NFAを実行するソースは実装しません。

これを、実装してみましょう。第一回で述べた通り、NFAを評価するには2種類の方法があります。

続きを読む

正規表現エンジンを作ろう(1)

CodeZineさんで連載を始めました。全6回でDFAエンジンの実装方法を紹介する予定なので、興味のある方はぜひ*1

ところで、第一回で出て来た /^([a-z]*)\1$/ と言う正規表現ですが、

 残念なことに、数学的な3つの定義ではこの正規表現が表す文字列集合を表現できません。このことは数学的に証明も可能です。

と書きました。この証明をするには、正規言語のポンピングレンマってのを使います。

証明

この正規表現が表す言語が、正規言語であると仮定します。ポンピングレンマより、p≧1がポンピング長pが存在します。

このpに対し、長さがp以上である、a..(p個)..aba..(p個)..abと言う2p+2の長さの /^([a-z]*)\1$/ にマッチする文字列を考えます。ポンピングレンマより、この文字列はある XYZ と言う三つの部分文字列にわけられて、ポンピング補題の3条件を満たすはずです。

ここでまず、XYZは2つの条件である |Y| > 0 と |XY| ≦ p を満たしています。この時、 a..aba..ab の最初のp 文字は a であるため、XY は全てaからなります。特に、Yが aを1文字以上繋げたものであることに着目して下さい。

ここで XYYZ と言う文字列を考えると、この文字列は、 a..(p個より多い)..aba..(p個)..ab となってしまうため、/^([a-z]*)\1$/ にマッチしません。つまり、 ポンピングレンマの最後の条件が i=2 に対して成立する・・・つまり、 XYYZ ∈ /^([a-z]*)\1$/ が成り立たなければいけないことに矛盾します。

以上から背理法により /^([a-z]*)\1$/ は正規言語ではありません。

参考文献

計算理論の基礎 [原著第2版] 1.オートマトンと言語
太田 和夫 田中 圭介 阿部 正幸

4320122070
共立出版 2008-05-21
売り上げランキング : 43388

Amazonで詳しく見る
by G-Tools

*1:ただし、動作を理解するのが目的の実装ですので実用性はないですw

最短一致マッチで誤解しやすいこと

問題

文字列'abcccde'に対して、以下の最短一致マッチ(non-greedy match)を使った(1)から(4)の正規表現をかけたときのマッチ結果は? (マッチするかしないかではなく、どの部分がマッチして $& に入るかです。)

foreach my $regexp (
    qr/bc*/  , # (1)
    qr/bc*?/ , # (2)
    qr/c*d/  , # (3)
    qr/c*?d/ , # (4)
){
    if( 'abcccde' =~ $regexp ){
        print $regexp, " -> match: $&\n";
    }else{
        print "no match.\n";
    }
}

実行せずに(4)がわかれば、通です。オレは間違えました(笑。

続きを読む