標籤：

正則表達式的實現

01-31

幾年前學習編譯原理的時候看過codeproject上的 一篇文章，講解了正則表達式引擎的一種實現，這裡要閱讀.NET的源碼，又把這篇文章撿起來學習一下，原文用的是C++實現，我重新用C#代碼實現一遍。

正則表達式基本操作

其實可以把原始的正則表達式操作歸類成下面三種（不考慮回溯、分組等方法）：

  1. 克林閉包（Kleen Closure）或者說星號操作，如 a* ；
  2. 串聯（Concatenation）操作，如 ab；
  3. 合併（Union）操作，通常符號用 「|」 實現，如：a | b。

其它的操作都可以用上面三種操作組合實現，如：

  • a+，可以通過串聯和克林閉包組合實現，如 aa*；
  • [a-z]，可以通過合併實現，如 a | b | c | ... | z。

而上面的三種基本操作，採用NFA - DFA演算法實現，生成DFA之後，DFA可以理解成一個表格，表格每一行表示有限自動機的狀態，而列表示從當前狀態可以執行的狀態轉換。例如下面的表格：

int DFATable[][37] = {n // 0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z !n {1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,-1}, // s0 -- 起始狀態n {1,1,1,1,1,1,1,1,1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}, // s1 -- 到這裡說明是數字n {3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,4,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,-1}, // s2 -- 變數n {2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,-1},n {2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,-1} // s4 -- 這是IFn};n

有限自動機在代碼裡面的表示就是那個二維數組 DFATable。DFATable的每一行(DFATable[i])表示有限自動機的狀態，而列表示從當前狀態可以執行的狀態轉換（Transfer）。例如在匹配的時候，程序先從DFATable[0]，也就是起始狀態開始，如果第一個字元串是i，則根據DFATable[0][i]指定的轉換規則跳轉到下一個狀態（State）去，這裡下一個狀態是2，也就是DFATable的第三行，再根據str的下一個字元來確定要轉換的狀態。匹配過程一直循環到字元串被全部處理掉，這時程序判斷當前的狀態是不是一個可以接受的狀態（Acceptable State），也就是說這個狀態是否在TokenType中定義，如果狀態在TokenType中定義，那好，我們給出的字元串匹配成功，否則就是匹配失敗。

基於二維數組的表格匹配法，這個是幾年前我寫的C++代碼，有興趣的網友可以嘗試一下：

#include <iostream>n#include <stdio.h>nnusing namespace std;nnenum TokenTypen{n BOOM_ERROR = -1, // 啊哈，出錯了n NUMBER = 1,n IDENTIFIER = 2,n IF = 4n};nnint DFATable[][37] = {n // 0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z !n {1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,-1}, // s0 -- 起始狀態n {1,1,1,1,1,1,1,1,1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}, // s1 -- 到這裡說明是數字n {3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,4,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,-1}, // s2 -- 變數n {2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,-1},n {2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,-1} // s4 -- 這是IFn};nn// n// Match:n// 給定一個字元串str，判斷這個字元串的類型n// n// 例子:n// if, 返回IFn// 數字,返回NUMBERn// 變數,返回IDENTIFIERn// nTokenType Match(string str)n{n int state = 0;nn for (string::iterator iter = str.begin();n iter != str.end();n ++iter )n {n char c = *iter;n int index = 0;n if ( c >= 0 && c <= 9 )n {n index = c - 0;n }n else if (c >= a && c <= z)n {n index = c - a + 10; // a列在DFATable中的索引值n }n else n {n index = 36; // !列在DFATable中的索引值，到這裡說明不匹配了n }nn state = DFATable[state][index];nn if (state == BOOM_ERROR)n break;n }nn return (TokenType)state;n}nnint g_line = 0;nvoid Print(TokenType type)n{n switch (type)n {n case BOOM_ERROR:n cout << ++g_line << ": BOOM_ERROR/n" <<>n break;nn case IF:n cout << ++g_line << ": IF/n" <<>n break;nn case NUMBER:n cout << ++g_line << ": NUMBER/n" <<>n break;nn case IDENTIFIER:n cout << ++g_line << ": IDENTIFIER/n" <<>n break;nn default:n cout << ++g_line << ": Error/n" <<>n break;n }n}nnint main()n{n Print(Match("if"));n Print(Match("iff"));n Print(Match("if0"));n Print(Match("0if"));n Print(Match("i0f"));n Print(Match("ia"));n Print(Match("01")); n Print(Match("123")); n Print(Match("1f")); n Print(Match("abcd")); n Print(Match("ab")); n Print(Match("a")); n Print(Match("0")); n Print(Match("i"));n Print(Match("_"));nn return 0;n}n

然而使用二維數組的辦法就是每一個列對應一個可能的轉換，比如26個英文字母就要求26列，而且表格的大小也隨著可能的狀態增大而膨脹的很快，採用基於圖的DFA演算法來匹配會節省很多的空間。

將正則表達式轉換成NFA

使用Thompson演算法可以將正則表達式轉換成NFA，上面三個基本的正則表達式操作對應的NFA圖形如下：

1. 串聯操作，ab：

  1. 合併操作，a|b：

  2. 克林閉包，a*：

在將正則表達式轉換成NFA的過程，跟處理計算四則運算的表達式類似，將正則表達式里的普通字元（如a和b）看成普通的操作數，將「|」和「」號看成操作符，因為連接操作中兩個操作數之間沒有操作符，為了處理方便，在轉換前，我們可以預處理一下，在操作數之間加上一個特殊字元：x0008（為了在本文方便演示，我用.號表示字元x0008）。例如經過預處理之後，表達式 `a|bcde就變成a|b.c.d.e*`。下面是執行預處理的代碼：

public SimpleRegex(string expression)n{n var sb = new StringBuilder(expression);n for (int i = 0; i < sb.Length - 1; ++i)n {n var next = sb[i + 1];n if (IsOprand(sb[i]) && next != | && next != * && next != ))n {n sb.Insert(i + 1, CONCAT);n i++;n }n }nn _expression = sb.ToString();n}nnprivate bool IsOprand(char c)n{n return c != ( && c != CONCAT && c != |;n}n

其中操作符|和.都是二目操作符，*是一目操作符，比如說針對表達式a.b|c.d*，如果採用後序處理法 - 表達式轉換成ab.c|d*.，處理過程如下（其中result表示操作符的計算結果）：

PUSH a // 將a壓入操作數棧nPUSH b // 將b壓入操作數棧nPOP // 取出bnPOP // 取出anCONCATENATION // 計算a.b nPUSH result // 將a.b的計算結果壓入操作數棧nPUSH c // 將c壓入操作數棧nPOP // 取出cnPOP // 取出a.b的計算結果nUNION // 計算a.b的計算結果和c的合併nPUSH result // 將結果壓入棧nPUSH d // 將d壓入操作數棧nSTAR // 計算d*nPUSH result // 將結果壓入棧nPOP // 取出d*的結算結構nPOP // 取出前面的計算結果nCONCATENATION // 計算串聯操作nPUSH result // 將結算結果壓棧nPOP // 返回最終結果n

正則表達式里還可以加上括弧來改變模式匹配的優先順序，而且一般用戶輸入的正則表達式不會採用後序法輸入，而是採用中序輸入的表達式。針對中序輸入的表達式，處理辦法一般是，將操作數壓入操作數棧，將操作符壓入操作符棧的時候，先判斷棧頂的操作符是不是比當前操作符的優先順序的優先順序高，如果高的話，則依次先將操作符棧上比當前操作符優先順序高的操作符都計算完，直到棧頂操作符的優先順序比當前操作符的優先順序低。舉個例子，在處理1+2*3+4，在壓入第二個+號的時候，就先計算3*4（這時3和4都在操作數棧里了），並將結果12壓入操作數棧里，這時操作符棧頂的+號的優先順序跟當前操作符的優先順序是一樣的，可以將第二個+號壓棧了，示例代碼里我將各個操作符的優先順序定義為：

Presedences = new Dictionary<char, int>();nPresedences.Add(*, 3);nPresedences.Add(|, 2);nPresedences.Add(CONCAT, 1);nPresedences.Add((, 0);n

下面是處理表達式的代碼，處理完畢之後，操作數棧上應該只剩下一個操作數，也就是最終結果，也是最終的可接受狀態（最終狀態）：

public Graph RegexToNfa()n{n for (int i = 0; i < _expression.Length; ++i)n {n var c = _expression[i];n switch (c)n {n case (:n case |:n case *:n case CONCAT:n // 判斷棧頂操作符的優先順序是不是比當前要壓棧的操作符c的優先順序高？n while (Presedences.ContainsKey(c) && _operatorStack.Count > 0 &&n Presedences[c] < Presedences[_operatorStack.Peek()])n Eval(); // 如果優先順序高的話，先執行高優先順序操作符的計算nn // 將操作符壓棧n _operatorStack.Push(c);n break;nn case ): // 碰到括弧結束，執行括弧里的所有計算n PopTransitions(();n _operatorStack.Pop();n break;nn default: // 將操作數壓棧n PushTransition(c);n break;n }n }nn // 表達式已經處理完畢，計算所有未處理的操作符n PopTransitions();nn // 最後操作數棧頂就是最終的計算結果，而且是最終的可接受狀態n var graph = _oprandStack.Pop();n graph.Vetexes[graph.Vetexes.Count - 1].AcceptingState = true;nn return graph;n}n

具體的操作符處理代碼，通過Eval函數來根據棧頂的操作符來調用對應的函數：

private void Eval()n{n if (_operatorStack.Count > 0)n {n var op = _operatorStack.Pop();nn switch (op)n {n case |:n Union();n break;nn case *:n Star();n break;nn case CONCAT:n Concat();n break;nn default:n throw new InvalidOperationException("不支持的正則表達式操作符!");n }n }n}n

在將正則表達式里的操作數（也就是普通字元）壓棧的時候，其實是壓入一個小的包含一個狀態轉換的NFA圖形，即從一個狀態（from）通過字元（transition）轉換到另一個狀態（to）的圖形，下面是壓入操作數的代碼：

private void PushTransition(char transition)n{n var from = new Vetex();n var to = new Vetex();n from.OutEdges.Add(new Edge(transition, to));nn var graph = new Graph();n graph.Vetexes.Add(from);n graph.Vetexes.Add(to);nn _oprandStack.Push(graph);n}n

這是壓入的圖形的一個示例：

根據Thompson演算法，各個操作的代碼如下：

串聯操作

// 連接兩個NFA圖形nprivate void Concat()n{n // 從操作數棧里取出一個NFA圖形，這個圖形可能不僅僅是一個簡單的圖形n // 可能是一個如"(a|b)*c"這樣的組合圖形n var right = _oprandStack.Pop();n // 串聯操作是雙目操作符，需要兩個操作數n var left = _oprandStack.Pop();n // 通過增加一條從左邊圖形到右邊圖形的epsilon轉換的邊n // 就可以完成串聯n var from = left.Vetexes[left.Vetexes.Count - 1];n var to = right.Vetexes[0];nn from.OutEdges.Add(new Edge(Edge.EPSILON, to));nn // 最終的操作結果保存在左邊的圖形里，把右邊圖形的節點n // 合併到結果節點裡n left.Vetexes.AddRange(right.Vetexes);nn // 將計算結果壓棧，之前的兩個操作數已經出棧了n _oprandStack.Push(left);n}n

結果圖形：

合併操作

private void Union()n{n // 按照Thompson演算法，需要新建兩個節點作為合併後的NFA圖形的起點和終點n var begin = new Vetex();n var end = new Vetex();n // 將操作數出棧n var right = _oprandStack.Pop();n var left = _oprandStack.Pop();nn // 給起點加兩條邊到要合併的兩個NFA圖形的起點n begin.OutEdges.Add(new Edge(Edge.EPSILON, right.Vetexes[0]));n begin.OutEdges.Add(new Edge(Edge.EPSILON, left.Vetexes[0]));nn var rightEnd = right.Vetexes[right.Vetexes.Count - 1];n var leftEnd = left.Vetexes[left.Vetexes.Count - 1];nn // 合併的兩個NFA圖形的終點加兩條邊到新的終點n rightEnd.OutEdges.Add(new Edge(Edge.EPSILON, end));n leftEnd.OutEdges.Add(new Edge(Edge.EPSILON, end));nn // 將新的節點和要合併的NFA圖形的節點都加到新合併後的NFA圖形里n // 這樣完成最終的合併圖形操作n var graph = new Graph();n graph.Vetexes.Add(begin);n graph.Vetexes.AddRange(right.Vetexes);n graph.Vetexes.AddRange(left.Vetexes);n graph.Vetexes.Add(end);nn // 結果壓棧n _oprandStack.Push(graph);n}n

結果圖形：

克林閉包操作

private void Star()n{n // 閉包操作只要一個操作數n var subGraph = _oprandStack.Pop();n var begin = new Vetex();n var end = new Vetex();nn // 按照Thompson演算法新建必要的起始和結束節點n // 再加上必要的epsilon轉換邊n var edgeBegin = subGraph.Vetexes[0];n var edgeEnd = subGraph.Vetexes[subGraph.Vetexes.Count - 1];nn edgeEnd.OutEdges.Add(new Edge(Edge.EPSILON, edgeBegin));n edgeEnd.OutEdges.Add(new Edge(Edge.EPSILON, end));nn begin.OutEdges.Add(new Edge(Edge.EPSILON, end));n begin.OutEdges.Add(new Edge(Edge.EPSILON, edgeBegin));nn var graph = new Graph();n graph.Vetexes.Add(begin);n graph.Vetexes.AddRange(subGraph.Vetexes);n graph.Vetexes.Add(end);nn _oprandStack.Push(graph);n}n

結果圖形：

為了檢驗最終圖形生成的效果，示例代碼里使用了grapviz來生成圖形，這是一個開源的工具，具體的dot語法可以參考文檔，我在程序里加上了生成NFA和DFA圖形的兩個步驟，生成的graphviz文件保存在nfa.dot和dfa.dot文件里。下面是程序執行完畢之後，生成nfa圖形的步驟：

regex abndot -Tpng -o nfa.png nfa.dotn

將NFA轉換成DFA

接下來基於生成的NFA圖形創建DFA，以便做模式匹配，轉化過程的演算法，基本步驟如下：

  1. 從NFA的起始狀態開始，將所有可由該起始狀態經過epsilon轉換到達的狀態都放在DStartStates集合里，這個過程稱為EpsilonClosure，在示例代碼里，函數接受一個狀態集合，返回此集合中可以由epsilon轉換到達的所有狀態的集合：

private SortedSet<Vetex> EpsilonClosure(SortedSet<Vetex> states)n{n // 結果集合應該包含發起的狀態n var result = states;n var stack = new Stack<Vetex>(states);nn // 進行深度遍歷，針對每個未處理的狀態，找到可以從它開始通過epsilon轉換到達的狀態集合n while (stack.Count > 0)n {n var state = stack.Pop();n foreach (var edge in state.OutEdges.Where(e => e.Transition == Edge.EPSILON))n {n var to = edge.To;n if (!result.Contains(to))n {n result.Add(to);n stack.Push(to);n }n }n }nn return result;n}n

  1. 從DStartStates集合里的狀態開始，遍歷輸入模式字元串的每一個字元，找到可以從DStartStates按這個字元轉換到下一個狀態集，這個過程稱為Move，在示例代碼里，函數接受一個狀態集合和輸入字元，返回此集合中可以通過輸入字元轉換到達的所有狀態的集合（不包括epsilon轉換可以到達的）：

private SortedSet<Vetex> Move(SortedSet<Vetex> states, char transition)n{n var result = new SortedSet<Vetex>();n foreach (var state in states)n {n foreach (var edge in state.OutEdges.Where(e => e.Transition == transition))n {n var to = edge.To;n if (!result.Contains(to))n result.Add(to);n }n }nn return result;n}n

  1. 在第二步返回的集合之上再次執行EpsilonClosure過程，獲得所有可以通過輸入字元轉換（包括epsilon轉換）到達的最大狀態集合：
  2. 如果第二步輸入的狀態集合在之前沒有處理過，那麼就將這個狀態集合作為待處理的集合，循環到第二步繼續處理。

// 將NFA圖形轉換成對應的DFAnpublic Graph NfaToDfa(Graph nfa)n{n // 準備執行遍歷，初始化節點的Mark與否狀態n foreach (var vetex in nfa.Vetexes) vetex.Marked = false;nn var result = new Graph();n // 先獲取從起始狀態能通過epsilon轉換到達的狀態集合，也就是將要生成的DFA起始狀態集合n var startStates = EpsilonClosure(new SortedSet<Vetex>(new Vetex[] { nfa.Vetexes[0] }));n var dStates = new SortedSet<VetexGroup>();n dStates.Add(new VetexGroup(startStates));nn while (dStates.Any(v => !v.Marked))n {n // 針對待處理的新生成的DFA狀態集合n var iter = dStates.First(v => !v.Marked);n iter.Marked = true;nn foreach (var c in _inputset.ToString())n {n // 找到可以從當前DFA狀態集合通過輸入字元到達的狀態，也就是執行Move操作n // 並針對Move操作的結果狀態集，再執行一遍EpsilonClosure過程，以求n // 獲取可以從當前字元到達的最大的狀態結果集n var states = EpsilonClosure(Move(iter.Vetexes, c));n if (states.Count == 0) continue;nn // 查看新創建的DFA狀態集是否已經存在了，是集合層面的相等n var vetexGroup = FindDfaStateGroup(dStates, states);nn if (vetexGroup == null)n {n vetexGroup = new VetexGroup(states);n dStates.Add(vetexGroup);n }nn // 在DFA狀態集之間添加狀態轉換，以便生成DFA圖形n iter.OutEdges.Add(new Edge(c, vetexGroup));n }nn result.Vetexes.Add(iter);n }nn return result;n}nn// 查看新創建的DFA狀態集states是否已經在dStates存在了，是集合層面的相等，n// 即判斷兩個集合里的狀態是否完全相等nprivate VetexGroup FindDfaStateGroup(SortedSet<VetexGroup> dStates, SortedSet<Vetex> states)n{n foreach (var item in dStates)n {n if (item.Vetexes.Count != states.Count) continue;nn if (item.Vetexes.All(v => states.Any(vi => vi.State == v.State)))n return item;n }nn return null;n}n

  1. 在第三步中，得到的狀態集合中如果包含可接受狀態，那麼這個狀態集就是DFA的可接受狀態集。

public VetexGroup(SortedSet<Vetex> vetexes) : base()n{n Vetexes = vetexes;n AcceptingState = vetexes.Any(v => v.AcceptingState);n}n

比如一個 a|b 的模式，其NFA和DFA分別是這樣的：

NFA

DFA

進行模式匹配

執行模式匹配的時候，就是以要匹配的字元遍歷模式生成的DFA圖，從起始狀態集合開始，按照待匹配字元串里的字元順序依次遍歷轉換轉換邊，如果待匹配字元串處理完畢後，當前所在的狀態是最終可接受狀態，那麼就說明字元串和模式匹配成功，否則就是失敗了。

public bool Match(Graph graph, string input)n{n var iter = graph.Vetexes[0];nn foreach (var c in input)n {n var edge = iter.OutEdges.SingleOrDefault(e => e.Transition == c);n if (edge == null) return false;nn iter = edge.To;n }nn return iter.AcceptingState;n}n

最小化DFA

最小化DFA的代碼我沒有實現，有興趣的朋友可以閱讀最上面里的codeproject文章。

推薦閱讀：

※高德API+.NET解決租房問題（新增步行導航，價格區間）
※【譯】.NET Core 路線圖
※淺談.NET程序集安全簽名
※造輪子進度（2017.07.26）

TAG:NET | 编译原理 |