如何從零寫一個正則表達式引擎？

12-10

是的, 首先要確定實現的目標, 有幾個關鍵目標是會影響你的實現的

- 要不要支持完整的正則文法? (如果不支持 "|", 幾十行就能搞定, 如果要支持完整的正則文法, 就需要一個能力超越正則的解析器, 如果要編寫一個高效的 one-pass 正則編譯器, 還是要學不少編譯技術的...)

- 要不要支持 unicode 及 unicode character class? (掃描 UTF-8/16 碼點會比較蛋疼, 容易一點的做法是轉換成 UTF-32 做), 要對 unicode 做完整支持的話, 很多傳統正則引擎里基於位元組的匹配方式就不能做了, 一些 DFA 節點的表示方式和壓縮手段也會受限制.

- 要不要支持 back reference? (如果你要實現 back reference 的話, 你不能用 Implementing Regular Expressions 里描述的 ThompsonVM/PikeVM 的, thread list 佔有的內存會隨著狀態數指數增長而爆裂) 支持 back reference 的正則基本很多會退回去擴展最原始那個 Henry Spencer VM...

- 要做成 NFA based, DFA based, 還是一個位元組碼虛擬機? 對虛擬機的解決方案, 你要學習位元組碼解釋器的基本構造, 可能會用 direct threading 等技術去做優化. 位元組碼可以看作線性化的 NFA, 相比構造 NFA 節點會減少一些 cache miss 但是相應的就不能使用很多節點壓縮和優化的手段了.

- 要不要做一個 JIT 引擎? 這個更令人興奮, 可以參考 ytljit/regexp.rb at master · miura1729/ytljit · GitHub)

- 要不要兼容 POSIX 標準里的正則部分? (估摸至少 4000 行代碼, 自己考慮工作量咯)

- 要不要做 extended 正則?

所謂 extended 正則, 就是還支持補集和交集運算, 正則語言這麼搞完結果還是個正則語言, 就是實現 grep -v 之類的可以簡單一些, 可以嘗試這個方法

- 要不要做 Online Parsing?

online parsing 常用於語法高亮和大文件解析中. 其意思是輸入一部分內容就匹配一部分, 有新內容輸入的時候你不該重頭匹配一遍 (每敲一個字元重新著色一遍太慢了), 而是做最低限度的回溯. 如果要做 online parsing, 那麼怎麼暫停你的 VM, 怎麼緩存回溯都是要考慮的問題. 而且正則的語法會有限制.

- 要不要支持超巨大的正則表達式?

有些 network filter 例如聯邦的防火牆, 會有幾十萬條規則, 你會發現普通的辦法在 20G 內存的機器上都編譯不了這個正則... 不過用小內存支持 DFA 千萬節點的方法已經有人研究出來了: D^2FA... 為了編譯出這麼大的 D^2FA, 其編譯期演算法也有人研究過了: D^2FA

- 要不要支持以下各種正則引擎的 fancy feature?

-- X 匹配字素
-- 遞歸 named group
-- capture history
-- nested capture
-- atomic group
-- greedy vs reluctant vs possessive
...

每一項都相當有難度... 尤其是 greedy/reluctant/possessive 的區別有可能從根本上顛覆你這個正則引擎的實現, 很多人的正則引擎做完 DFA/NFA 就停下來了, 也是因為搞不動這些 feature.

---

OK, 目標明確了, 開始代碼之前要先夾溝夾溝哦, 建議: 不要一開始就想把它做得很高效率, 要把問題拆得足夠小足夠簡單的來做, 只要決定好大方向不錯, 就不用推倒重來很多次了...

現在的正則引擎的構造比各種 parser generator 都要複雜, good luck!

推薦書籍: Parsing Techniques - A Practical Guide 2008 (講得比較全了, 就是缺少 coroutine based parser 的構建)

推薦課程: Parsing Beyond Context-Free Grammars (為什麼要 beyond CFG 呢? 因為現在正則引擎的能力已經 beyond CFG 啦)

