正規表現のパーサーを書く

質問

何年ものプログラミングの後でも、恥ずかしながら、私は正規表現を完全に理解したことがありません。一般に、問題が正規表現を必要とする場合、私は通常 (構文を何度も参照した後で) 適切なものを考え出すことができますが、これは私がますます頻繁に使用しているテクニックであることがわかります。

というわけで、正規表現を学び、理解するために を適切に すなわち、十分に学んだと感じたらすぐに放棄するような、野心的なものを書いてみることにしました。

この目的のために、私はPythonで正規表現パーサーを書きたいと思います。この場合、「十分に学ぶ」とは、Perl の拡張正規表現構文を完全に理解することができるパーサーを実装したいことを意味します。しかし、最も効率的なパーサーである必要はありませんし、実世界で使えるものである必要もありません。単に、文字列内のパターンに正しくマッチするか、マッチしないかだけでよいのです。

問題は、どこから始めればよいかということです。私は、何らかの方法で有限状態オートマトンを含むという事実を除けば、正規表現がどのように解析され解釈されるかについてほとんど何も知りません。このかなり困難な問題にアプローチする方法についての提案は非常にありがたいものです。

EDIT。 を明確にする必要がありますが、私が行っているのは インプリメント を実装するつもりですが、例や記事がどのようなプログラミング言語で書かれているかについてはあまり気にしていません。それが Brainfuck でない限り、私はおそらく、私の時間を価値あるものにするためにそれの十分に理解することができます。

どのように解決するのですか？

正規表現エンジンの実装を書くことは、実に複雑な作業です。

しかし、実際に実装するほど細部を理解できなくても、その方法に興味があるのであれば、少なくともこの記事を見ておくことをお勧めします。

正規表現マッチングはシンプルで高速にできる (ただし、Java, Perl, PHP, Python, Ruby, ...では遅い)

この記事では、一般的なプログラミング言語の多くが、いくつかの正規表現に対して非常に遅い方法で正規表現を実装していることを説明し、より速い少し異なる方法について説明しています。提案されている実装がどのように動作するのか、C言語のソースコードも含めて詳しく書かれています。正規表現を学び始めたばかりの方には少し重い読み物かもしれませんが、2つのアプローチの違いについて知っておく価値は十分にあると思います。