typeof.net

原文地址： http://www.cnblogs.com/Ninputer/archive/2011/06/08/2075714.html

从今天这一篇起，我们就来正式揭开编译器的奥秘。首先我们接触到的模块是词法分析器，也叫词法扫描器，代码里我常常叫它 Scanner。昨天我稍微解释了一下为什么需要将词法分析单独分离出来，今天来回顾一下这个问题。请看下面这段 C# 代码：

string str = "Hello World";

即使没有语法高亮，这段代码也可以很明显地分成好几部分。首先是关键字 string ，之后是变量名 str ，然后是等号 = ，接下来是一个字符串字面常量 "Hello World" 。现代语言如 C# 这样的，都能明显地将源代码分断成这样具有明确含义的片段，我们称之为词素 (lexeme) 。与描述整个 C# 语言的语法相比，我们用比较简单的规则就能描述不同类型的词素。比如上面这段代码中出现的词素用白话来描述的话就是：

我们看到，不同词素可以根据其特征划分到 a 几个类型当中，而接下来的语法分析阶段，就可以直接以词素的类型——我们称之为单词 (token) ——作为输入。 token 有时候也翻译成令牌、记号、象征什么的，在本文中统一称为单词。如此可见，只要用相对简洁的规则，就能把原本字符串组成的源文件，分解为一串单词流，这样就能大大简化接下来的语法分析。这就是我们把词法分析单独分出来作为一个模块的根本原因。

不过，上面表格中所列的规则是用白话来描述的，我们希望能用一种形式化的语言来进行描述，以便计算机自动进行处理。正则表达式就是一个理想的选择。

大家日常编程中估计多多少少都接触过正则表达式，用它来匹配字符串等，也可能已经很熟悉其语法了。但我这次想从正则表达式的最基本概念来重新介绍一次，主要想让大家更深地理解它。首先我们要重新定义一下“语言”这个概念。“语言”就是指字符串的集合，其中的字符来自于一个有限的字符集合。也就是说，语言总要定义在一个有限的字符集上，但是语言本身可以既可以是有穷集合，也可以是无穷集合。比如“C# 语言”就是指满足 C# 语法的全体字符串的集合，它显然是个无穷集合。当然也可以定义一些简单的语言，比如这个语言 { a } 就只有一个成员，那就是一个字母 a。后面我们都用大括号 { } 来表示字符串的集合。所谓正则表达式呢，就是描述一类语言的一种特殊表达式，正则表达式共有 2 种基本要素：

1. 表达式 ε 表示一个语言，仅包含一个长度为零的字符串，可以理解为 {String.Empty} ，我们通常把 String.Empty 记作 ε ，读作 Epsilon (Έψιλον) 。
2. 对字符集中任意字符 a，表达式 a 表示仅有一个字符 a 的语言，即 { a } 。

同时正则表达式定义了 3 种基本运算规则：

1. 两个正则表达式的并，记作 X|Y ，表示的语言是正则表达式 X 所表示的语言与正则表达式 Y 所表示语言的并集。比如 a|b 所得的语言就是 {a, b} 。类似于加法
2. 两个正则表达式的连接，记作 XY ，表示的语言是将 X 的语言中每个字符串后面连接上 Y 语言中的每一种字符串，再把所有这种连接的结果组成一种新的语言。比如令 X = a|b ， Y = c|d ，那么 XY 所表示的语言就是 {ac, bc, ad, bd} 。因为 X 表示是 {a, b} ，而 Y 表示的是 {c, d} ，连接运算取 X 语言的每一个字符串接上 Y 语言的每一个字符串，最后得到了 4 种连接结果。这类似于乘法
3. 一个正则表达式的克林闭包，记作 X* ，表示分别将零个，一个，两个……无穷个 X 与自己连接，然后再把所有这些求并。也就是说 X* = ε | X | XX | XXX | XXX | … 。比如 a* 这个正则表达式，就表示的是个无穷语言 {ε, a, aa, aaa, aaaa, … } 。这相当于任意次重复一个语言。

