使用 Rust 實作 regular expression tester
其實這個功能很早以前就已經完成了,將正規表示式對轉換成Non-Deterministic Automata(NFA) ,來 match 字串,
先前的實作有一些問題,因為再建 NFA的時候,狀態是使用整數來表示。
在轉換成NFA時,正規表示式的 Concatenate, Choose, Repeat 需要將兩個NFA 結合成一個,因為由 Empty 或 Literal 直接建NFA時,
編號一定是從 0 開始,兩個都包含狀態 0 的狀態機,直接結合起來絕對不會是對的,需要讓兩邊的狀態都不一樣才行。
當然也不可能用亂數來作為狀態,畢竟以亂數作為狀態,連一個NFA裡面有哪些狀態都不知道,結合時根本就無法檢查是否有衝突。