RegEx引擎如何工作

Question

在學習正則表達式時，它讓我想知道底層引擎是如何工作的。也許更具體一點，我想知道更多關於它如何評估，優先考慮和解析表達。我覺得RegEx引擎對我來說是一個黑盒子，我真的很喜歡破譯它。

所以我想問一下是否有一些很好的資源，我可以在上面討論RegEx引擎理論。

*注意：我對構建引擎不感興趣，只是瞭解它的內部工作原理。

Answer 1

有兩個主要類的正則表達式引擎。

1. 那些基於有限狀態自動。這些通常是最快的。他們通過構建state machine並從輸入字符串中提供字符來工作。即使不是不可能，在這樣的引擎中實現一些更高級的功能也是困難的。基於FSA引擎

   實例：

   • Posix/GNU ERE/BRE —用於大多數UNIX實用程序，如grep的，sed和AWK。
   • Re2 —一個相對較新的項目，旨在爲基於自動機的方法提供更多的權力。
      

2. 那些基於回溯。這些經常將模式編譯成字節碼，類似於機器指令。然後引擎執行代碼，從指令跳轉到指令。當一條指令失敗時，它會回溯尋找另一種匹配輸入的方式。回溯基於發動機

   例子：

   • Perl —原。這種類型的大多數其他引擎都試圖在Perl語言中複製正則表達式的功能。
   • PCRE —最成功的實施。這個庫是使用最廣泛的實現。它具有豐富的功能，其中一些功能不再被視爲"Regular"。
   • Python,Ruby,Java,.NET —其他實現我不打算進一步描述。

欲瞭解更多信息：

• regular-expressions.info - Tutorial
• regular-expressions.info - Flavor comparison
• swtch.com - Implementing Regular Expressions —一套好的約有效，基於自動機，正則表達式的文章。

如果您希望我在某些方面有所擴展，請發表評論。