C# 中的正则表达式解析器实现
4.91/5 (42投票s)
关于如何实现正则表达式解析器的文章
引言
我想了解正则表达式解析器是如何工作的。所以我进行了一些搜索，并找到了一些描述正则表达式如何查找匹配过程的精彩文章。我在本文的参考文献部分列出了这些文章。我根据我的研究实现了这个解析器。我将不会详细描述正则表达式背后的过程和理论，因为参考文献中的文章已经很好地涵盖了这一点（正则表达式的主题非常广泛，需要一本书来全面解释）。
在本文中，我将简单地展示一个简单的正则表达式解析器（或迷你正则表达式解析器）的实现。我将继续使用术语自动机、NFA、DFA、最小DFA、状态、转换和epsilon转换。如果您不理解这些术语，我强烈建议您在继续之前阅读参考文献中的一些文章。
所以您会问，“为什么是这个？”这个实现是分步进行的，所以对于想了解正则表达式工作原理的人来说很容易。其他特性
- 拥有一个有助于您理解状态和转换的 GUI
- 使用 ^ 和 $ 标记分别指定在模式开头和结尾进行匹配
- C# 实现，非常面向对象
- 易于理解的代码，附带注释
- 具有允许您控制解析器贪婪度的功能——让您体验贪婪度的不同行为。
- 不限于 ASCII 字符 (0-255)
- 与我遇到的许多解析器相比，此实现更完整。
所以我想与 CodeProject 用户分享这个实现。顺便说一句：这是我第一次提交到 CodeProject，希望您喜欢。
特点
下表显示了解析器支持的符号。
| 符号 | 描述 | 示例 |
| ? | (量词) 匹配前一个字符零次或一次 | "A?" 匹配零次或一次 A |
| + | (量词) 匹配前一个字符一次或多次 | "A+" 匹配一次或多次 A |
| * | (量词) 匹配前一个字符零次或多次 | "A*" 匹配零次或多次 A |
| _ (下划线) | 任意单个字符。 | "a_b" 将匹配 "abb", "aab", "acb"，但不会匹配 "ab" |
| _* | 匹配任意字符零次或多次（通配符）。 | "a_*p" 在字符串 "appleandpato" 中将匹配 "appleandp"。 |
| [ ] | 指定范围 ([a-f]) 或集合 ([abcdef]) 内的任意单个字符。 | "[C-P]arsen" 匹配 "Carsen", "Larsen", "Karsen" 等。 |
| [^] | 指定范围 ([^a-f]) 或集合 ([^abcdef]) 外的任意单个字符。 | "de[^l]-*" 匹配以 "de" 开头且后续字母不是 l 的字符串。 |
| $ | 指定匹配字符串开头的标记 | "AA$" 匹配 "AAA" 中的最后两个 A |
| ^ | 指定匹配字符串结尾的标记 | "^AA" 匹配 "AAA" 中的前两个 A |
| \ (转义) | 您可以转义以下字符 \(, \), \n (换行符), \r (回车符), \[, \], \*, \?, \+, \t (制表符) |
"\n\n" 匹配任意两个连续出现的换行符。 "a]b[cd\]]" 是一个有效模式。 |
一些解析器使用点 (.) 来表示任意单个字符，而不是下划线 (_)。如果您愿意，可以通过简单地更改为此定义的常量值来修改源代码。
您可以通过设置 RegEx.UseGreedy 属性来控制解析器的贪婪度。如果您将此属性设置为 false 并在字符串 "appleandpato" 中使用模式 "a_*p"，它将匹配 "ap" 而不是 "appleandp"。
解析器会验证输入模式字符串的正确性。如果遇到语法错误，它会准确地报告错误及其详细信息（即错误位置、长度和错误类型）。
Using the Code
此解析器中的算法遵循 Mike Clark 先生的讲义。不幸的是，在他将讲义下线后我才下载。所以我在此提供它们。
- LexAnal3_regexpr2nfa.pdf - 解释如何将正则表达式转换为 NFA 的过程
- LexAnal4_nfa2dfa.pdf - 解释如何从 NFA 转换为 DFA 的过程
- LexAnal5_minimaldfa.pdf - 最后，解释如何从 DFA 转换为最小 DFA 或 DFA M' 的过程
我认为这些讲义相当简单且易于理解。我的代码结构就是按照这些讲义中提到的步骤进行的。如果您有时觉得难以理解我的代码在做什么（我希望不会），请阅读其中相关的讲义。
此解析器使用 C# 和 Visual Studio 2005 编写。下面是该组件关键类的部分类图。
Set 类是数学中集合的简单表示。由于 .NET 没有提供 Set 类，我不得不自己编写一个。Map 类是一个介于键和一个或多个对象之间的映射，.NET 中也没有。State 类保存了自动机的 (automata) 数据结构。RegEx 是实际使用其他类的主要类。RegExValidator 类用于验证模式字符串。验证使用递归下降解析 (Recursive Descent Parsing) 进行。除了验证模式，它还执行另外两项任务：插入隐式标记使其显式化以及扩展字符类。例如：
- "AB" -> "A.B" (插入连接运算符(.))
- "A.B" -> "A\.B" (插入转义)
- "[A-C]" -> "(A|B|C)" (扩展范围)
- "(AB" -> 报告括号不匹配的错误
您会在源代码中找到类方法的描述作为注释。
下面的序列图显示了如何使用该解析器。
下面的代码片段展示了如何使用 RegEx 类
private void TestMatch()
{
RegEx re = new RegEx();
string sPattern = "a_*p";
ErrorCode errCode = re.Compile(sPattern);
if (errCode != ErrorCode.ERR_SUCCESS)
{
string sErrSubstring = sPattern.Substring(re.GetLastErrorPosition(),
re.GetLastErrorLength());
string sFormat =
"Error occured during compilation.\nCode: {0}\nAt: {1}\nSubstring: {2}";
sFormat = String.Format(sFormat, errCode.ToString(),
m_regEx.GetLastErrorPosition(), sErrSubstring);
MessageBox.Show(sFormat);
return;
}
int nFoundStart = -1;
int nFoundEnd = -1;
string sToSearch = "appleandpotato";
bool bFound = m_regEx.FindMatch(sToSearch, 0, sToSearch.Length - 1,
ref nFoundStart, ref nFoundEnd);
if (bFound)
{
int nMatchLength = nFoundEnd - nFoundStart + 1;
if (nMatchLength == 0)
{
MessageBox.Show("Matched an empty string at position " +
nFoundStart.ToString() + ".");
}
else
{
string sMatchString = sToSearch.Substring(nFoundStart, nMatchLength);
MessageBox.Show("Match found at: " + nFoundStart.ToString() + "\n" +
sMatchString);
}
}
else
{
MessageBox.Show("No match found.");
}
}
关注点
量词 **\***, **\+**, **\?** 的 NFA 模型可以在我提到的文章中找到。
在实现解析器时，我在几个转换上遇到了很多麻烦
**_** (下划线) - 任意单个字符
**[^A]** - 字符集的补集
我在搜索时没有找到关于这些转换的信息。
经过大量的试错，我找到了可以正常工作的 NFA 模型。使用这些模型，您无需修改原始算法。
这个 "AnyChar" 转换在 RegEx.FindMatch 方法中作为特殊情况处理。如果当前状态没有当前输入符号的转换，它会检查当前状态是否具有 "AnyChar" 符号的转换。如果有，则使用该转换。
字符集补集使用 "AnyChar" 转换和 "Dummy" 转换。如果当前状态使用了被禁止的转换（例如，在 [^A] 中的 A），它会转到一个只有一个出度的状态——即 "Dummy" 转换，并且该状态不是接受状态。"Dummy" 转换在实际过程中永远不会被使用，因此解析器会到达死胡同状态，从而导致不匹配。如果当前状态没有当前输入符号的任何转换，它会使用 "AnyChar" 转换并到达接受状态，从而有效地匹配正确的部分/字符串。
此外，RegEx.FindMatch 方法也需要一些讨论。如果没有实现 ^（匹配开始）、$（匹配结束）、_（任意单个字符）、_*(通配符 - 任意数量的任意字符）和贪婪度（控制它）的功能，此方法将非常简单，如下所示：
public bool FindMatch(string sSearchIn,
int nSearchStartAt,
int nSearchEndAt,
ref int nFoundBeginAt,
ref int nFoundEndAt)
{
if (m_stateStartDfaM == null)
{
return false;
}
if (nSearchStartAt < 0)
{
return false;
}
State stateStart = m_stateStartDfaM;
nFoundBeginAt = -1;
nFoundEndAt = -1;
bool bAccepted = false;
State toState = null;
State stateCurr = stateStart;
while (nSearchStartAt <= nSearchEndAt)
{
char chInputSymbol = sSearchIn[nSearchStartAt];
toState = stateCurr.GetSingleTransition(chInputSymbol.ToString());
if (toState == null)
{
toState = stateCurr.GetSingleTransition(MetaSymbol.ANY_ONE_CHAR_TRANS);
}
if (toState != null)
{
if (nFoundBeginAt == -1)
{
nFoundBeginAt = nSearchStartAt;
}
if (toState.AcceptingState)
{
bAccepted = true;
nFoundEndAt = nSearchStartAt;
}
stateCurr = toState;
nSearchStartAt++;
}
else
{
if (!bAccepted) // we reset everything
{
nSearchStartAt = (
nFoundBeginAt != -1 ? nFoundBeginAt + 1 : nSearchStartAt + 1);
nFoundBeginAt = -1;
nFoundEndAt = -1;
stateCurr = stateStart; // start from beginning
}
else
{
break;
}
}
} // end of while..loop
return bAccepted;
}
但添加了这些功能后，此方法变得更具逻辑性。目前的实现如下所示：
public bool FindMatch(string sSearchIn,
int nSearchStartAt,
int nSearchEndAt,
ref int nFoundBeginAt,
ref int nFoundEndAt)
{
if (m_stateStartDfaM == null)
{
return false;
}
if (nSearchStartAt < 0)
{
return false;
}
State stateStart = m_stateStartDfaM;
nFoundBeginAt = -1;
nFoundEndAt = -1;
bool bAccepted = false;
State toState = null;
State stateCurr = stateStart;
int nIndex = nSearchStartAt;
int nSearchUpTo = nSearchEndAt;
while (nIndex <= nSearchUpTo)
{
if (m_bGreedy && IsWildCard(stateCurr) == true)
{
if (nFoundBeginAt == -1)
{
nFoundBeginAt = nIndex;
}
ProcessWildCard(stateCurr, sSearchIn, ref nIndex, nSearchUpTo);
}
char chInputSymbol = sSearchIn[nIndex];
toState = stateCurr.GetSingleTransition(chInputSymbol.ToString());
if (toState == null)
{
toState = stateCurr.GetSingleTransition(MetaSymbol.ANY_ONE_CHAR_TRANS);
}
if (toState != null)
{
if (nFoundBeginAt == -1)
{
nFoundBeginAt = nIndex;
}
if (toState.AcceptingState)
{
// then we ignore the accepting state
if (m_bMatchAtEnd && nIndex != nSearchUpTo)
{
//toState = stateStart ;
}
else
{
bAccepted = true;
nFoundEndAt = nIndex;
if (m_bGreedy == false)
{
break;
}
}
}
stateCurr = toState;
nIndex++;
}
else
{
if (!m_bMatchAtStart && !bAccepted ) // we reset everything
{
nIndex = (nFoundBeginAt != -1 ? nFoundBeginAt + 1 : nIndex + 1);
nFoundBeginAt = -1;
nFoundEndAt = -1;
//nIndex++;
stateCurr = stateStart; // start from beginning
}
else
{
break;
}
}
} // end of while..loop
if (!bAccepted)
{
if (stateStart.AcceptingState == false)
{
return false;
}
else // matched an empty string
{
nFoundBeginAt = nSearchStartAt;
nFoundEndAt = nFoundBeginAt - 1;
return true;
}
}
return true;
}
最初，我费力地尝试不在 FindMatch 方法中添加任何额外的逻辑，并试图通过 NFA 模型寻找这些功能的解决方案。但这些努力一无所获，最终我在此方法中添加了一些逻辑。但现在所有这些功能都运行得很好。
结语
这是一个简单的实现。如果您愿意，可以为这个演示代码添加更多功能。如果您为此处提供的演示代码添加了更多功能，如果您方便的话，我很希望能获得一份代码副本。您可以根据 CodeProject 许可证 (CPOL) 以任何您喜欢的方式使用此代码。如果您想将此演示代码移植到 C++，我认为这不会太难。
历史
- 2008 年 8 月 1 日 -- 首次提交
- 2009 年 2 月 24 日 -- Xawiersas 发现了代码中的一个错误（见下文），所以我修复了它并重构了代码，使其更具可读性。
- 2009 年 6 月 24 日 -- 更新了源代码和演示项目
参考文献
- Mike Clark 先生的讲义
- LexAnal3_regexpr2nfa.pdf - 解释如何将正则表达式转换为 NFA 的过程
- LexAnal4_nfa2dfa.pdf - 解释如何从 NFA 转换为 DFA 的过程
- LexAnal5_minimaldfa.pdf - 最后，解释如何从 DFA 转换为最小 DFA 或 DFA M' 的过程
- 编写自己的正则表达式解析器 作者：Amer Gerzic
- 正则表达式匹配可以简单快速 作者：Russ Cox