正規表現の微分を Haskell で実装してみる - Qiita
この記事は 正規表現 Advent Calendar 2022 の 19 日目の記事です． いったい何番煎じかわかりませんが，正規表現の微分を Haskell で書いてみたときのメモが残っていたので，投下したいと思います． 正規表現の微分とは 正規表現の微分は，Brzozowski が提唱したもの [1] が知られており，Brzozowski 微分 (Brzozowski derivative) とも呼ばれます． ざっくりと説明するなら，正規表現 $r$ の文字列 $u$ に関する微分とは，$r$ の先頭から $u$ 部分だけを除いた正規表現のことをいいます． いくつか例を挙げてみます (連接の記号は省略しています)． 正規表現 abc の文字列 a に関する微分は bc 正規表現 abc の文字列 ab に関する微分は c 正規表現 abc の文字列 abc に関する微分は $\vare
正規表現エンジンを作ろう （1）
はじめに こんにちは。hirataraです。 私が初めて正規表現を使ったのは、PerlによるCGIでの文字列処理でした。それから私はPerlを使い続け、今では正規表現なしのコーディングは考えられないほど、正規表現を当たり前の機能として日常的に使っています。昔は標準では正規表現をサポートしていなかったJavaも、今では正規表現をサポートするようになりました。Javaだけではなく、今日ではほとんどの高級言語にとって、正規表現はなくてはならない機能であると言っても過言ではないほどメジャーな機能となっています。 本記事では、この正規表現の舞台裏に光を当てます。一見すると作ることが難しそうな正規表現エンジンですが、その根底には数学的な概念があり、その概念さえ知っていれば基礎となる機能の実装はそんなに難しくありません。この連載ではその数学的な概念をPythonを使って表現しながら、実際に動作する正規表
Copy/Cut/Paste:正規表現
4 正規表現の処理メカニズム 正規表現には2種類のエンジン(DFA、NFA)があるという話。 4.2 マッチの基本原則 ・最初(最左)のマッチが優先される。 ・標準の量定子(*、+、?、{n,m})は欲張りである。 4.2.4 第2原則:標準の量指定子は欲張りである 欲張り量指定子の「欲張り」とは、マッチを満たすために、常に、必要な最低量を超えて対象テキストを飲み込む(少なくともそうしようとする)という意味である。 4.2.4.3 早いもの勝ち 練習問題 "^.*([0-9]+)"を"Copyright 2003."に適用した場合に何がキャプチャされるか。 これはなるべく最初のマッチが優先され、量指定子は"かなり"欲張りなので、3しか"[0-9]+"に渡されないことになる。 これは間違う。 4.3 正規表現制御型とテキスト制御型 「NFA」というのは「非決定性オー
スクレイピングはもっと簡単にならなければいけない - bits and bytes
スクレイピングをやったことがあるひとならばわかると思うけど、スクレイピングはとてもつまらない作業だ。 HTMLの中から抜き出したい部分を見つけて、その周辺にある特徴的な部分に着目して正規表現を書いたりして抜き出す。あるいはHTMLからDOMを生成して特定のクラスがついているエレメントを抜き出したりする。HTMLをXHTMLに整形、変換してXPathで抜き出す方法もある。どの方法もやることは単純で簡単なことだけれど、極めてめんどくさい。 そういうものだと思って数年間過ごしてきたけれど、去年の夏に出てきた Dapper: The Data Mapper は、そんな退屈な常識をモダーンなajaxでもって吹き飛ばした。もしDapperがどんなのなのか知らなかったら、ちょっと長くてはじめ退屈なんだけど デモムービー を見てみてください。 Dapperが教えてくれたことは、スクレイピングなんて、欲し
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Does the ring of regular expressions exist?
