解析正则表达式（一）概要 - c++编程基础

silon(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 StateMachine;
typedef SharedPtr 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 之后读到的不是“|”。

注意到此处有个并联处理。在“|”之前已经有了一个由第一次 ParseExprNoO

解析正则表达式（一）概要 (二)