Regular Expression Matching Can Be Simple And Fast

Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...) Russ Cox rsc@swtch.com January 2007 Introduction This is a tale of two approaches to regular expression matching. One of them is in widespread use in the standard interpreters for many languages, including Perl. The other is used only in a few places, notably most implementations of awk and grep.

[miau]

幅優先探索にする＆ルートでなくノードを基準とすることで、NFA でも DFA と似たような動作にでき、複雑な正規表現も高速に実行できるという話。ただし後方参照は実現できないので、既存の NFA と併用を提案している。

[theatrical]

正規表現のアルゴリズムの話

[tettsyun]

regular expression

[hogem]

一度きちんと読みたい

[tanakaBox]

NFAとDFAの実装について。

[nakag0711]

斜め読み / perlってDFA使ってなかったんだ?

[kohedonian]

Regexpのパース処理速度に関する論文。 "非決定的"有限オートマトンの実装。

[teddy-g]

UNIXでやってたみたいに、NFAで状態遷移図の各ルートを並列で動かすと、DFAで前もって最適化するより早いという話。複雑な正規表現ほど差が大きくなるそうだ。

[Phinloda]

(English)

[kazy]

UNIX toolにおけるregexp実装の再評価

[k_37to]

詳しく書いてあるっぽい。頑張って読んでみるか＾＾；