PC | 練炭ブログ

正規表現技術入門 ――最新エンジン実装と理論的背景

2015年07月14日 02:14 - 製品レビュー, PCソフトウェア

コメントなし»

webdb_regexp

読みました。
勉強になりました（小並感

正規表現の入門書というより、正規表現エンジンの実装のための入門書。
正規表現エンジンを書きたいと思っているけどどうすればいいのか分からない、っていう人におすすめ。

一部のページは、Software Design 2013年5月号の正規表現特集に掲載された新屋氏自身の記事(sd_engine.pdf)がベースになっているっぽいです。

第2章
歴史が面白い。
Ken Thompson すごい。
Kleene はクリーネと読むのでしょうか。

p64
「合計が閾値θ(ノード内部)を超えると」は「θ以上」と書くべきではないか気になりましたが、ニューロン業界だとそういう表現をするらしい？

p75
『以降、本書では「POSIXの正規表現」と言えば「ERE」を指す』とあるので心して読み進めましたが、p246とp253でしか言われてない上にどちらもどの仕様かは関係ない意味合いで使われてました。

第3章
p99
TRE はこれでしょうか。
TRE — The free and portable approximate regex matching library.

p105
妥協するという選択肢っていいですね。
メールアドレスの正規表現はもう HTML5 方式だけでいいでしょ。

第4章
p127
「ε遷移の除去」という見出しですがε遷移のやり方を説明しつつ、中盤の「しかし、実はどんなε-NFAでもε遷移を取り除くことができます。……」という段落だけは除去の話をしているのでちょっと分かりにくかったです。

p131

しかし、現代の正規表現エンジンで有限オートマトンベースのマッチングをするもので、
NFA だけを用いるエンジンはほとんどありません。
NFA ベースのマッチングを実装しているエンジンは同時に DFA ベースのマッチングにも
対応しているのです。そのため、本書では有限オートマトンベースのマッチングを用いる
正規表現エンジンを DFA 型の正規表現エンジンと呼んでいます。

これはつまり

DFA に変換せず NFA のまま直接処理するエンジン(ごく少数)
NFA を DFA に変換して処理するエンジン
NFA のまま処理するコードと、NFA を DFA に変換して処理するコードを併せ持つエンジン

を DFA 型と呼んでいるということなのでしょうか。

NFA を DFA に変換して処理するという定義に限定すべきでは。

第4章は

分岐のない NFA の説明とコード
ε-NFA の説明とコード
部分集合構成法の説明とコード
DFA の説明とコード

というような順番で説明して欲しかったです。

第5章
p163,173
後方参照に使われるキャプチャにバックトラックが必要なのはなぜ？
いつか鬼雲のソースを読もう。

第6章
p221
固定文字列検索の分野も面白そう。

第7章
p241
(\D+|<\d+>)*[!?] と
(\D++|<\d+>)*[!?] が同じというのが分かりません。
手元で試しても違うように見えます。

p249
固定文字列検索でもオーバーラップしないという仕様はありえるし、正規表現にかぎらず文字列検索一般に該当する問題で、ただ正規表現の場合はオーバーラップしない仕様でも先読みを使えばオーバーラップさせられる、ということでは。

正規表現でもオーバーラップするものとしては、Mery 2.2.2.4953 | Haijin Boys Online とか Perl6 の overlap とか。

p257
可変長後読みはどこからマッチを開始するのかどうやって決めるのか、パターンを逆向きに構築して一文字ずつ後ろ向きにマッチしていく手法はどうか？とか、いろいろと大変だと昔なにかで見た気がします。

p257
空文字列の繰り返しをVM型エンジンでマッチしようとすると、無限ループになりいずれスタック溢れで止まると思うのですが、そういう問題ではないのでしょうか。

他の章で触れられてはいますがそちらでは最適化の一手としての説明ですし。

JavaScript のこの挙動は、
ECMA-262 Edition 5.1 15.10.2.5 Term

