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

正则表达式是一种描述词素的重要表示方法。虽然正则表达式并不能表达出所有可能的模式（例如“由等数量的 a 和 b 组成的字符串”），但是它可以非常高效的描述处理词法单元时要用到的模式类型。

一、正则表达式的定义
正则表达式可以由较小的正则表达式按照规则递归地构建。每个正则表达式 r  表示一个语言 L(r) ，而语言可以认为是一个字符串的集合。正则表达式有以下两个基本要素：

1.ϵ  是一个正则表达式， L(ϵ)=ϵ ，即该语言只包含空串（长度为 0 的字符串）。
2.如果 a  是一个字符，那么 a  是一个正则表达式，并且 L(a)={a} ，即该语言只包含一个长度为 1  的字符串 a 。
由小的正则表达式构造较大的正则表达式的步骤有以下四个部分。假定 r  和 s  都是正则表达式，分别表示语言 L(r)  和 L(s) ，那么：

1.(r)|(s)  是一个正则表达式，表示语言 L(r)∪L(s) ，即属于 L(r)  的字符串和属于 L(s)  的字符串的集合（ L(r)∪L(s)={s|s∈L(r) or s∈L(s)} ）。
2.(r)(s)  是一个正则表达式，表示语言 L(r)L(s) ，即从 L(r)  中任取一个字符串，再从 L(s)  中任取一个字符串，然后将它们连接后得到的所有字符串的集合（ L(r)L(s)={st|s∈L(r) and t∈L(s)} ）。
3.(r)∗  是一个正则表达式，表示语言 L(r)∗ ，即将 L(r)  连接 0  次或多次后得到的语言。
4.(r)  是一个正则表达式，表示语言 L(r) 。
上面这些规则都是由 Kleene 在 20 世纪 50 年代提出的，在之后有出现了很多针对正则表达式的扩展，他们被用来增强正则表达式表述字符串模式的能力。这里采用是类似 Flex 的正则表达式扩展，风格则类似于 .Net 内置的正则表达式：

正则表达式	描述
x	单个字符 x。
.	除了换行以外的任意单个字符。
[xyz]	一个字符类，表示 'x'，'y'，'z' 中的任意一个字符。
[a-z]	一个字符类，表示 'a' 到 'z' 之间的任意一个字符（包含 'a' 和 'z'）。
[^a-z]	一个字符类，表示除了 [a-z] 之外的任意一个字符。
[a-z-[b-f]]	一个字符类，表示 [a-z] 范围减去 [b-f] 范围的字符，等价于 [ag-z]。
r*	将任意正则表达式 r 重复 0 次或多次。
r+	将 r 重复 1 次或多次。
r?	将 r 重复 0 次或 1 次，即“可选”的 r。
r{m,n}	将 r 重复 m 次至 n 次（包含 m 和 n）。
r{m,}	将 r 重复 m 次或多次（大于等于 m 次）。
r{m}	将 r 重复恰好 m 次。
{name}	展开预先定义的正则表达式 “name”，可以通过预先定义一些正则表达式，以实现简化正则表达式。
"[xyz]\"foo"	原义字符串，表示字符串“[xyz]"foo”，用法与 C# 中定义字符串基本相同。
\X	表示 X 字符转义，如果 X 是 'a','b','t','r','v','f','n' 或 'e'，表示相应的 ASCII 字符；如果 X 是 'w','W','s','S','d' 或 'D'，则表示相应的字符类；否则表示字符 X。
\nnn	表示使用八进制形式指定的字符，nnn 最多由三位数字组成。
\xnn	表示使用十六进制形式指定的字符，nn 恰好由两位数字组成。
\cX	表示 X 指定的 ASCII 控制字符。
\unnnn	表示使用十六进制形式指定的 Unicode 字符，nnnn 恰好由四位数字组成。
\p{name}	表示 name 指定的 Unicode 通用类别或命名块中的单个字符。
\P{name}	表示除了 name 指定的 Unicode 通用类别或命名块之外的单个字符。
(r)	表示 r 本身。
(?r-s:pattern)	应用或禁用子正则表达式中指定的选项。选项可以是字符 'i','s' 或 'x'。 'i' 表示不区分大小写；'-i' 表示区分大小写。 's' 表示允许 '.' 匹配换行符；'-s' 表示不允许 '.' 匹配换行符。 'x' 表示忽略模式中的空白和注释，除非使用 '\' 字符转义或者在字符类中，或者使用双引号（""） 括起来；'-x' 表示不忽略空白。 以下下两列中的模式是等价的： (?:foo) (foo) (?i:ab7) ([Aa][Bb]7) (?-i:ab) (ab) (?s:.) [\u0000-\uFFFF] (?-s:.) [^\n\r] (?ix-s: a . b) ([Aa][^\n\r][Bb]) (?x:a b) ("ab") (?x:a\ b) ("a b") (?x:a" "b) ("a b") (?x:a[ ]b) ("a b") (?x:a     (?#comment)     c) (abc)
(?#comment)	表示注释，注释中不允许出现右括号 ')'。
rs	r 与 s 的连接。
r|s	r 与 s 的并。
r/s	仅当 r 后面跟着 s 时，才匹配 r。这里 '/' 表示向前看，s 并不会被匹配。
^r	行首限定符，仅当 r 在一行的开头时才匹配。
r$	行尾限定符，仅当 r 在一行的结尾时才匹配。这里的行尾可以是 '\n'，也可以是 '\r\n'。
<s>r	仅当当前是上下文 s 时才匹配 r。
<s1,s2>r	仅当当前是上下文 s1 或 s2 时才匹配 r。
<*>r	在任意上下文中匹配 r。
<<EOF>>	表示在文件的结尾。
<s1,s2><<EOF>>	表示在上下文 s1 或 s2 时的文件的结尾。

这里与字符类和 Unicode 通用类别相关的知识请参考 C# 的正则表达式语言 - 快速参考中的“字符类”小节。大部分的正则表达式表示方法也与 C# 中的相同，有所不同的向前看（r/s）、上下文（<s>r）和文件结尾（<<EOF>>）会在之后的文章中解释。

利用上面的表格中列出扩展正则表达式，就可以比较方便的定义需要的模式了。不过有些需要注意的地方：

1. 这里的定义不支持 POSIX Style 的字符类，例如 [:alnum:] 之类的，与 Flex 不同。
2. $ 匹配行尾，即可以匹配 \n 也可以匹配 \r\n，也与 Flex 不同。
3. 字符集的相减是 C# 风格的 [a-z-[b-f]]，而不是 Flex 那样的 [a-c]{-}[b-z]。
4. 向前看中的 $ 只表示 '$'，而不再匹配行尾，例如 a/b$ 仅当 "a" 后面是 "b$" 时才匹配 "a"。

二、正则表达式的表示

虽然上面定义了正则表达式的规则，但它们表示起来却很简单，我使用 Cyjb.Compiler.RegularExpressions 命名空间下的 8 个类来表示任意的正则表达式，其类图如下所示：

图 1 正则表达式类图

其中，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 类则是用于正则表达式解析的类，具体的解析算法太过复杂，就不多加解释。

三、正则表达式

正则表达式构造好后，就需要使用它去匹配词素。一