如何編寫代碼來識別正則表達式是否匹配給定的字符串？

Question

給出兩個字符串作爲參數，一個是正則表達式字符串，另一個是文本。如何編寫一個函數來識別給定的正則表達式是否匹配文本而不使用任何內部庫或模塊？

Answer 1

希望這個問題只是爲了教育目的，因爲它是相當寫代碼，做正則表達式匹配的任務。

基本上有兩種方法：

1）一種正則表達式可被轉換成可很容易地用於找到任何串內匹配確定性有限自動機（DFA）。參見（https://en.wikipedia.org/wiki/Deterministic_finite_automaton）。

該方法包括第一轉換到非確定性有限自動機（NFA - https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton）使用Thompson的施工（https://en.wikipedia.org/wiki/Thompson%27s_construction），則轉換該對一個DFA使用子集構造（https://en.wikipedia.org/wiki/Powerset_construction），然後用Hopcroft算法最小化DFA或類似的文件（https://en.wikipedia.org/wiki/DFA_minimization）

這種方法的優點是生成的匹配器速度非常快，無論原始正則表達式有多複雜。它有一些缺點，包括無法處理反向引用。

編譯器使用這種技術來標記解析程序。我有一個開源的庫，它可以在Java中執行此操作：http://mtimmerm.github.io/dfalex/

2）另一種方法，通常稱爲「回溯」方法，將正則表達式轉換爲可能性樹。當你將一個字符串與這棵樹相匹配時，它會首先嚐試第一種可能性，然後如果失敗了，它會返回並嘗試針對字符串的同一部分的下一個可能性。這很容易實現，但並不是特別快。

在某些情況下，匹配字符串可能需要很長時間。例如，請參閱http://www.regular-expressions.info/catastrophic.html

儘管如此，這是在大多數語言提供的庫（包括Java，C＃，Perl等）中完成的方式。與標準實現最接近的是PCRE或「Perl兼容的正則表達式「：http://www.pcre.org/

3）...還有很多不常用的方法。有些軟件包就像（1），但可以動態執行子集構建，只需構建所需的狀態。一些直接執行NFA（https://swtch.com/~rsc/regexp/regexp1.html）。有些像（2），但一次嘗試多個分支。這兩種方法都避免了災難性的情況。 GLR解析（https://en.wikipedia.org/wiki/GLR_parser）等一些解析技術也可用於實現總是以合理方式執行的相當快的正則表達式引擎。