推薦代碼: Henry Spencer"s regexp engine regexp.old/regexp.c at master · garyhouston/regexp.old · GitHub 是很多現代流行的正則引擎的始祖, 解釋器實現, 很多新 feature 能擴展得得進去, 也有混合 DFA 的優化

Onigmo k-takata/Onigmo · GitHub 是 Ruby 的正則引擎, 特點是 encoding aware 兼容多種語法和 feature, 如果要做 unicode character class 可以抄它的...

https://gist.github.com/timshen91/f6a3f040e5b5b0685b2a

寫了個80行的C++模板版。注意啊，regex的定義包括了concatenation，alternation（「|」），Kleene closure（「*」），還得有一個ε字元（可近似認為「?」），expression還要能嵌套（「(」「)」）。有些例子里缺了alternation和嵌套那就不該叫regex了。

之所以這麼短是因為壓根沒有parsing，parsing多無聊啊。直接構造regex的AST，根本不去打NFA的主意。想加什麼功能就直接加type就行了。

這個是compile time regex，所以跑起來是raw speed，很快。你要是要運行時的regex，把那幾個模板特化改為一個樹狀variant結構，在樹上走就行了，演算法（包括那個continuation的trick）都是一樣的。

建NFA那套做法是Ken Thompson推出來的「標準」演算法，但是就玩玩而已應該從更簡單的學起。學一下CPS變換又不會死。

另外把程序寫短小緊湊的訣竅就是寫成FP style。我的80行中所有函數都只有一個return語句。

https://gist.github.com/picasso250/0efc287080664f43eb93

好吧，我將 @Tim Shen 的C++的版本改成了JS版本。

偏特化用類實現，模板匹配用switch+instanceof 語句實現，字元串結尾判斷用s[i] === undefined 實現

因為不到40行，就把代碼直接放上來吧

// from c++ version: https://gist.github.com/timshen91/f6a3f040e5b5b0685b2a // author: wangxiaochi


function ConcatExpr (Left,Right) {this.Left = Left;this.Right=Right} // ab

function AltExpr(Left,Right) {this.Left = Left;this.Right=Right} // a|b

function RepeatExpr(SubExpr) {this.SubExpr= SubExpr;} // a*

function OptionalExpr(SubExpr) {this.SubExpr= SubExpr;} // a?

function MatchExpr(ch) {

  this.ch= ch

}
MatchImplApply = function (expr, target, i, cont) {

  switch (true) {

  case expr instanceof ConcatExpr:

    return MatchImplApply(expr.Left, target, i, (rest,ri) =&>

      MatchImplApply(expr.Right, rest, ri, cont))

  case expr instanceof AltExpr:

    return (MatchImplApply(expr.Left, target, i, cont) ||

        MatchImplApply(expr.Right, target, i, cont))

  case expr instanceof RepeatExpr:

    return MatchImplApply(expr.SubExpr, target, i, (rest,ri) =&>

            (MatchImplApply(expr, rest, ri, cont) || cont(rest,ri))

          ) || cont(target, i)

  case expr instanceof OptionalExpr:

    return MatchImplApply(expr.SubExpr, target, i, cont) || cont(target, i)

  case expr instanceof MatchExpr:

    return target[i] !== undefined  target[i] == expr.ch  cont(target, i+1) // end of string, match a char

  default:

    throw "no expression type"

  }

}
RegexMatch = (RegExpr,target) =&> // all match

  MatchImplApply(RegExpr, target,0, (rest,i) =&> rest[i] === undefined)

RegexSearch = (RegExpr,target,i) =&> // partial match from begining

  MatchImplApply(RegExpr, target,i, (rest,i) =&> true) ||

    (target[i] !== undefined  RegexSearch(RegExpr, target, i+1))

