六、使用正则表达式构造词法分析器

判断一个字符串是否属于某规则的算法介绍到这里就结束了。回到我们一开始的问题上，我们需要使用一些规则来吧一个长的字符串断开成记号，然后计算出每一个记号对应的规则。在解决这个问题之前，我们先考察一下能够成功地被词法分析器接受的字符串应该是什么样子的。

假设我们现在有规则A、B、C和D，分别对应于四种记号类型，那么被词法分析器接受的字符串就是A、B、C和D的任意组合，也就是(A|B|C|D)*。如果规定了输入的字符串不能为空的话，那么被词法分析器接受的字符串就是(A|B|C|D)+。但是单纯地使用(A|B|C|D)+作为一个规则去应用在输入的字符串的话，我们只能够判断字符串是否是词法分析器能够接受的字符串。因此我们需要对这个方法进行修改。

首先按照上文的方法，把每一个记号类型对应的规则的正则表达式转换成DFA，然后使用并联的方法将他们组合起来，但是并不使用“重复”。但是这次我们要做一点修改，我们要把新的DFA的每一个状态对应的规则的DFA状态集合记住。

这里给出一个例子，我们假设需要一个简单语言的词法分析器，规则如下：

I：[a-zA-Z_][a-zA-Z_0-9]*

N：[0-9]+

R：[0-9]+.[0-9]+

O：[=>+-*/|&]

按照规则构造出四个DFA并将它们组合起来：

 

图6.1

我们构造出了I|N|R|O的DFA，并且标识出了哪些状态包含了原DFA的结束状态。这样做的一个好处是，当我们把一个字符串放进这样的一个DFA之后，我们就一直等待整个字符串被接受，或者失败。如果字符串被接受的话，我们就把当前的结束状态记下来。如果失败的话，我们就把这个状态机在分析字符串的时候经过的最后一个结束状态记下来。这个时候，结束状态所代表的原DFA结束状态的相应记号类型就是我们所需要的信息了。如果得不到任何结束状态的话，输入的字符串就是不背词法分析其接受的。

举个例子，使用上述状态机分析”123.ABC”。

首先从状态0开始，依次经过状态N N N 2，然后宣告失败。最后一个N(结束状态)以及当时被接受的字符串”123”被识别，结果为(N，”123”)。然后从”.ABC”开始，输入第一个记号就失败了，于是”.”被识别为不可接受字串。最后输入”ABC”，依次经过状态0 1 I I，然后字符串结束并且被接受，于是输出(I，”ABC”)。

为什么我们在构造状态机的时候不使用“重复”呢？因为在每一个记号被识别出的时候，我们都要做一些额外的工作。如果我们使用“重复”来构造词法分析器的状态机，我们将无从知道一个记号被识别出来的确切时间。

算法到这里基本上就结束了，不过还存在一些小问题需要在细节上解决。一般来说我们给出的一些构成词法分析器的规则很少有冲突，不过偶尔会出现两个规则所代表的字符串集合存在交集的情况。有了DFA这个工具，我们可以很轻易地识别出规则冲突。

假如我们的词法分析器有A和B两个状态，那么我们构造词法分析器A|B的时候，将会得到一些包含DFA(A)和DFA(B)的结束状态的新状态。我们只需要检查这些状态是否具有以下特征，就可以判断A和B的关系。我们假设DFA(A)为规则A的状态机，DFA(B)为规则B的状态机，DFA(L)为词法分析器A|B的状态机：

1：如果DFA(L)存在一个或多个状态同时包含了DFA(A)和DFA(B)的结束状态，那么A和B所代表的字符串存在交集。

2：如果DFA(L)不存在同时包含了DFA(A)和DFA(B)的结束状态的状态，那么A和B所代表的字符串不存在交集。

3：如果DFA(L)的某些状态包含了DFA(A)的结束状态，并且这些状态都无一例外地包含了DFA(B)的结束状态的话，那么A是B的子集。

4：如果DFA(L)的某些状态包含了DFA(A)的结束状态，但是这些状态并没有无一例外地包含DFA(B)的结束状态的话，那么A不是B的子集。

在图6.1的词法分析器中，我们可以很清楚地看出I、N、R和O四个规则两两之间都不存在交集。我们可以尝试构造一个冲突的规则，并看一看词法分析器的DFA是什么样子的：

假设词法分析器包含以下规则：

A：”if”

B：[a-z]+

对A|B构造DFA，我们将会得到如下状态机：

七、尾声

使用DFA的方法完成的可配置词法分析器的性能是相当好的。笔者前不久曾经做过实验，首先使用本文提到的算法开发一个这样的词法分析器，然后在一份C++代码(这份代码经过多次复制而成件，一共有3.12M)中抽取所有数字、标识符和注释，吞吐速度高达46万记号/秒（笔者的台式电脑配置是奔腾4的超线程2.99GHz处理器，1G内存），其中抽取出来的记号一共有22万个。在分析的过程中，只有10%的时间花在了DFA上，90%的时间花在了处理结果的工作上。DFA本身造成的消耗是很小的。不过词法分析的性能在很大程度上跟DFA的实现有很大关系。三个月前笔者也实现过一个同类的程序，但是吞吐速度仅有1.1万记号/秒。

一般来说，比较高性能的DFA的实现是一张二维的表。行代表字符，列代表DFA的状态，单元格代表该状态经输入某个字符之后进行转移的目标状态。此外还有一张表用来记录哪些状态对应哪些规则的结束状态。笔者的词法分析器是基于UTF-16编码的字符串，一张表一共有65535行显然是不现实的，因此还有另一张表把字符转换成字符类。字符类是这样定义的：假设现在已经存在了65535行的一张大表，如果在某个字符区间所对应的子表内，任意一列的单元格的数据都一样的话，那么这个区间内的所有字符就可以被视为是等价的，这些字符就属于同一个字符类。于是仅需要另外一张65535个单元的表用来把一个字符映射到字符类。这种做法可以大大的压缩DFA所需要的空间。在笔者的程序里，识别字符类的算法被融入了DFA的构造算法中

参考文献

【1】：Alfred V.Aho Ravi Sethi Jeffrey D.Ullman ，Compilers Principles , Techniques , and Tools

【2】：Dick Grune Ceriel Jacobs ，Parsing Techniques ---- A Practical Guide

【3】：Kenneth C.Louden ，Compiler Construction Principles and Practice