想搞正則表達式解析器好久了。前面由於一些基礎設施沒准備好，沒法開始動手。現在 xlLib 裡頭准備的差不多了，可以著手實施了。
在做這件事之前，讀了好幾遍 @vczh 的文章《構造可配置詞法分析器》《構造正則表達式引擎》（http://www.cppblog.com/vczh/archive/2008/05/22/50763.html），給了很大的幫助和啟發，在這裡表示感謝。（雖然到現在為止還沒有完全讀懂。）
編譯原理理論上的東西我了解的還不是很多。正則表達式在文本解析中有著特殊的作用，特殊之一是，它的每個詞法單元都是單個字符（轉義的除外），因此詞法分析階段需要做的工作僅僅是轉義、識別單個字符。
本文我們實現以下功能：
詞法分析
語法分析
操作符“|”的支持
小括號“()”的支持（僅用於改變優先級）
詞法分析
我們定義一個 Token 結構來描述一個詞法單元：
enum TokenType
{
TT_Eof,
TT_VerticalBar, // |
TT_OpenParen, // (
TT_CloseParen, // )
TT_OrdinaryChar
};
struct Token
{
TokenType type;
Char ch;
size_t length;
Token(TokenType type = TT_OrdinaryChar, Char ch = 0, size_t length = 1)
: ch(ch), type(type), length(length)
{
}
};
其中 TokenType 表示哪種類型，除了普通字符外，我們支持的單詞類型有豎線、左小括號、右小括號，EOF 嚴格的說並不屬於單詞，但這裡我們需要一種表示單詞讀盡的方法。ch 表示這個 Token 的字符，length 表示這個 Token 的字符個數，一般來說是 1，如果碰到轉義的，那就不是 1。之所以要記錄長度，是因為有時候試探性地多讀了一個 Token 後，需要回退回去。
整個詞法分析就由下面這一個函數去做：
Token LookAhead()
{
if (m_nCurrentPosition >= m_strRegExp.Length())
{
return Token(TT_Eof, 0, 0);
}
Char ch = m_strRegExp[m_nCurrentPosition++];
TokenType type = TT_OrdinaryChar;
if (ch == L'\\')
{
if (m_nCurrentPosition < m_strRegExp.Length())
{
return Token(TT_OrdinaryChar, m_strRegExp[m_nCurrentPosition++], 2);
}
}
switch (ch)
{
case L'|':
type = TT_VerticalBar;
break;
case L'(':
type = TT_OpenParen;
break;
case L')':
type = TT_CloseParen;
break;
default:
break;
}
return Token(type, ch);
}
其中 m_strRegExp 是要解析的表達式，m_nCurrentPosition 是當前位置。
我們的轉義定義是，從前往後讀，反斜槓 \ 後面的一個字符，轉義為該字符本身。反斜槓後面跟任何字符，都是合法的。如果反斜槓出現在最後一個位置，那麼容錯處理，視為反斜槓這個字符。其余未經轉義的，除了我們已定義功能的“|”“(”“)”外，都作為普通字符處理。目前這樣的轉義處理，不支持 \d、\uXXXX 之類的寫法，這些以後再考慮。
順便再寫一個回退用的函數：
void Backward(const Token &token)
{
m_nCurrentPosition -= token.length;
}
語法分析
文法介紹
按照本文開頭定義的，我們的“正則表達式”的語法可以用以下的 EBNF 文法描述：
Expr -> ExprNoOr { "|" ExprNoOr }
ExprNoOr -> ExprNoGroup { "(" Expr ")" ExprNoGroup }
ExprNoGroup -> { OrdinaryChar }
（大概這個意思，不知道寫得規不規范）
“|”的優先級最低，整個表達式（Expr）首先被第一級豎線分割成各個版本不帶豎線的子式（ExprNoOr）。
每個 ExprNoOr，被括號分分隔，括號外面的是不帶括號（當然也不帶豎線）的子式（ExprNoGroup），括號的裡面，視為一個完整的表達式（Expr）。整個 ExprNoOr，由若干個 ExprNoGroup 或者帶括號的表達式連接構成。注意這裡有個遞歸定義。到目前為止，所有的子式將終結於 ExprNoGroup。
ExprNoGroup 定義為由若干個普通字符（不含“|”“(”“)”）組成的字符串。
狀態機
這個，完整的叫做“非確定有限狀態機”（NFA），理論上的東西我目前不是很精確地了解，以後總結。現在把代碼實現中所需要的預備知識和算法講一下。
舉個例子，對於符合我們前面定義的正則表達式“abc”，我們可以用一下的NFA 表示：
匹配字符串的時候，我們從起始狀態S 開始，依次用每個字符區嘗試匹配每一條邊，如果最後走到結束狀態E，說明匹配成功。
再例如“(a|b)c”，它的NFA 表示如下：
又例如“a|ab”，它的NFA 表示如下：
這時，一個狀態後面可能有不止一條邊滿足某個字符的通過條件，匹配的時候可能需要進行回溯操作。
另外，由於一下代碼實現實現上的原因，“a|bc”可能被弄成下面這個樣子：
跟剛才的相比，多了一條“ε邊”。ε邊是一條可以不消耗字符直接通過的邊。
具有ε邊的 NFA 叫做 ε-NFA。
好了，上面介紹了我們在本文定義的正則表達式語法中可能涉及到的狀態機的樣子。操作符“|”會導致狀態機產生支路；括號改變優先級，體現在支路的位置不同。
我們使用一個圖結構（xl::Graph）表示狀態機，圖的簡單實現見：
http://xllib.codeplex.com/SourceControl/changeset/view/16803#160588
節點的數據結構定義如下：
struct Node
{
public:
Node() : m_nIdentify(++ms_nCounter)
{
}
int m_nIdentify;
static int ms_nCounter;
};
__declspec(selectany) int Node::ms_nCounter = 0;
沒有特別的數據，只帶一個類實例計數，以區分不同的實例。
邊的數據結構定義如下：
struct Edge
{
Edge()
: m_bEpsilon(true), m_chBegin(0), m_chEnd(0)
{
}
Edge(Char ch)
: m_bEpsilon(false), m_chBegin(ch), m_chEnd(ch)
{
}
Edge(Char chBegin, Char chEnd)
: m_bEpsilon(false), m_chBegin(chBegin), m_chEnd(chEnd)
{
}
bool Match(Char ch)
{
if (m_bEpsilon)
{
return false;
}
return (ch >= m_chBegin && ch <= m_chEnd);
}
bool bEpsilon;
Char chBegin;
Char chEnd;
};
代碼實現
我們將用一個類 xl::RegExp 來實現這個簡單的“正則表達式”。一些成員變量定義如下：
typedef Graph<Node, Edge> StateMachine;
typedef SharedPtr<StateMachine> StateMachinePtr;
StateMachinePtr m_spStateMachine;
StateMachine::NodePtr m_pBegin;
StateMachine::NodePtr m_pEnd;
String m_strRegExp;
int m_nCurrentPosition;
m_spStateMachine 就是狀態機，m_pBegin 和 m_pEnd 是頭指針和尾指針。m_strRegExp 保存待解析的表達式，m_nCurrentPosition 是 LookAhead 裡面保存當前位置的。
入口函數：
bool Parse(const String &s)
{
m_strRegExp = s;
m_nCurrentPosition = 0;
m_spStateMachine = new StateMachine;
m_pBegin = m_spStateMachine->AddNode(NewNode());
m_pEnd = Parse(m_pBegin);
if (m_pEnd == nullptr)
{
return false;
}
return true;
}
簡單做下初始化和准備工作，將控制權交給另一個 Parse 函數，最後檢查結果。
有幾個為了書寫方便而引入的狀態機操作函數這裡先提一下：
// 創建一個節點（不加入狀態機）
StateMachine::NodePtr NewNode()
{
return new StateMachine::NodeType();
}
// 創建一條ε邊（不加入狀態機）
StateMachine::EdgePtr NewEdge()
{
return new StateMachine::EdgeType();
}
// 創建一條可通過一個字符的邊（不加入狀態機）
StateMachine::EdgePtr NewEdge(Char ch)
{
return new StateMachine::EdgeType(Edge(ch));
}
// 創建一條可通過一個區間的字符的邊（不加入狀態機）
StateMachine::EdgePtr NewEdge(Char chBegin, Char chEnd)
{
return new StateMachine::EdgeType(Edge(chBegin, chEnd));
}
// 從一個指定節點連一條可通過一個字符的邊到新節點，返回新節點
StateMachine::NodePtr AddNormalNode(StateMachine::NodePtr pNodeFrom, Char chEdgeChar)
{
StateMachine::EdgePtr pEdge = NewEdge(chEdgeChar);
StateMachine::NodePtr pNode = NewNode();
m_spStateMachine->AddNode(pNode);
m_spStateMachine->AddEdge(pEdge, pNodeFrom, pNode);
return pNode;
}
下面是依據 EBNF 而構造的一組語法分析函數，每個函數大體長成這樣：
StateMachine::NodePtr ParseXXX(StateMachine::NodePtr pNode);
傳入的是當前節點，返回的是解析完畢後的當前節點。如果出現錯誤，那麼返回 nullptr。
重新回顧一下 EBNF：
Expr -> ExprNoOr { "|" ExprNoOr }
ExprNoOr -> ExprNoGroup { "(" Expr ")" ExprNoGroup }
ExprNoGroup -> { OrdinaryChar }
函數如下：
StateMachine::NodePtr Parse(StateMachine::NodePtr pNode)
{
StateMachine::NodePtr pCurrent = ParseExpr(pNode);
Token token = LookAhead();
if (token.type != TT_Eof)
{
return nullptr;
}
return pCurrent;
}
這個 Parse 並不屬於 EBNF 的一部分，它也是入口性質的，為了調用 ParseExpr。因為 ParseExpr 需要處理的可能是整個表達式，也可能是括號裡的子式，所以 ParseExpr 不能以 TT_Eof 作為結束，而是以不認識的字符作為結束。上面的 Parse 是針對整個表達式的，它來檢驗表達式是否全部解析完畢。
下面是 ParseExpr：
StateMachine::NodePtr ParseExpr(StateMachine::NodePtr pNode)
{
StateMachine::NodePtr pCurrent = ParseExprNoOr(pNode);
if (pCurrent == nullptr)
{
return nullptr;
}
while (true)
{
Token token = LookAhead();
if (token.type != TT_VerticalBar)
{
Backward(token);
return pCurrent;
}
StateMachine::NodePtr pNewNode = ParseExprNoOr(pNode);
StateMachine::EdgePtr pEdge = NewEdge();
m_spStateMachine->AddEdge(pEdge, pNewNode, pCurrent);
}
return nullptr;
}
按照文法中描述的，它首先做一遍 ParseExprNoOr，然後檢查下一個字符是不是“|”，如果是，繼續 ParseExprNoOr，如此循環往復。直到某一次 ParseExprNoOr 之後讀到的不是“|”。
注意到此處有個並聯處理。在“|”之前已經有了一個由第一次 ParseExprNoOr 產生的新節點 pCurrent，第二次（以及第三次、第四次……） ParseExprNoOr 產生的新節點 pNewNode，都用一條ε邊連接到 pCurrent。
接下來是 ParseExprNoOr：
StateMachine::NodePtr ParseExprNoOr(StateMachine::NodePtr pNode)
{
StateMachine::NodePtr pCurrent = pNode;
while (true)
{
pCurrent = ParseExprNoGroup(pCurrent);
if (pCurrent == nullptr)
{
return nullptr;
}
Token token = LookAhead();
if (token.type != TT_OpenParen)
{
Backward(token);
return pCurrent;
}
pCurrent = ParseExpr(pCurrent);
if (pCurrent == nullptr)
{
return nullptr;
}
token = LookAhead();
if (token.type != TT_CloseParen)
{
return nullptr;
}
}
return nullptr;
}
它跟文法中寫的形式上稍稍有點不一樣。文法中是“ExprNoGroup { "(" Expr ")" ExprNoGroup }”，而現在好像是“{ ExprNoGroup "(" Expr ")" }”。其實是一樣的，循環的退出點是某一次 ParseExprNoGroup 之後讀到的不是“(”，要不要重復取決於“(”有沒有出現。
以下是 ParseExprNoGroup，也是本文的解析終點：
StateMachine::NodePtr ParseExprNoGroup(StateMachine::NodePtr pNode)
{
StateMachine::NodePtr pCurrent = pNode;
while (true)
{
Token token = LookAhead();
if (token.type != TT_OrdinaryChar)
{
Backward(token);
return pCurrent;
}
pCurrent = AddNormalNode(pCurrent, token.ch);
if (pCurrent == nullptr)
{
return nullptr;
}
}
return nullptr;
}
它只認普通字符，有的話把它加入狀態機。
至此，我們的語法分析已經做完了，最終得到一個ε-NFA。之後我們使用這個ε-NFA來匹配字符串。
匹配檢驗
相對於語法分析，匹配就比較簡單了。我們現在要做的工作是：已知一個正則表達式對應的ε-NFA，給出一個字符串，判定該字符串是否符合正則表達式的描述。
由於我們現在直接使用ε-NFA，所以可能需要回溯，因此，簡單起見寫成如下遞歸形式：
bool Match(const String &s)
{
return Match(s, 0, m_pBegin);
}
bool Match(const String &s, int i, StateMachine::NodePtr pNode)
{
if (pNode == m_pEnd)
{
if (i < s.Length())
{
return false;
}
return true;
}
for (auto it = pNode->arrNext.Begin(); it != pNode->arrNext.End(); ++it)
{
if (Match(s, i, *it))
{
return true;
}
}
return false;
}
bool Match(const String &s, int i, StateMachine::EdgePtr pEdge)
{
if (!pEdge->tValue.bEpsilon)
{
if (i >= s.Length())
{
return false;
}
if (!pEdge->tValue.Match(s[i]))
{
return false;
}
return Match(s, i + 1, pEdge->pNext);
}
else
{
return Match(s, i, pEdge->pNext);
}
}
第一個 Match 是入口。第二個 Match 是針對某個節點，它遍歷該節點的所有後續的邊，如果從某一條邊解析後續字符串成功，就結束，否則繼續嘗試下一條邊。第三個 Match 是針對某條邊的，如果能通過這條邊，就繼續到下個節點。這裡有個對ε邊的特殊處理，如果是ε邊，i 沒有加一，直接到下個節點。
上述過程是一個深度優先的搜索過程，如果能走到最後的節點，且字符串也剛剛走到最後，算匹配成功。
單元測試
先做一些常規的測試：
XL_TEST_CASE()
{
RegExp r;
XL_TEST_ASSERT(r.Parse(L""));
XL_TEST_ASSERT(r.Parse(L"||"));
XL_TEST_ASSERT(r.Parse(L"()"));
XL_TEST_ASSERT(r.Parse(L"|"));
XL_TEST_ASSERT(r.Parse(L"(|)"));
XL_TEST_ASSERT(r.Parse(L"(||)"));
XL_TEST_ASSERT(r.Parse(L"()|()"));
XL_TEST_ASSERT(!r.Parse(L"("));
XL_TEST_ASSERT(!r.Parse(L")"));
}
XL_TEST_CASE()
{
RegExp r;
XL_TEST_ASSERT(r.Parse(L""));
XL_TEST_ASSERT(r.Match(L""));
XL_TEST_ASSERT(!r.Match(L"a"));
XL_TEST_ASSERT(r.Parse(L"a"));
XL_TEST_ASSERT(r.Match(L"a"));
XL_TEST_ASSERT(!r.Match(L"ab"));
XL_TEST_ASSERT(!r.Match(L"b"));
XL_TEST_ASSERT(r.Parse(L"(a)"));
XL_TEST_ASSERT(r.Match(L"a"));
XL_TEST_ASSERT(!r.Match(L"ab"));
XL_TEST_ASSERT(!r.Match(L"b"));
XL_TEST_ASSERT(r.Parse(L"ab|c"));
XL_TEST_ASSERT(!r.Match(L"a"));
XL_TEST_ASSERT(!r.Match(L"b"));
XL_TEST_ASSERT(r.Match(L"c"));
XL_TEST_ASSERT(r.Match(L"ab"));
XL_TEST_ASSERT(!r.Match(L"bc"));
XL_TEST_ASSERT(!r.Match(L"ac"));
XL_TEST_ASSERT(r.Parse(L"a(b|c)"));
XL_TEST_ASSERT(!r.Match(L"a"));
XL_TEST_ASSERT(!r.Match(L"b"));
XL_TEST_ASSERT(!r.Match(L"c"));
XL_TEST_ASSERT(r.Match(L"ab"));
XL_TEST_ASSERT(r.Match(L"ac"));
XL_TEST_ASSERT(!r.Match(L"bc"));
}
XL_TEST_CASE()
{
RegExp r;
XL_TEST_ASSERT(r.Parse(L"\\|"));
XL_TEST_ASSERT(r.Match(L"|"));
XL_TEST_ASSERT(r.Parse(L"\\("));
XL_TEST_ASSERT(r.Match(L"("));
XL_TEST_ASSERT(r.Parse(L"\\)"));
XL_TEST_ASSERT(r.Match(L")"));
XL_TEST_ASSERT(r.Parse(L"\\\\"));
XL_TEST_ASSERT(r.Match(L"\\"));
XL_TEST_ASSERT(r.Parse(L"\\"));
XL_TEST_ASSERT(r.Match(L"\\"));
XL_TEST_ASSERT(r.Parse(L"\\|(\\(|\\))"));
XL_TEST_ASSERT(r.Match(L"|("));
XL_TEST_ASSERT(r.Match(L"|)"));
}
嗯……沒有成就感。再來點有意思的。我們目前雖然只支持“|”和“(”“)”，但能做的事情已經很多了，比如匹配 0 到 255 的數字。
我們將 0 到 255 的數分為五類：
1. 一位數：(0|1|2|3|4|5|6|7|8|9)
2. 兩位數：(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)
3. 三位數：
a) 0到199：(0|1)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)
b) 200到249：2(0|1|2|3|4)(0|1|2|3|4|5|6|7|8|9)
c) 250到255：25(0|1|2|3|4|5)
將這五個使用“|”連起來，就是一個0到255的正則表達式。
XL_TEST_CASE()
{
RegExp r;
XL_TEST_ASSERT(r.Parse(L"(0|1|2|3|4|5|6|7|8|9)|"
L"(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)|"
L"(0|1)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)|"
L"2(0|1|2|3|4)(0|1|2|3|4|5|6|7|8|9)|"
L"25(0|1|2|3|4|5)"));
XL_TEST_ASSERT(r.Match(L"0"));
XL_TEST_ASSERT(r.Match(L"1"));
XL_TEST_ASSERT(r.Match(L"2"));
XL_TEST_ASSERT(r.Match(L"3"));
XL_TEST_ASSERT(r.Match(L"4"));
XL_TEST_ASSERT(r.Match(L"5"));
XL_TEST_ASSERT(r.Match(L"6"));
XL_TEST_ASSERT(r.Match(L"7"));
XL_TEST_ASSERT(r.Match(L"8"));
XL_TEST_ASSERT(r.Match(L"9"));
XL_TEST_ASSERT(r.Match(L"10"));
XL_TEST_ASSERT(r.Match(L"20"));
XL_TEST_ASSERT(r.Match(L"30"));
XL_TEST_ASSERT(r.Match(L"40"));
XL_TEST_ASSERT(r.Match(L"50"));
XL_TEST_ASSERT(r.Match(L"60"));
XL_TEST_ASSERT(r.Match(L"70"));
XL_TEST_ASSERT(r.Match(L"80"));
XL_TEST_ASSERT(r.Match(L"90"));
XL_TEST_ASSERT(r.Match(L"100"));
XL_TEST_ASSERT(r.Match(L"199"));
XL_TEST_ASSERT(r.Match(L"200"));
XL_TEST_ASSERT(r.Match(L"249"));
XL_TEST_ASSERT(r.Match(L"250"));
XL_TEST_ASSERT(r.Match(L"251"));
XL_TEST_ASSERT(r.Match(L"252"));
XL_TEST_ASSERT(r.Match(L"253"));
XL_TEST_ASSERT(r.Match(L"254"));
XL_TEST_ASSERT(r.Match(L"255"));
XL_TEST_ASSERT(!r.Match(L"256"));
XL_TEST_ASSERT(!r.Match(L"260"));
XL_TEST_ASSERT(!r.Match(L"300"));
}
我們可以 YY 下現在的狀態機的樣子：
再來一個例子，匹配 IPv4。我們剛才已經有了0到255的數字的表示方法了，將他們用句點“.”連接起來就可以了。注意，“.”在我們目前的定義中沒有特殊含義，只是普通字符，所以不必轉義（當然轉義一下也沒問題）。
XL_TEST_CASE()
{
RegExp r;
// IPv4 address
XL_TEST_ASSERT(r.Parse(L"("
L"(0|1|2|3|4|5|6|7|8|9)|"
L"(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)|"
L"(0|1)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)|"
L"2(0|1|2|3|4)(0|1|2|3|4|5|6|7|8|9)|"
L"25(0|1|2|3|4|5)"
L").("
L"(0|1|2|3|4|5|6|7|8|9)|"
L"(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)|"
L"(0|1)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)|"
L"2(0|1|2|3|4)(0|1|2|3|4|5|6|7|8|9)|"
L"25(0|1|2|3|4|5)"
L").("
L"(0|1|2|3|4|5|6|7|8|9)|"
L"(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)|"
L"(0|1)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)|"
L"2(0|1|2|3|4)(0|1|2|3|4|5|6|7|8|9)|"
L"25(0|1|2|3|4|5)"
L").("
L"(0|1|2|3|4|5|6|7|8|9)|"
L"(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)|"
L"(0|1)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)|"
L"2(0|1|2|3|4)(0|1|2|3|4|5|6|7|8|9)|"
L"25(0|1|2|3|4|5)"
L")"));
XL_TEST_ASSERT(r.Match(L"192.168.1.1"));
XL_TEST_ASSERT(r.Match(L"0.0.0.0"));
XL_TEST_ASSERT(r.Match(L"255.255.255.255"));
XL_TEST_ASSERT(!r.Match(L"0.0.0.256"));
}
小結
本文構造了正則表達式解析器的一個基本框架，並且完成了對“|”“(”“)”這三個操作符的語法分析。在這裡，我們確定了基本的數據結構和算法，以後將在此基礎上擴展，實現更多的功能。
本文中定義的節點結構和邊結構，只適用於目前的需求，以後如果滿足不了需要，將會修改。本文所使用的 xl::Graph 功能也並不完善，以後也會同步修改。本文使用ε-NFA直接進行匹配檢驗，檢驗的時候使用了較多的遞歸，性能上並沒有達到比較優化的狀態，這將在未來某篇中討論。在最初的幾篇中，我們將著重於實現一些必要的功能。
本文中涉及的實現代碼在：
http://xllib.codeplex.com/SourceControl/changeset/view/16815#270275
單元測試代碼在：
http://xllib.codeplex.com/SourceControl/changeset/view/16815#270901
歡迎探討、批評、指正。
摘自 溪流漫話
