1樓：Belleve
在 PEG 文法裡 ，用後者展開即可得到以下的模式// Matcher(a) 是乙個函式，接入三個引數：匹配狀態 s，成功續體 success 和失敗續體 failure
// 在任意狀態 s 下匹配空模式 ε 總是成功，故可以直接用封裝的 success(s)
function
Directly
(success,s
)}function
KleeneStar(a
),Directly
(success,s
))// 否則，在 s 處直接匹配成功
}returnf}
2樓：luikore
和深度優先搜尋比較像
例如 (a|b)(c|d) 搜尋匹配 "bd" 的順序是:aacadb
bcbd
如果正則支援原子組, 搜尋順序就不太一樣
例如 (?>a|b)(c|d) 搜尋匹配 "bd" 的順序是:abbcbd
就和廣度優先搜尋有點像了
3樓：Htedsv
正規表示式 -> NFA -> DFA
DFA識別字串不需要回溯。DFA識別的過程用迴圈就行了。所以所謂的回溯問題是你程式的邏輯可能有問題，好好檢查下程式吧。
如果你希望匹配出所有符合條件的字串，一種是就像普通字串匹配一樣，匹配失敗後，回到你開始匹配第乙個字元的地方。
如果你希望效率更高一點，就用KMP，給DFA的每個狀態記錄匹配失敗後的next函式，轉移到另乙個狀態。這樣就可以完全杜絕回溯，總時間複雜度就是O(m+n)了。
不過你要考慮二義性的問題，即你希望a*可以從aaaaa中匹配出幾個模式。
你是如何學會正規表示式的？
一絲混亂 大部分知識和技能的都符合二八定律 20 知識點的使用頻率是80 80 知識點的使用頻率是20 但是這些東西的教程或者說明是一股腦兒全部給你的，並沒有著重標出哪些是重點，哪些用的頻率不那麼高。正則就是乙個非常典型的例子，我覺得正則說是9.5 0.5都不為過。我使用過程中，用到最多的是i g ...
用 d 正規表示式匹配 abcd 為什麼得到的是 abcd 而不是 d
Coincidence 的匹配過程 a匹配了乙個a，但是a後面是b不是d，不匹配，回溯，繼續匹配ab匹配了ab,但是ab後面不是d，不匹配，回溯，繼續abc 匹配了abc，後面是d，匹配結束。abcd 最終結果 我的分析這是簡要分析，貼張regexbuddy的匹配全過程圖 a 匹配過程 a a匹配a...
正規表示式是圖靈完備的嗎？
理論上說，正規表示式就是符合Chomsky層級中type3文法的字串，那麼肯定是不完備的，至少連 1 n 2 n 這樣的字串都無法描述。但是實際的正規表示式引擎實現中，有時為了增強匹配字串的能力，會讓該引擎的語法達到type2乃至type0。比如Perl6的正規表示式可以完全匹配CFG type2 ...