NOTE 4 Step 1 of the RepeatMatcher's d closure states that, once the minimum number of repetitions has been satisfied, any more expansions of Atom that match the empty String are not considered for further repetitions. This prevents the regular expression engine from falling into an infinite loop on patterns such as:

によるものだと思いますが、空文字列にマッチするかどうかは実際にマッチを試して成功してからでないと分からないのに「0回のマッチ(1回もマッチしていない)」として扱われるのが謎。

第8章
p264
VerbalExpressions より Regexp::Assemble を紹介した方がよかったかも。

Appendix
この本のメインディッシュ。
第1～8章のいろいろなところで「○○については Appendix で」という案内が書かれていたりします(各節冒頭のあらすじを除いても14か所くらい)。

もちろん第1～8章だけでも役に立ちます。

・組版的なところ

スペースを網掛け＋ルビで表記しているのは分かりやすいです。

第1章以外で正規表現が等幅フォントになっていないのは構わないけど、* が上付きになっているのは注釈記号に見えて紛らわしいので、それだけはなんとかして欲しかった。

図が多くて分かりやすいです。
ただ、この本に限らない一般的な作法ではありますが、図をページの一番下、紙面に余裕がない場合は次ページの一番下に落としてあるのが、本文と図が離れすぎて読みづらいです。正直廃れて欲しい風習……。

スクリーンショットに書き込まれているコメントが、背景色とほとんど同じ色で見づらいです。

ノンブルが文字ごとに上端下端が違うフォントなので、ページをパラパラとめくった時に数字が上下に動いているようで見づらいです。

・以下些細な点。

p43 - 下の方のコードはスクリーンショットなので黒地に白抜きでは。

p64 図2.1 -
(3) 1=x1&x2 は v=(略) では。
(4) v=￢x1 字が小さくて見えづらいけどマイナスじゃなくて否定記号であってる？

p109 図3.4 - このように塗ったほうがよかったのでは。