console.assert(RegexMatch(new ConcatExpr(new MatchExpr("a"), new MatchExpr("b")), "ab")); console.assert(RegexMatch(new AltExpr(new MatchExpr("a"), new MatchExpr("b")), "a")); console.assert(RegexMatch(new AltExpr(new MatchExpr("a"), new MatchExpr("b")), "b")); console.assert(RegexMatch(new RepeatExpr(new MatchExpr("a")), "aaaaa")); console.assert(RegexMatch(new ConcatExpr(new RepeatExpr(new MatchExpr("a")), new MatchExpr("b")), "aaaaab")); console.assert(RegexMatch(new ConcatExpr(new RepeatExpr(new MatchExpr("a")), new MatchExpr("b")), "b")); console.assert(RegexSearch(new ConcatExpr(new RepeatExpr(new MatchExpr("a")), new MatchExpr("b")), "aaaaabb", 0)); console.assert(RegexMatch(new OptionalExpr(new MatchExpr("a")), "a")); console.assert(RegexMatch(new OptionalExpr(new MatchExpr("a")), "")); console.assert(RegexMatch(new OptionalExpr(new ConcatExpr(new MatchExpr("a"), new MatchExpr("b"))), "ab")); console.assert(RegexMatch(new OptionalExpr(new ConcatExpr(new MatchExpr("a"), new MatchExpr("b"))), ""));

