C#词法分析器之正则表达式的使用

其中，Regex类是正则表达式的基类，CharClassExp表示字符类（单个字符），LiteralExp表示原义文本（多个字符组成的字符串），RepeatExp表示正则表达式重复（可以重复上限至下限之间的任意次数），AlternationExp表示正则表达式的并（r|s），ConcatenationExp表示正则表达式的连接（rs），AnchorExp表示行首限定、行尾限定和向前看，EndOfFileExp表示文件的结尾（<<EOF>>）。

将CharClassExp、LiteralExp、RepeatExp、AlternationExp、ConcatenationExp这些类进行嵌套，就可以表示大部分正则表达式了；AnchorExp单独拿出来是因为它只能作为最外层的正则表达式，而不能位于其它正则表达式内部；EndOfFileExp则是专门用于<<EOF>>的。这里并未考虑上下文，因为上下文的处理并不在正则表达式这里，而是在之后的“终结符符定义”部分。

正则表达式的表示比较简单，但为了更加易用，有必要提供从字符串（例如"abc[0-9]+"）转换为相应的正则表达式的转换方法。RegexCharClass类是System.Text.RegularExpressions.RegexCharClass类的包装，用于表示一个字符类，我对其中的某些函数进行了修改，以符合我这里的正则表达式定义。RegexOptions类和RegexParser类则是用于正则表达式解析的类，具体的解析算法太过复杂，就不多加解释。

三、正则表达式

正则表达式构造好后，就需要使用它去匹配词素。一个词法分析器可能需要定义很多正则表达式，还可能包括上下文以及行首限定符，处理起来还是比较复杂的。为了简便起见，我会首先讨论怎么用一条正则表达式去匹配字符串，在之后的文章中再讨论如何用组合多条正则表达式去匹配词素。

使用正则表达式匹配字符串，一般都会用到有穷自动机（finiteautomata）的表示方法。有穷自动机是识别器（recognizer），只能对每个可能的输入回答“是”或“否”，表示时候与此自动机相匹配。或者说，不断的读入字符，直到有穷自动机回答“是”，此刻就正确的匹配了一个字符串。

有穷自动机分为两类：

不确定的有穷自动机（NondeterministicFiniteAutomata，NFA）对其边上的标号没有任何限制。一个符号标记离开同一状态的多条边，并且空串$\epsilon$也可以作为标号。确定的有穷自动机（DeterministicFiniteAutomata，DFA）对于每个状态及自动机输入字母表中的每个符号有且只有一条离开该状态、以该符号为标号的边。

NFA和DFA可以识别的语言集合是相同的（后面会说到NFA如何转换为等价的DFA），并且这些语言的集合正好是能够用正则表达式描述的语言集合（正则表达式可以转换为等价的NFA）。因此，采用有穷自动机来识别正则表达式描述的语言，也是很自然的。

3.1不确定的有穷自动机NFA

一个不确定的有穷自动机（NFA）由以下几个部分组成：

一个有穷的状态集合$S$。一个输入符号集合$\Sigma$，即输入字母表（inputalphabet）。我们假设空串$\epsilon$不是$\Sigma$中的元素。一个转换函数（transitionfunction），它为每个状态和$\Sigma\cup\{\epsilon\}$的每个符号都给出了相应的后继状态（nextstate）的集合。$S$中的一个状态$s_0$被指定为开始状态，或者说初始状态。$S$的一个子集$F$被指定为接受状态（或者说终止状态）的集合。

下图就是一个能识别正则表达式(a|b)*baa的语言的NFA，边上的字母就是该边的标号。