什麼導致回溯

要查詢匹配項,正規表示式引擎將逐個使用字元。當部分匹配開始時,引擎將記住起始位置,以便在以下字元未完成匹配的情況下返回。

  • 如果匹配完成,則沒有回溯
  • 如果匹配未完成,引擎將回溯該字串(就像回放舊磁帶時)以嘗試查詢整個匹配項。

例如:\d{3}[a-z]{2} 對字串 abc123def 將被瀏覽:

abc123def
^ Does not match \d
abc123def
 ^ Does not match \d
abc123def
  ^ Does not match \d
abc123def
   ^ Does match \d (first one)
abc123def
    ^ Does match \d (second one)
abc123def
     ^ Does match \d (third one)
abc123def
      ^ Does match [a-z] (first one)
abc123def
       ^ Does match [a-z] (second one)
           MATCH FOUND

現在讓我們用相同的字串(abc123def)將正規表示式更改為\d{2}[a-z]{2}

abc123def
^ Does not match \d
abc123def
 ^ Does not match \d
abc123def
  ^ Does not match \d
abc123def
   ^ Does match \d (first one)
abc123def
    ^ Does match \d (second one)
abc123def
     ^ Does not match [a-z]
abc123def
    ^ BACKTRACK to catch \d{2} => (23)
abc123def
      ^ Does match [a-z] (first one)
abc123def
       ^ Does match [a-z] (second one)
           MATCH FOUND