計算正則表達式的效率

你將如何計算/查找正則表達式匹配給定字符串的操作數？我想開發一個程序，讓您按照效率排列正則表達式。計算正則表達式的效率

此外，如果操作次數超過給定閾值，是否有可能突破正則表達式？我希望將它變成一個Web應用程序，所以我不希望用戶輸入可能會導致服務器死機的正則表達式（如果甚至可能的話）。

非常感謝。

編輯：爲了澄清，我指的是包括回溯（因此是非線性）的普通正則表達式的超集。

2011-07-27 Chris

正則表達式處理的性能取決於它所實現的語言，以及有關如何實際執行的無數細節。即使你爲它編寫一個Web應用程序，它也只會測試Web服務器正在使用的正則表達式實現。這對於數百個其他正則表達式實現沒有任何意義。 –

根據正則表達式的不同，程序的其他部分可能會佔用時間，比如在使用String＃scan時創建字符串結果。 –

操作次數也取決於輸入字符串。您無法計算操作次數，但可以計算其他正則表達式對相同字符串執行匹配所花費的時間差異。

2011-07-27 02:07:03

找出解析給定字符串需要多少操作的方法是解析它並計算操作數。你可以做一些有限的靜態分析，但是一個明確的答案就等於解決了暫停問題。

嘗試對任何輸入的表達式排序更加複雜。採取表達式A[0-9]+

正則表達式解析器基本上只是一個程序。幾乎總是不可能說一個程序總體上比另一個程序更快，只能用於特定的輸入。

您可以嘗試基於對輸入內容的一些理解來使用靜態分析。例如，可以立即消除大部分常用輸入的表達式可能比不支持的表達式快。我會說唯一的方法就是接受一個表達式的數據集，這個表達式與被解析的表達式類似，並且使用這些數據做基準測試[簡單]或者分析[硬]。

2011-07-27 03:43:12

回答