如何簡化這個正則表達式以避免遞歸？

Question

正則表達式：

(?|`(?>[^`\\]|\\.|``)*`|'(?>[^'\\]|\\.|'')*'|"(?>[^"\\]|\\.|"")*"|(\?{1,2})|(:{1,2})([a-zA-Z_\x7f-\xff][a-zA-Z0-9_\x7f-\xff]*)) 

示例輸入：

INSERT INTO xyz WHERE 
a=? 
and b="what?" 
and ??="cheese" 
and `col?`='OK' 
and ::col='another' 
and last!=:least 

https://regex101.com/r/HnTVXx/6

應該匹配?，??，:xyz和::xyz但如果它們是反引號串，雙內帶引號的字符串或單引號字符串。

當我嘗試在PHP中以非常大的輸入運行此操作時，我從preg_last_error()得到PREG_RECURSION_LIMIT_ERROR。

我怎樣才能簡化這個正則表達式模式，使它不會做這麼多的遞歸？

---

下面是一些測試代碼顯示使用Niet's optimized regex在PHP錯誤：https://3v4l.org/GdtmP錯誤代碼6 PREG_JIT_STACKLIMIT_ERROR。另一位我所看到的是3 = PREG_RECURSION_LIMIT_ERROR

Answer 1

同樣的想法跳過QUOT ED部分（(*SKIP)(*F)組合），而且還2項技術，以減少正則表達式引擎的工作：

• 的第一個字符識別
• 展開的模式

這兩個技術有一個共同點：限制改變的代價。

當您的圖案以變化開始時，第一個字符歧視很有用。開始時的交替問題是每個分支都要進行測試，以確定模式失敗的位置。由於大多數時候，一個字符串中有很多失敗的位置，很快拋棄它們是一個顯着的改進。

舉例來說，像這樣："...|'...|`...|:...也可以寫成這樣：

(?=["'`:])(?:"...|'...|`...|:...) 

或

["'`:](?:(?<=")...|(?<=')...|(?<=`)...|(?<=:)...) 

這樣，每個不使用這些字符開始位置["'`:]是立即拒絕第一個標記而不測試每個分支。

---

鋪開模式由改寫這樣的：" (?:[^"\\]|\\.)* "到：

" [^"\\]* (?: \\. [^"\\]*)* " 

注意，這樣的設計消除了交替和減少步數急劇：
basic
unrolled

---

使用這兩種技巧，您的模式可以被寫入ñ這樣的：

~ 
[`'"?:] 
(?: 
    (?<=`) [^`\\]*+ (?s:\\.[^`\\]*|``[^`\\]*)*+ ` (*SKIP) (*F) 
    | 
    (?<=') [^'\\]*+ (?s:\\.[^'\\]*|''[^'\\]*)*+ ' (*SKIP) (*F) 
    | 
    (?<=") [^"\\]*+ (?s:\\.[^"\\]*|""[^"\\]*)*+ " (*SKIP) (*F) 
    | 
    (?<=\?) \?? 
    | 
    (?<=:) :? ([a-zA-Z_\x7f-\xff][a-zA-Z0-9_\x7f-\xff]*) 
) 
~x 

demo

---

其他方式：不是在一開始使用的交替（改善或沒有），您可以構建所有連續的結果字符串相匹配的模式。一般設計是：

\G (all I don't want) (*SKIP) \K (what I am looking for) 

\G是，無論是先前的結果後的位置或字符串的開頭相匹配的錨。用它開始模式可確保所有匹配都是連續的。在這種情況下（在模式的開始和整個模式的因素中），您也可以用A修飾符替換它。

這給：

~ 
[^`'"?:]* 
(?: 
    ` [^`\\]*+ (?s:\\.[^`\\]*|``[^`\\]*)*+ ` [^`'"?:]* 
    | 
    ' [^'\\]*+ (?s:\\.[^'\\]*|''[^'\\]*)*+ ' [^`'"?:]* 
    | 
    " [^"\\]*+ (?s:\\.[^"\\]*|""[^"\\]*)*+ " [^`'"?:]* 
)* 
\K # only the part of the match after this position is returned 
(*SKIP) # if the next subpattern fails, the contiguity is broken at this position 
(?: 
    \?{1,2} 
    | 
    :{1,2} ([a-zA-Z_\x7f-\xff][a-zA-Z0-9_\x7f-\xff]*) 
) 
~Ax 

demo

Answer 2

的「匹配這個東西，但不是在這種情況下」可以用這種模式實現的總體思路：

(don't match this(*SKIP)(*FAIL)|match this) 

在你的情況，你想要的東西像...

(
    (['"`]) # capture this quote character 
    (?:\\.|(?!\1).)*+ # any escaped character, or 
        # any character that isn't the captured one 
    \1  # the captured quote again 
    (*SKIP)(*FAIL) # ignore this 
    | 
    \?\?? # one or two question marks 
    | 
    ::?\w+ # word characters marked with one or two colons 
)x 

https://regex101.com/r/HnTVXx/7