來來來誠心安利FP大法好，五行帶你寫regexp matcher(不要問我為啥要用SML咱學校就任性就只叫這個= =

fun match (Char(a)) cs k = (case cs of nil =&> false | (c::cs") =&> (a=c) andalso k(cs")) | match (One) cs k = k cs | match (Zero) _ _ = false | match (Times(r1,r2)) cs k = match r1 cs (fn cs" =&> match r2 cs" k) | match (Plus(r1,r2)) cs k = match r1 cs k orelse match r2 cs k | match (Star(r)) cs k = k cs orelse match r cs (fn cs" =&> not (cs = cs") andalso match (Star(r)) cs" k)

代碼的核心在於他保證了如下性質:
match r cs k returns true
iff
cs can be split as cs == p@s,
with p representing a string in L(r)
and k(s) evaluating to true.

這裡傳的cs和k就是傳說中的cps啦

知乎網頁版掛了= =...回頭加代碼高亮

Implementing Regular Expressions by Russ Cox

咋都寫的是matcher？考慮過parser的感受嗎？

簡單寫了個Swift版本的Parser，支持() ，| , + , ? , * 以及各種嵌套，parse的結果就是AST。

有了AST，才能用前面的菊苣們寫的matcher呀！

依賴：基於我自己寫的一個Swift版的簡化Parsec ： SwiftyRegex/Parser.swift at master · aaaron7/SwiftyRegex · GitHub，這裡定義了最基本的Combinator。

let reserved = "+?()|*"


indirect enum Regex{

    case Char(Character)

    case Concat(Regex,Regex)

    case Alter(Regex,Regex)

    case ZeroOrOne(Regex)

    case ZeroOrMore(Regex)

    case OneOrMore(Regex)

}
func notReserved(c : Character) -&> Bool{

    return reserved.characters.indexOf(c) == nil

}
func rchar()-&>Parser&{

    return satisfy(notReserved) &>&>= { c in

        pure(.Char(c))

    }

}
func regop(c : Character) -&> (Regex-&>Regex)?{

    if c == "?"{

        return { reg in

            .ZeroOrOne(reg)

        }

    }else if c == "*"{

        return { reg in

            .ZeroOrMore(reg)

        }

    }else if c == "+"{

        return { reg in

            .OneOrMore(reg)

        }

    }

    return nil

}
func rexp() -&> Parser&{

    return (rtrm() &>&>= {term in

        symbol("|") &>&>= { _ in

            rexp() &>&>= { exp in

                pure(.Alter(term,exp))

            }

        }

    }) +++ rtrm()

}
func ratm() -&> Parser&{

    return rchar() +++ (symbol("(") &>&>= { _ in

        rexp() &>&>= { reg in

            symbol(")") &>&>= { _ in

                pure(reg)

            }

        }

    })

}
func rfac() -&> Parser&{

    return (ratm() &>&>= {atm in

        satisfy({sc in sc == "*" || sc == "?" || sc == "+"}) &>&>= {c in

            pure(regop(c)!(atm))

        }

    })  +++ ratm()

}
func rtrm() -&> Parser&{

    return (rfac() &>&>= { reg1 in

        rtrm() &>&>= { reg2 in

            pure(.Concat(reg1,reg2))

        }

    }) +++ rfac()

}

let parserResult = rexp().p(reg) print(parserResult)

完整版Demo在這裡：GitHub - aaaron7/SwiftyRegex: 占坑， Matcher和大家一樣用的SML教材里的演算法，只是用Swift實現了一下。

http://www.cppblog.com/vczh/archive/2008/05/22/50763.html

我用求導大法(Derivative)寫了個小巧的來玩，簡單地支持 *, +, |, ?, {n,m}, (), [] 這幾種語法
核心代碼在
CodeSnippet/Derivative.hpp at master · Cheukyin/CodeSnippet · GitHub
CodeSnippet/Engine.hpp at master · Cheukyin/CodeSnippet · GitHub
測試用例見
CodeSnippet/EngineTest.cpp at master · Cheukyin/CodeSnippet · GitHub

基本思路參考論文《Parsing with Derivatives》前三節，
大致是從集合的角度來思考，每條正則代表一個符合某個規則的語言集合，
所有的正則語法可以規約成三種基本的集合運算：並，連接，重複，
然後定義集合的求導運算Derivative，正則匹配就是不斷對集合求導，細節看論文，
具體到代碼實現很好寫，定義好求導規則，讓程序自動遞歸便可，這樣便可以寫出一個小引擎。

最後便只需為引擎添加一個前端，將正則的各種花哨語法規約為那三種基本運算，
我隨便寫了個遞歸下降的parser，代碼在
CodeSnippet/Parser.cpp at master · Cheukyin/CodeSnippet · GitHub

當然這種寫法是比較低效的，因為各種胡亂遞歸，正統的估計還是得搞回NFA/DFA那套吧

首先確定要實現什麼樣的正則表達式

1. 經典正則表達式：這是我們在編譯原理課或者形式語言與自動機課上學到的那種正則表達式，即正規文法，也就是Chomsky體系中的3型文法。任何正則文法都可以構造等價的有限狀態自動機，也就是說我們可以構造一個有限狀態自動機來實現經典正則表達式的匹配。

2. 擴展的正則表達式：這個名字是我給起的，其實我更喜歡稱他們為黑魔法正則，也就是我們現在在Perl、Python、Java的標準庫中用到的正則表達式。相比經典正則，其表達能力更強，使用更方便，深受廣大人民群眾喜歡，參見Python文檔（7.2. re — Regular expression operations）。但此類正則表達式已經超越正則文法，特別是對backreference支持（帶backreference的正則表達式匹配其實是NP完全的）。

接下來，如何實現呢？

為了方便論述，假設文本的長度為n，正則表達式的長度為m

1. 實現經典正則表達式

經典NFA：就是搜索加回溯的方式，搜索到第一個match就退出。經典NFA的空間複雜度（即狀態數和轉移數）是O(m)，但匹配的時間複雜度最壞情況下是指數級的，即O(2^n)。
POSIX NFA: 和傳統NFA差不多，不同是只有找到最長的match才會退出，所以理論上會比經典NFA更慢。
Thompson NFA：上個世紀60年代，由Ken Thompson提出，空間複雜度仍然是O(m)，但匹配的時間複雜度可以降到O(nm), 演算法可以參考Regular Expression Matching: the Virtual Machine Approach。當然構造NFA的方法還有很多，比如Glushkov NFA，這裡不一一列舉了（好吧，實話是因為這樣我就要去問谷歌了）
DFA：NFA和DFA的表達能力有等價的，而且任何一個NFA都可以轉化為一個DFA。DFA匹配的時間複雜度是線性的，即O(n), 但因為對於某些複雜的正則表達式，會導致DFA的狀態爆炸，所以最壞情況下，轉化需要的空間複雜度和時間複雜度是O(2^m)。可見相比NFA，DFA算是用空間來換時間了。在工程上，有時也不得不放棄DFA，投奔NFA。

我建議經典正則還是值得自己實現一把的，尤其是Thompson NFA及其變種，可以自己做一些修改或精簡來支持自己特殊的需求。和 @陳碩大神一樣，推薦Implementing Regular Expressions系列。

2. 實現擴展正則表達式
實現複雜度取決於你願意支持多少黑魔法，但因為同樣基於回溯，時間複雜度和經典NFA一樣，逃脫不了指數級時間複雜度的魔咒。我不建議手擼此類正則表達式，用標準庫就行了。（好吧，實話是我也沒幹過）

我也來擼一個簡單的Racket的版本吧，只有14行哦（（（（括弧大法好））））

#lang racket


; &
 ::= &

;         | (&
 *)

;         | (&
 +)

;         | (&
 ?)

;         | (&
 or &
)
; reg-match : (listof pat) string integer -&> boolean

(define (reg-match pats str pos)

  (if (null? pats) (= pos (string-length str))

      (match (car pats)

        [(? string?) (let ([len (string-length (car pats))])

                       (and (&>= (string-length str) (+ pos len))

                            (substring=? (car pats) str pos (+ pos len))

                            (reg-match (cdr pats) str (+ pos len))))]

        [`(,p1 or ,p2) (or (reg-match `(,p1 ,@(cdr pats)) str pos)

                           (reg-match `(,p2 ,@(cdr pats)) str pos))]

        [`(,p *) (or (reg-match (cdr pats) str pos)

                     (reg-match `(,p ,@pats) str pos))]

        [`(,p +) (reg-match `(,p (,p *) ,@(cdr pats)) str pos)]

        [`(,p ?) (reg-match `((,p or "") ,@(cdr pats)) str pos)]

        [else (error "bad pattern")])))
; auxiliary function

(define (substring=? pat str start end)

  (for/and ([i (in-range start end)]

            [j (in-naturals)])

    (char=? (string-ref pat j) (string-ref str i))))

; test (reg-match "("a" ("b"*) (("c"?) or ("d"+))) "abbc" 0)

同意 @Zete童鞋的說法。你如果只是想做個簡單的正則的話，標準的做法先生成AST，之後遍歷AST構造NFA，構造完NFA再將其化簡成DFA這樣去做匹配。但是由於正則的語法本身就比較簡單，所以生成AST這步你也可以忽略掉，直接生成NFA。整個演算法可能也就是在NFA化簡DFA的時候比較繁瑣。其他的相對來說還是比較簡單的。

DFA拿到之後，功能還是很有限的。如果你要想把你的正則實現的更加吊炸天點，希望添加capture，backreference, not greedy，僅僅只用DFA是不夠的。需要和NFA結合，對於不同的策略選擇是用DFA還是NFA。其實，我是一直覺得現在的正則變得越來越臃腫了，感覺是功能上想更加的逼近peg，但是又受限於正則本身的表達能力。

除了構造NFA和DFA這樣經典實現之外，你還可以使用 Thompson"s VM的方式，生成位元組碼解釋執行來進行匹配。既然是vm，那就肯定有人覺得：我們為什麼不去給加上JIT，讓vm跑的更快，從而提升正則匹配的性能那？所以就產生了JIT引擎（畢竟自從V8出現之後，你一個腳本語言或者VM沒個JIT功能都不好意思跟別人打招呼）。這個你可以參考下春哥的 sregex：openresty/sregex · GitHub 用的dynasm實現的JIT。

最後：我還是強烈希望樓主去讀下 Russ Cox的 Implementing Regular Expressions ：
Implementing Regular Expressions

看到了C++和JS的版本，我也花了一會兒寫了一個Lua版本（參照的JS版本），主要演示了Lua的幾個特性：

元表，運算符重載的靈活性
閉包和詞法作用域的方便性
靈活和DSL友好的函數調用語法糖
用table+匿名函數代替switch語句
」正確的尾遞歸（調用）」的性能優勢

代碼一共50行，貌似上面說JS的只有40行？沒統計，不過，最終的介面是要比JS的一堆new好看太多了。

前面幾個應該很好解釋，這裡說一下「正確的尾調用」，意思是return foo(...)這樣的函數調用，會直接復用當前的棧楨（可以認為是函數執行過程中需要的空間）來調用foo函數，換句話說，如果所有的遞歸調用都是尾調用，那麼Lua會將所有的遞歸都優化成類似goto的迭代，就不會因為遞歸層數過深而棧溢出了。比如下面代碼裡面的match和concat，本質上都是順序匹配就好，都可以寫成尾調用的形式，棧是不會增長的，而其他的一些函數，因為必須存儲當前的中間狀態（哪怕就一行，return a and b or c，這個和return a ? b : c;是一個意思），也得佔用棧楨。因此只需要注意一下，Lua幾乎可以零成本地寫遞歸演算法。

注意，如果喜歡這種寫法（a^b，如果b是負數，則a最多出現-b次，否則，則a最少出現b次，比如Optional就是a^-1，而Repeat就是a^0），這些寫法和lpeg庫（LPeg - Parsing Expression Grammars For Lua，Lua作者寫的基於回溯的匹配庫）的語法是完全一樣的，你可以馬上用上這個庫，把同樣的（甚至更強的）語法和工業質量的實現用在你的實際項目中~

代碼是這樣的：

local Regex = {} Regex.__index = Regex


function Regex.P(a)        return setmetatable({ T="match",  a    }, Regex) end

function Regex.__mul(a, b) return setmetatable({ T="concat", a, b }, Regex) end

function Regex.__add(a, b) return setmetatable({ T="alt",    a, b }, Regex) end

function Regex.__pow(a, b) return setmetatable({ T="rep",    a, b }, Regex) end
local Match = {}

local match, repLeast, repMost

function Match.match(e,t,i,c)

   if t:sub(i,i+#e[1]-1) ~= e[1] then return end

   return c(t,i+#e[1])

end

function Match.concat(e,t,i,c)

   return match(e[1],t,i,function(t,i) return match(e[2],t,i,c) end)

end

function Match.alt(e,t,i,c)

   return match(e[1],t,i,c) or match(e[2],t,i,c)

end

function Match.rep(e,t,i,c)

   if e[2] &>= 0 then return repLeast(e[1],t,i,c,e[2])

   else return repMost(e[1],t,i,c,-e[2])  end

end

function repLeast(e,t,i,c,n)

   return match(e,t,i,function(t, i)

      return repLeast(e,t,i,c,n-1)

   end) or (n &<= 0 and c(t,i))
end
function repMost(e,t,i,c,n)
   return n &> 0 and match(e,t,i,function(t,i)

      return repMost(e,t,i,c,n-1)

   end) or c(t,i)

end

function match(e,t,i,c)

   local f = Match[e.T]

   if not f then return end

   return f(e,t,i,c)

end
function Regex:match(t)

   return match(self,t,1,function(t,i) return i == #t+1 end)

end

function Regex:search(t, i)

   for i = i or 1, #t do

      if match(self,t,i,function(t,i) return true end) then

         return i

      end

   end

end

local P = Regex.P assert((P"a" * P"b"):match "ab") assert((P"a" + P"b"):match "b") assert((P"a"^0):match "aaaaa") assert((P"a"^0 * P"b"):match "aaaaab") assert((P"a"^0 * P"b"):match "b") assert((P"a"^0 * P"b"):search "aaaaabb") assert((P"a"^-1):match "a") assert((P"a"^-1):match "") assert(((P"a"*P"b")^-1):match "ab") assert(((P"a"*P"b")^-1):match "")

說個玩具代碼之美--簡單正則表達式匹配器實現 30行c, Rob Pike寫的

看看lua的幾百行代碼高大上的實現

首先你要知道正則表達式的文法
然後到@vczh的Gaclib里找出正則相關代碼
山寨之

前幾天正好也在從零實現正則引擎，主要參考是就是別人提到的Cox和輪子哥當年寫的東西。

Cox用C語言寫了re1，可以參考一下。但是裡面有很多是用的vm實現的正則，有些vm實現會產生很多次回溯，性能很差。他這幾篇blog重點說的就是這個問題。既然要造輪子，肯定是想學東西，所以感覺可以直接跳過vm實現。

Cox的NFA的實現，用的不是e-NFA轉NFA轉DFA這種教科書方法，這和vczh的文章里有細節上的區別。Cox的NFA轉DFA也不是教科書里的方法（起碼blog里說的），而是動態的轉一部分（類似於JIT？）。感覺還是輪子哥的清晰。

實現正則引擎其實也是實現一個語言，只不過正則的計算能力要弱很多。所以可以按詞法分析語法分析語義分析代碼生成這種框架來。Cox的方法用的是後綴表達式，vczh用的是AST 樹（也提到了可以用後綴表達式），我覺得這麼簡單的語法，用Cox的方法就很好。

NFA就是個圖（是吧），圖的表示方法其實有幾種，vczh選的是用一個矩陣，每列代表一個狀態，每行代表一個可接受的字元（Incidence Matrix?)。我用的是鄰接表。這裡的不同感覺會對後面e-NFA轉NFA的實現由影響。但是我比較懶還沒寫到那。

源碼參考：
Cox 的re1：re1 -

toy regular expression implementation
vczh的學生的實現：學生做的正則表達式引擎提供下載！

現在應該看支持並,交,差的DFA正則表達式引擎，把自動機的各種演算法用到了極致

最簡單的正則表達式實現可以參考Lua的lstrlib
代碼在：lua/lstrlib.c at master · lua/lua · GitHub
文檔在：Lua 5.3 Reference Manual
不支持「|」，不支持back reference
另外相比pcre或者re2，lstrlib有個獨有特性：For instance, the item %b() matches expressions with
balanced parentheses.
這個實現，代碼短小，簡單易懂，從零寫一個正則表達式引擎適合參考這個代碼來試驗、起步，了解基本原理

經典且實現複雜的正則表達式實現，是起源於Perl的pcre庫
這個代碼龐大、複雜，調調配置，直接拿來用就好
千萬別去擼它的代碼
千萬別去擼它的代碼
千萬別去擼它的代碼

近來非常牛逼的一個正則表達式庫是re2，作者是Russ Cox
在這裡，作者論述了re2背後的思想：Implementing Regular Expressions
代碼在這裡：GitHub - google/re2: RE2 is a fast, safe, thread-friendly alternative to backtracking regular expression engines like those used in PCRE, Perl, and Python. It is a C++ library.
re2的代碼量不大，而且原理先進，可拿來分析研究
正則特性方面，re2不支持back reference，其它的特性基本都支持
Go語言的正則庫也是re2的原理，貌似就是re2的C++代碼移植為Go代碼
就題主的問題，從零寫一個正則表達式引擎，最後，不如把re2拿來變成「完全自主知識產權」。

正則表達式一〉後綴樹一〉NFA一〉DFA

PSA/mini_regex at master · wolfkdy/PSA · GitHub 鄙人寫過一個，只支持 and , or, 以及克萊因閉包的正則表達式引擎，其實正則表達式引擎和詞法分析器是等價的概念，大體思路就是構造NFA，然後用湯普森演算法變成DFA，如果閑的蛋疼就再極小化一下，然後就可以進行匹配了。