以上三种运算写在一起时克林闭包的优先级高于连接运算，而连接运算的优先级高于并运算。以上就是正则表达式的全部规则！并不是很难理解对吧？下面我们用正则表达式来描述一下刚才各个词素的规则。 首先是关键字 string，刚才我们描述说它是“正好是 s-t-r-i-n-g 这几个字母按顺序组成”，用正则表达式来表示，那就是 s-t-r-i-n-g 这几个字母的连接运算，所以写成正则表达是就是 string。大家一定会觉得这个例子很无聊……那么我们来看下一个例子：标识符。用白话来描述是“由字母开头，后面可以跟零个或多个字母或数字”。先用正则表达式描述“由字母开头”，那就是指，可以是 a-z 中任意一个字母来开头。这是正则表达式中的并运算： a|b|c|d| …… x|y|z 。如果每个正则表达式都这么写，那真是要疯掉了，所以我们引入方括号语法，写在方括号里就表示这些字符的并运算。比如 [abc] 就表示 a|b|c 。而 a-z 一共 26 个字母我们也简写成 a-z，这样，“由字母开头”就可以翻译成正则表达式 [a-z] 了。接下来我们翻译第二句“后面可以跟零个或多个字母或数字”这句话中的“零个或多个”可以翻译成克林闭包运算，最后相信大家都可以写出来，就是 [a-z0-9]* 。最后，前后两句之间是一个连接运算，因此最后描述标识符“语言”的正则表达式就是 [a-z][a-z0-9]* 。其中的 * 运算也意味着“标识符”是一种无穷语言，有无数种可能的标识符。本来就是这样，很好理解对吧？ 从上面例子可以看出，正则表达式都可以用两种要素和三种基本运算组合出来。但是如果我们要真的拿来描述词法单词的规则，需要一些便于使用的辅助语法，就像上边的方括号语法那样。我们定义一些正则表达式的扩展运算：

• 方括号表示括号内的字符并运算。 [abc] 就等于 a|b|c
• 方括号中以 ^ 字符开头，表示字符集中，排除方括号中的所有字符之后，所剩字符的并运算。 [^ab] 就表示除了 ab 以外所有字符求并。
• 圆点表示字符集内所有字符的并。因此 .* 这个表达式就能表示这种字符集所能组成的一切字符串。
• X? 表示 X|ε 。表示 X 与空字符串之间可选。
• X+ 表示 XX* 。这等于限制了 X 至少要重复 1 次。

用过正则表达式的同学应该都熟悉以上运算了。其实 .NET 中的正则表达式还提供更多的扩展语法，但我们这次并不使用 .NET 的正则库，所以就不列出其余的语法了。 我们把所有能用正则表达式表示的语言称作正则语言。很遗憾，并非所有的语言都是正则语言。比如 C#，或者所有编程语言、 HTML、 XML、 JSON 等等，都不是正则语言。所以不能用正则表达式定义上述语言的规则。但是，用正则表达式来定义词法分析的规则却是非常合适的。大部分编程语言的词素都可以用一个简单的正则表达式来表达。下面就是上述单词的正则表达式定义。

我们大家平时熟悉的正则表达式是写成上文这样的字符串形式。但这次我们要自己处理正则表达式，写成字符串显然增加了处理的难度 (要解析正则表达式字符串) 。所以在 VBF.Compilers 库的词法分析库中，我引入了一种用对象来表示正则表达式的手法。我定义了一个 RegularExpression 基类，然后为每一种正则表达式要素或运算编写了一个子类：

其中 AlternationExpression 就是“并”运算， ConcatenationExpression 就是“连接”运算， EmptyExpression 当然就表示 ε 空字符串， KleeneStarExpression 表示“克林闭包”运算 (你现在可以知道克林闭包也可以叫做克林星——本来就是一星号嘛) 和表示单一字符的 SymbolExpression。像 SymbolExpression 里面其实就储存了它所表示的一个字符，而 AlternationExpression 下面储存了两个 RegularExpression 实例，用来表示并运算的双方。所以，任何正则表达式都能用 RegularExpression 的对象树来表示。比如正则表达式 [a|b]* 就可以表示为：

RegularExpression re = new KleeneStarExpression(
    new AlternationExpression(
        new SymbolExpression('a'), new SymbolExpression('b')));

有点像 Linq to XML 有木有？虽然它写起来比字符串长了那么一点点 (观众：是长好多吧……)，但是我们不需要解析字符串就可以获得它的结构，这对下一步进行处理非常有帮助。好吧，我承认全都写这么长也受不了，所以我定义了一些辅助的静态方法和运算符重载。上面的正则表达式可以写成：

var re = (RE.Symbol('a') | RE.Symbol('b')).Many();

其中 RE 其实是要 using RE=VBF.Compilers.Scanners.RegularExpression 语句来声明的别名。虽然它还是比字符串的正则表达式长一些，但考虑到无需解析字符串带来的方便，就忍了吧。等到后面语法分析学习完了以后我会带大家自己开发正则表达式字符串的解析器。 接下来的问题是，怎么用正则表达式表示的规则来进行词法分析呢？正则表达式利于我们理解单词的规则，但并不能拿来直接解析字符串。为此我们要引入有穷自动机的概念来真正处理输入字符串。敬请期待下一篇。

同时大家别忘了关注 VBF 项目： http://github.com/Ninputer/VBF 和我的微博： @ninputer 多谢大家支持！