正規表現は、特に文字列操作が中心となるWEB分野におけるプログラミングにおいて、なくてはならない重要な機能です。本稿では正規表現を解釈するエンジンを実際に実装し、正規表現エンジンがどのように動いているのかを解説します。第3回は、実装するDFAエンジンが扱う文法を解釈するコンパイラを作成します。 はじめに こんにちは。hirataraです。 前回はDFAエンジンの仕様を明らかにし、DFAとNFAをPythonで実装しました。今回は、実装するDFAエンジンが扱う文法を解釈するコンパイラを作成します。 対象読者 正規表現をもっと知りたい方 情報科学分野に興味がある方 正規表現エンジンを実装する必要がある方 正規表現のコンパイル 前回、正規表現の仕様の中で正規表現の文法を定めました。これから、この文法を解釈できるコンパイラを作成します。コンパイラの仕事は、文字列を解釈して計算機が扱いやすいデータ方
はじめに こんにちは。hirataraです。 前回までの連載で、正規表現からNFAを構築する部分までを作成しました。今回は、NFAをDFAに変換する部分集合構成法を解説し、今まで作った部品を組み合わせて正規表現エンジンを完成させます。 対象読者 正規表現をもっと知りたい方 情報科学分野に興味がある方 正規表現エンジンを実装する必要がある方 部分集合構成法 NFAをDFAに変換するには、部分集合構成法（subset construction）と呼ばれる方法を利用します。 第1回で説明した通り、NFAは1つの文字の入力によって一意に状態が決まらないのが特徴でした。'a'を入力すると、1になるかもしれないし、2になるかもしれません。そして、NFAのシミュレート方法には、バックトラックを利用する深さ優先の方法と、もう一つ、幅優先の方法があることも紹介しました。幅優先の動作では、入力による遷移の全て
はじめに こんにちは。hirataraです。 私が初めて正規表現を使ったのは、PerlによるCGIでの文字列処理でした。それから私はPerlを使い続け、今では正規表現なしのコーディングは考えられないほど、正規表現を当たり前の機能として日常的に使っています。昔は標準では正規表現をサポートしていなかったJavaも、今では正規表現をサポートするようになりました。Javaだけではなく、今日ではほとんどの高級言語にとって、正規表現はなくてはならない機能であると言っても過言ではないほどメジャーな機能となっています。 本記事では、この正規表現の舞台裏に光を当てます。一見すると作ることが難しそうな正規表現エンジンですが、その根底には数学的な概念があり、その概念さえ知っていれば基礎となる機能の実装はそんなに難しくありません。この連載ではその数学的な概念をPythonを使って表現しながら、実際に動作する正規表
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く