C/C++中的正則表達式庫

Question

我想在C/C++中編寫正則表達式庫。 什麼是好的起點，任何書籍或文章。

我知道有可能庫，但我想寫我自己的版本。

Answer 1

一個好的起點是使用現有的實現並批評它們。

注意您不喜歡的數據結構和設計決策。
當你寫你的版本時避免它們。

Answer 2

我不知道一本書能幫助你實現細節 - 我確信有很多細節可以使它高效。然而，Thomas A. Sudkamp撰寫的「語言與機器」一書將有助於理解實施背後的想法。

我認爲你需要做的是將正則表達式編譯成有窮自動機。如果你對語法和自動機不太瞭解，那麼該書的第二部分「語法，自動機和語言」將非常有幫助。

這本書編譯器，原理，技巧，&工具;阿爾弗雷德阿霍，莫妮卡林，拉維塞西和傑弗裏烏爾曼（也被稱爲龍書）也可能有所幫助。它的目標是爲計算機語言編寫一個編譯器，而不是用於正則表達式語言。但是，您可能會發現它很有用，特別是關於解析的部分，因爲它具有更多的實用性質（與語言和機器非常相似）。

無論如何，如果我要寫一個正則表達式語言，那將是我的出發點。我建議你從你有權訪問的圖書館借閱。除此之外，你應該看看工作實現。我只是在這裏猜測，但我認爲可能會有關於Perl正則表達式實現的很好的文檔。看到他們如此受歡迎，工作如此出色。

祝你好運。

Answer 3

[編輯16-Jan-2015]我最近遇到這本美麗的書Beautiful Code。我建議你閱讀Brian Kernighan的第1章「正則表達式匹配器」。

您可以閱讀肯·湯普森的經典論文「正則表達式搜索算法」... http://portal.acm.org/citation.cfm?doid=363347.363387 ...本文應該讓您很好地理解如何使用有限自動機匹配正則表達式。

這是拉斯考克斯提供了一些詳細的資料另一頁... http://swtch.com/~rsc/regexp/

希望這些幫助您開始。