perl，python，java和vim等使用正則表達式進行解析的基本方法是什么？不聰明的形式語言方法（即NFA，DFA）; 解析器組合器（例如14行正則表達式引擎）也是如此。我看過Java實現perl樣式正則表達式的源代碼，但是其復雜的功能（例如，反向引用）和效率（例如，Boyer-Moore子字符串匹配）使得很難看到它的基本工作原理。編輯 各種消息來源說，“回溯”參與（如正則表達式匹配可以是簡單，快速;形式化方法的課程），但不清除到底是什么回溯上...它來評估的方式NFA？可以直接從正則表達式的AST完成嗎？java / perl / python正則表達式引擎實際上是做什么的？是否是這樣的：“一種以常規語言生成所有可能單詞的方法，但是一旦它與輸入字符串不匹配，就放棄特定單詞”。
3 回答
翻閱古今
TA貢獻1780條經驗 獲得超5個贊
正則表達式引擎中有兩種通用方法。
正則表達式可以轉換為有限自動機。這種關系在計算機科學中得到了很好的研究。這些有限的自動化然后可以有效地執行，甚至向后運行。它們提供了有力的保證，例如在線性時間和關于輸入字符串的恒定空間中運行，但是從正則表達式創建有限自動機可能會很昂貴。這種方法還將引擎限制為真正的正則表達式，即排除了諸如反向引用或遞歸之類的高級功能。
正則表達式可以由回溯引擎解釋。如果模式中的替代方法失敗，則可以追溯到最后一個決策點，然后嘗試其他方法。這是非常靈活的，并且（具有遞歸+命名子模式等額外功能）可以解析更大類的形式語言（形式上是LL（*）語法集）。這與PEG解析器非常相似。最大的缺點：由于回溯，運行regex會花費成倍的時間-即使沒有任何其他高級功能。
最重要的是，正則表達式引擎具有額外的優化功能，例如首先在模式中搜索常量子字符串，因為它比運行任何類型的正則表達式（任何人甚至都可以使用矢量化CPU指令）更高效。如果在多個常量字符串之間有一個選擇點，則可以很容易地將它們編譯成trie數據結構（實際上是一個簡單的有限自動機）。這樣可以減少回溯的數量。
a*a*a*a*a*b字符串上的模式是證明有限自動機和回溯的區別的正則表達式aaaaaaaaaaaaaaacb。有限的自動機可以很容易地看到，由于c輸入中的原因，該模式將不匹配。但是，回溯引擎現在具有許多決策點，可以在其中為每個a*子模式嘗試不同的長度。re在這種情況下，像Perl或Python中的模塊之類的Regex引擎呈指數級，即完成時間很長–a向輸入中添加更多s會使其花費更長的時間。如果不受信任的用戶可以提供任意正則表達式，則可以進行有趣的拒絕服務攻擊。對于不受信任的輸入，僅應使用基于有限自動機的正則表達式引擎，例如Google的RE2。
添加回答
舉報
0/150
提交
取消