活動日誌

■ 正規表現エンジンの見分け方

詳説正規表現第2版 140 ページより。

/a|ab/ を "ab" にマッチさせたとき、a だけがマッチしたら従来型 NFA か DFA。POSIX NFA は最長マッチを探すので ab にマッチする。

/aXXaaaaaaaaaaaaaaaaaaaaa/ を 'X(.+)+X' にマッチさせたとき、 時間がかかったりエラーになったら NFA で、すぐ終わったら DFA。 ただし、最適化が施された NFA の場合もある。

Emacs も Ruby も従来型 NFA。