正規表現エンジンを作ろう （2）〜NFAとDFAを実装する〜：CodeZine
はじめに こんにちは。hirataraです。 本稿は、正規表現エンジン作成の第2回目です。前回は正規表現の数学的な側面を説明しました。今回は正規表現エンジンの実際の評価器となる、NFAとDFAを実装します。 対象読者 正規表現をもっと知りたい方 情報科学分野に興味がある方 正規表現エンジンを実装する必要がある方 必要な環境 サンプルはPython2.5で開発しましたが、2.4の環境でも動くはずです。 Python2.5 が動作する環境 実装する正規表現の仕様 今回から正規表現エンジンの実装に入りますが、実際に手を動かし始める前に、到達すべきゴールを明確にしておきましょう。まず、連載中に実装する正規表現の仕様を決定します。この連載では数学的な定義である3つの正規表現のみを実装し、正規表現が本当にDFAと等価であり、DFAをシミュレートすることで実装できることを確かめます。 文法 これから作る
正規表現エンジンを作ろう （1）
はじめに こんにちは。hirataraです。 私が初めて正規表現を使ったのは、PerlによるCGIでの文字列処理でした。それから私はPerlを使い続け、今では正規表現なしのコーディングは考えられないほど、正規表現を当たり前の機能として日常的に使っています。昔は標準では正規表現をサポートしていなかったJavaも、今では正規表現をサポートするようになりました。Javaだけではなく、今日ではほとんどの高級言語にとって、正規表現はなくてはならない機能であると言っても過言ではないほどメジャーな機能となっています。 本記事では、この正規表現の舞台裏に光を当てます。一見すると作ることが難しそうな正規表現エンジンですが、その根底には数学的な概念があり、その概念さえ知っていれば基礎となる機能の実装はそんなに難しくありません。この連載ではその数学的な概念をPythonを使って表現しながら、実際に動作する正規表
正規表現はお好き? - steps to phantasien
積んであった Beautiful Code を読んでみる. 第一章はカーニハンによる正規表現の話. 数十行のコードで簡単な正規表現を実装してみせる. パターン文字列を内部表現に変換せずマッチに使うぜ, コードも短い, ビューティホー! ...という主張なのだが, それはほんとにビューティホーなのか. UNIX 人の感覚にはついていけない. それにしても彼らは正規表現が好きだ. いつものその話ばかりしている. artu はいうまでもなく プログラミング作法 にも正規表現が出てきた. まったくこのマンネリめ. そう斜に構えつつ読み直してみると, 案外ラディカルな話も載っているのに気付く. 9.7 "オンザフライコンパイル" より: Ken Thompson はまさにこの方法によって 1967 年に IBM7094 上に正規表現を実装した. 彼のバージョンは, 正規表現に含まれる様々な処理を小さ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
正規表現エンジンを作ろう一覧