p113 - 正規表現が 0*(10*10*)*` と書いてあるように見えるけど、自分の本の印刷の汚れ？

p175 リスト5.16 - 2354行のコメントが薄字になっていない。

p194 -・(?(condition)yes|no)、(?(condition)yes)条件式
見出しレベルが違うのと、説明がよく分からない。

p204 図5.21 - a*+a のバイトコード

p217 図6.5 - #1 と #0 を繋ぐ線が矢印になっていない。

p235 - スクリーンショット 6、7行目の正規表現に ^ $ がない。

p242 - 一番上のスクリーンショット 3行目の正規表現に ^ $ がある。

p243 - スクリーンショット 3行目の正規表現に ^ $ がある。1、3行目が [!] になっている。

p265 リスト8.3 - 16行目のコメントが薄字になっていない。

p274 リスト8.6 - 「ですし」がおかしいのと、「数式」が別の意味で二つ使われていて紛らわしい。

p278 - 「これはintegerのdigitが1つ以上存在する」は「integerは数字が1つ以上存在する」あたりの方がよいのでは。

p279 リスト8.8 - integer だけラベルがついていて、上記の表現と相まって余計分かりづらくなっている。

p315 - A A A から C C C までだから 3^3=27 が正しい？

p334 - 索引にハ行がない（ハ行がないとは言ってない）

新屋良磨, 正規表現, 鈴木勇介, 高田謙

Catalyst Omega入れたら画面がピンクになった

2015年03月20日 00:24 - PCソフトウェア, PCハードウェア

コメントなし»

RADEON のドライバを入れたのが結構昔なので、たまにはアップデートしてみるかーと Catalyst Omega をインストールしたら画面がピンク色がかって表示されるようになってしまいました。

ドライバがぶっ壊れたかと肝を冷やしましたが、設定を修正して元に戻せました。

Catalyst, RADEON

Irvine: 『別名で保存』を指定すると同名のファイルがリネームされない

2015年03月10日 23:00 - Irvine

コメントなし»

フォルダ設定の「同名のファイルが有ればリネーム」にチェックを入れると、同名のファイルが存在する(＝既に一度ダウンロードが完了している)場合にリネーム([0]、[1]、……の付加)が行われます。

ただし、アイテム設定の「別名で保存」にファイル名を入力した場合はリネームが行われません。

この際フォルダ設定の「リジュームを行う」にチェックが入っていないと
リジュームを行いません → ダウンロードに失敗しました
となります。

一方、「リジュームを行う」にチェックが入っていると、サーバの仕様にもよりますが
プロトコルエラー(416 Requested range not satisfiable) → リジューム開始エラー
となります。
(サーバ上のファイルサイズを超えてデータを要求してしまうため)

いずれにせよダウンロードは失敗したという扱いになります。

しかも、フォルダ設定の「完了していないファイルを隠す」にチェックが入っているとダウンロード完了しているファイルに隠し属性が設定されるというオマケ付きです。

pixiv_r.dms のような Dorothy2 用スクリプトでは「別名で保存」に入力した形でアイテムを登録するので、この挙動が問題になります。
どう対処するのがいいんだろ……。

Proxomitron: 画像ちゃんねるURL修正

2015年02月27日 00:04 - Proxomitron

コメントなし»

[Patterns]
Name = "www.gazo-ch.net: fix image url  (2015-02-26; rentan)"
Active = TRUE
URL = "www.gazo-ch.net/$TYPE(htm)"
Limit = 1000
Match = "(<a\s[^>]++href=")\1(http://img.gazo-ch.net/bbs/)\9"
Replace = "\1http://\h/i/image.exec/1/1/?size=0&img_file=\9"

作ってみただけ。

画像ちゃんねる

DMonkey: 関数プロトタイプは同名の関数間で共有される

2015年01月27日 01:37 - Irvine

コメントなし»

スコープとか関係なしに、関数名が同じなら prototype は同じものが使用されます。
匿名関数は匿名関数同士で共有されます。

function a () {
  function f () { }
  f.prototype.foo = 'bar';
}

function b () {
  function f () { }

  alert (f.prototype.foo);  // bar
}

a ();
b ();

alert (
  (function () { }).prototype === (function () { }).prototype
);  // true

ちなみに { }.prototype で Object.prototype を参照してしまいます。

DMonkey

Proxomitron: pixiv Ad Killer

2015年01月17日 18:09 - Proxomitron

コメントなし»

[Patterns]
Name = "pixiv Ad Killer  (2015-01-07; )"
Active = TRUE
URL = "www.pixiv.net/$TYPE(htm)"
Limit = 30000
Match = "($NEST(<div,\s"
        "(class=$AV(ads_area|user-ad-container|search_a2_right|hotspot|ad(\s*)+|_premium-promotion*)"
        "|class=$AV(worksImageresponse)"
        "|id=$AV(back-to-top|header-banner)"
        ")*,</div>)"
        "|$NEST(<style(\s|>),*.ads_(area|anchor)*,</style>)"
        "|$NEST(<iframe,*src=$AV(http://serv.ads.pixiv.org/get.php*)*,</iframe>)"
        "|$NEST(<section,\sclass=$AV(popular-introduction)*,</section>)"
        "|<script\sid=$AV(template-thumbnail-filter)*</script>"
        "|"
        "$NEST(<div,\sclass=$AV(area_new)> *<a\shref=$AV((./premium|/print/service).php*)*,</div>)"
        "|"
        "<a\s+href=$AV((http://www.pixiv.net|.|)/premium.php*|/setting_user.php#premium_noads)*</a>"
        "|<li\sclass=$AV(info)[^>]+> <a\shref=$AV(premium.php*)*</li>"
        "|"
        "(<script(\s|>)*</script>&&*"
        "(http://((cache|adf.send).microad.jp|ads2.pixiv.net|pagead2.googlesyndication.com)/"
        "|ads_dokoiku|ads_textads_show|microadAds|ads_writed|window.pixivComicAds"
        ")*)"
        "|"
        "<a\s(target=$AV(*)|) href=$AV(http://serv.ads.pixiv.org/*)*</a>"
        ")$SET(#=<!-- Ad killed -->)"
        "|"
        "$NEST(<h1>,\s<div\sid=$AV(logoMap)*,</h1>)"
        "$SET(#=<h1><a id="logo" title="pixiv" href="http://www.pixiv.net/">pixiv</a></h1>)"
        "|"
        "<div\sclass=$AV(ad-footer)*(<footer)\#"
        "|"
        "<ul\sclass=$AV(_toolmenu)>*</ul>"
Replace = "\@"

<script> 以外はスタイルシートで display: none; を指定して非表示にした方が綺麗に書けるっぽいけど。

pixiv

Proxomitron: window.setIntervalで呼び出される関数のエラーを抑制する

2014年12月17日 01:35 - Proxomitron

コメントなし»

function hook (obj, name, func) {
  var orig = obj [name];
  var k = '__prox_' + name;
  if (!obj [k]) {
    obj [k] = orig;
  }
  obj [name] = func;
  return orig;
}
hook (window, 'setInterval', function (h, ms) {
  function f () {
    try {
      h ();
    }
    catch (e) { }
  }
  return window.__prox_setInterval (f, ms);
});

window.setInterval

DMonkey: String/StringBuffer オブジェクトの比較

2014年10月16日 00:41 - Irvine

コメントなし»

http://peace.2ch.net/test/read.cgi/win/1412399700/74 より。

別々の String オブジェクトを == 演算子や === 演算子で比較すると、true になってしまいます。

更に、StringBuffer オブジェクトや、String、StringBuffer を継承したクラス同士でもそうなります。

以下の例では、別々のオブジェクトなので正しくは false となるところ、全て true と表示されてしまいます。

class S extends String { }
class SB extends StringBuffer { }

var a = new String ('aaa');
var b = new String ('bbb');
var c = new S ('ccc');
var d = new S ('ddd');

alert (a === b);  // Stringの別々のインスタンス
alert (c === d);  // String派生クラスの別々のインスタンス
alert (a === c);  // StringとString派生クラス

var e = new StringBuffer ('eeee');
var f = new StringBuffer ('fff');
var g = new SB ('ggg');
var h = new SB ('hhh');

alert (e === f);  // StringBuffer
alert (g === h);  // StringBuffer派生クラス
alert (e === g);  // StringBufferとStringBuffer派生クラス

alert (a === e);  // StringとStringBuffer
alert (a === g);  // StringとStringBuffer派生クラス
alert (c === e);  // String派生クラスとStringBuffer
alert (c === g);  // String派生クラスとStringBuffer派生クラス

2015-03-22 追記
new してない String そのもの、StringBuffer そのものでも true になります。
派生クラスの場合(上の例の S や SB)は false です。

DMonkey

Irivne/Dorothy2: netinst.dms ネットインストール

2014年10月07日 18:16 - Irvine

コメントなし»

GitHub ではコミットごとに ZIP ファイルが自動生成されます。このファイルは Dorothy2 のパッケージインストール機能で扱えないこともありませんが、プロジェクトから出力して圧縮した書庫ではないため不要なファイルまでインストールされるといったデメリットがあります。

そこで、ZIP ファイルをダウンロードしてインストールする専用のツールを作っています。

自分自身は使わないし、必要とされるツールなのかどうか分かりませんが、一応形にはなったので反応を伺うためにも紹介しておきます。

ただ、簡単にインストールできるということが教えてクンを呼び込むことに繋がったら困る……。

設定画面のメニュー→パッケージ→ネットインストールで起動。

リストボックスがありますが選択肢は一つしか無いので、そのまま「ダウンロード」をクリックします。

netinst_2

ZIP ファイルのダウンロード、展開、内容の解析が行われ、スクリプトの一覧が表示されます。

ファイルに問題がある(必要なファイルが含まれない)場合は、ここでエラーが表示されます。

同じファイル名のスクリプトがインストール済みならチェックボックスにチェックが入り、「インストール済」欄にバージョンが表示されます。「→」は同じバージョンがインストールされていることを示します。

netinst_3

コンテキストメニューもあります。
WinMerge (WinMergeU.exe) がインストールされていれば差分を表示できます。

インストールしたいスクリプトにチェックを入れて「インストール」をクリックします。
(なおチェックを外してもアンインストールはされません)

※「新しいバージョンをインストールする」という動作ではなく「チェックを入れたスクリプトをインストールする」という動作です。同じバージョンや、より新しいバージョンがインストール済みでもチェックを入れたスクリプトは必ずインストールが行われます。

netinst_4

ファイルのコピーが行われ結果がステータスバーに表示されます。

ドキュメントが UTF-8 の場合は Shift_JIS に変換してインストールします。
今は Shift_JIS でレポジトリにコミットしていますが、このツールの使用を前提としていいなら UTF-8 でのコミットに変更したいと考えています。

netinst_5

先ほどの画面で「詳細表示」ボタンをクリックするとログファイルが開きます。

copy …… 新規ファイルをコピーした。
update …… 既存ファイルに上書きした。
same …… 同一内容のファイルが存在した(コピー省略)。
skip …… ファイル内容は異なるが、バージョン番号が同一なのでコピーしなかった。
※program\*.dms のみ適用。
error …… コピー時にエラーが発生した。

終了時に、ウィンドウ位置などの設定が Dorothy2\user\netinst.ini に保存されます。

Dorothy2, netinst.dms

Irvine/Dorothy2: ThreadStorage

2014年09月24日 00:20 - Irvine

4 個のコメント»

しばらく前から作っていた threadstorage ブランチを master にマージしました。
実験的な機能で、問題があれば削除して元に戻すかも知れません。

2ch で話題になっていた、プロセスIDとスレッドIDでダウンロードスレッドの同定を行い、スクリプトごしにデータを受け渡す仕組みです。common_load() で使える形式に実装し、Dorothy2R 本体側にも標準のインターフェースを設けています。

Dorothy2R_done.dms (Dorothy2B.dms に相当)とか Dorothy2R_resp.dms が増えています。

Dorothy2\common\threadstorage.dms は多分単体でも使えると思います。

いまのところ意味があるのは Dorothy.fileName = 'remove'; のための処理と、getuploader_r だけです。

自分の環境では、基本のキューフォルダは Dorothy2R_a.dms のみ有効、getuploader_r 用のフォルダは Dorothy2R_a.dms と Dorothy2R_resp.dms を有効にして使っています。

Dorothy2, Dorothy2R, ThreadStorage

練炭ブログ

X680x0、Irvine、DMonkey、Proxomitron などの情報を扱ってます。

正規表現技術入門 ――最新エンジン実装と理論的背景

Catalyst Omega入れたら画面がピンクになった

Irvine: 『別名で保存』を指定すると同名のファイルがリネームされない

Proxomitron: 画像ちゃんねるURL修正

DMonkey: 関数プロトタイプは同名の関数間で共有される

Proxomitron: pixiv Ad Killer

Proxomitron: window.setIntervalで呼び出される関数のエラーを抑制する

DMonkey: String/StringBuffer オブジェクトの比較

Irivne/Dorothy2: netinst.dms ネットインストール

Irvine/Dorothy2: ThreadStorage

カテゴリー

最近の投稿

アーカイブ

特設ページ

管理人

管理用メニューとRSS

Promotional Products

2026年1月
月	火	水	木	金	土	日
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31