正则表达式DFA构造方法

陈梓瀚 vczh@163.comhttp://www.cppblog.com/vczh/

1、问题概述

随着计算机语言的结构越来越复杂，为了开发优秀的编译器，人们已经渐渐感到将词法分析独立出来做研究的重要性。不过词法分析器的作用却不限于此。回想一下我们的老师刚刚开始向我们讲述程序设计的时候，总是会出一道题目：给出一个填入了四则运算式子的字符串，写程序计算该式子的结果。除此之外，我们有时候建立了比较复杂的配置文件，譬如XML的时候，分析器首先也要对该文件进行词法分析，把整个字符串断成了一个一个比较短小的记号(指的是具有某种属性的字符串)，之后才进行结构上的分析。再者，在实现某种控制台应用程序的时候，程序需要分析用户打进屏幕的命令。如果该命令足够复杂的话，我们也首先要对这个命令进行词法分析，之后得到的结果会大大方便进行接下去的工作。

当然，这些问题大部分已经得到了解决，而且历史上也有人做出了各种各样专门的或者通用的工具(Lex、正则表达式引擎等)来解决这一类问题。我们在使用这种工具的时候，为了更加高效地书写配置，或者我们在某种特殊情况下需要自己制作类似的工具，就需要了解词法分析背后的原理。本文将给出一个构造通用词法分析工具所需要的原理。由于实现的代码过长，本文将不附带实现。

究竟什么是“把一个字符串断成一些记号”呢？我们先从四则运算式子入手。一个四则运算式子是一个字符数列，可是我们关心的对象实际上是操作符、括号和数字。于是此法分析的作用就是把一个字符串断开成我们关心的带有属性的记号。举个例子：(11+22)*(33+44)是一个合法的四则运算式子，如果输入是(左括号,”(“) (数字,”11”) (一级操作符,”+”) (数字,”22”) (右括号,”)”) (二级操作符,”*”) (左括号,”33”) (一级操作符,”44”) (右括号,”)”)的话，我们在检查结构的时候只需要关心这个记号的属性(也就是左括号、右括号、数字、操作符等)就行了，具体计算的时候才需要关心这个记号实际上的内容。如果式子里边有空格的话，我们也仅仅需要把空格当成是一种记号类型，在词法分析得出结果之后，将具有空格属性的记号丢弃掉就可以了，接下去的步骤不需变化。

但需要注意的是，词法分析得到的结果是没有层次结构的，所有的记号都是等价的对象。我们在计算表达式的时候把+和*看成了不同层次的操作符，类似的结构是具有嵌套的层次的。词法分析不能得出嵌套层次结构的信息，最多只能得到关于重复结构的信息。

2、正则表达式

我们现在需要寻找一种可以描述记号类型的工具，在此之前我们首先研究一下常见的记号的结构。为了表示出具有某种共性的字符串的集合，我们需要书写出一些能代表字符串集合的规则。这个集合中的所有成员都将被认为是一种特定类型的记号。

首先，规则可以把一个特定的字符或者是空字符串认为是一种类型的记号的全部。上文所说到的四则运算式子的例子，“左括号”这种类型的记号就仅仅对应着字符”(“，其他的字符或者字符串都不可能是“左括号”这个类型的记号。

其次，规则可以进行串联。串联的意思是这样的，我们可以让一个字符串的前缀符合某一个指定的规则，剩下的部分的前缀符合第二个规则，剩下的部分的前缀符合第三个规则等等，一直到最后一个部分的全部要符合最后一个规则。如果我们把”function”这个字符串作为一个记号类型来处理的话，我们可以把”function”这个字符串替换成8个串联的规则：”f”,”u”,”n”,”c”,”t”,”i”,”o”,”n”。首先，字符串”function”的前缀”f”符合规则”f”，剩下的部分”unction”的前缀”u”符合规则”u”，等等，一直到最后一个部分”n”的全部符合规则”n”。

第三，规则可以进行并联。并联的意思就是，如果一个字符串符合一系列规则中的其中一个的话，我们就说这个字符串符合这一些规则的并联。于是这些规则的并联就构成了一个新的规则。一个典型的例子就是判断一个字符串是否关键字。关键字可以是”if”，可以是”else”，可以是”while”等等。当然，一个关键字是不可能同时符合这些规则的，不过只要一个字符串符合这些规则的其中一个的话，我们就说这个字符串是关键字。于是，关键字这个规则就是”if”、”else”、”while”等规则的并联。

第四，一个规则可以是可选的。可选的规则实际上是属于并联的一种特殊形式。加入我们需要规则”abc”和”abcde”并联，我们会发现这两个规则有着相同的前缀”abc”，而且这个前缀恰好就是其中的一个规则。于是我们可以把规则改写成”abc”与””和”de”的并联的串联。但是规则””指定的规则是空串，因此这个规则与”de”的并联就可以看成是一个可选的规则”de”。

第五，规则可以被重复。有限次的重复可以使用串联表示，但是如果我们不想限制重复的次数的话，串联就没法表示这个规则了，于是我们引入了“重复”。一个典型的例子就是程序设计语言的标识符。标识符可以是一个变量的名字或者是其他东西。一门语言通常没有规定变量名的最大长度。因此为了表示这个规则，就需要将52个字母进行并联，然后对这个规则进行重复。

上述的5种构造规则的方法中，后面的4个方法被用于把规则组合成为更大的规则。为了给出这种规则的形式化表示，我们引入了一种范式。这种范式有以下语法：

1：字符用双引号包围起来，空串使用ε代替。

2：两个规则头尾连接代表规则的串联。

3：两个规则使用 | 隔开代表规则的并联。

4：规则使用[]包围代表该规则是可选的，规则使用{}包围代表该规则是重复的。

5：规则使用()包围代表该规则是一个整体，通常用于改变操作符 | 的优先级。

举个例子，一个实数的规则书写如下：

{“0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”}”.”[{“0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”}]。

但是，我们如何表示“不是数字的其他字符呢”？字符的数量是有限的，因此我们可以使用规则的并联来表示。但是所有的字符实在是太多（ASCII字符集有127个字符，UTF-16字符集有65535个字符），因此后来人们想出了各种各样的简化规则书写的办法。比较著名的有BNF范式。BNF范式经常被用于理论研究，但是更加实用的是正则表达式。

正则表达式的字符不需要用双引号括起来，但是如果需要表示一些被定义了的字符(如 “|” )的话，就使用转义字符的方法表示(如 “/|”)。其次，X?代表[X]，X+代表{X}，X*代表[{X}]。字符集合可以用区间来表示，[0-9]可以表示“0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”，[^0-9]则表示“除了数字以外的其他字符”。正则表达式还有各种各样的其他规则来简化我们的书写，不过由于本文并不是“精通正则表达式”，因此我们只保留若干比较本质的操作来进行词法分析原理的描述。

正则表达式的表达能力极强，小数的规则可以使用[0-9]+.[0-9]来表示，C语言的注释可以表示为//*([^/*]|/*+[^/*/])*/*+/来表示。

3、有穷状态自动机

人阅读正则表达式会比较简单，但是机器阅读正则表达式就是一件非常困难的事情了。而且，直接使用正则表达式进行匹配配的话，不仅工作量大，而且速度缓慢。因此我们还需要另外一种专门为机器设计的表达方式。本文在以后的章节中会给出一种算法把正则表达式转换为机器可以阅读的形式，就是这一章节所描述的有穷状态自动机。

有穷状态自动机这个名字听起来比较可怕，不过实际上这种自动机并没有想象中的那么复杂。状态机的这种概念被广泛的应用在各种各样的领域中。软件工程的统一建模语言(UML)有状态图，数字逻辑中也有状态转移图。不过这些各种各样的图在本质上都跟状态机没有什么区别。我将会通过一个例子来讲述状态的实际意义。

假设我们现在需要检查一个字符串中a的数量和b的数量是否都是偶数。当然我们可以用一个正则表达式来描述它。不过对于这个问题来说，用正则表达式来描述远远不如构造状态机方便。我们可以设计出一个状态的集合，然后指定集合中的某一个元素为“起始状态”。其实状态就是在工作还没开始的时候，分析器所处的状态。分析器在每一次进行一项新的工作的时候，都要把状态重置为起始状态。分析器每读入一个字符就修改一次状态，修改的方法我们也可以指定。分析器在读完所有的字符以后，必然停留在一个确定的状态中。如果这个状态跟我们所期望的状态一致的话，我们就说这个分析器接受了这个字符串，否则我们就说这个分析器拒绝了这个字符串。

如何通过设计状态及其转移方法来实现一个分析器呢？当然，如果一个字符串仅仅包含a或者b的话，那么分析器的状态只有四种：“奇数a奇数b”、“奇数a偶数b”、“偶数a奇数b”、“偶数a偶数 b”。我们把这些状态依次命名为aa、aB、Ab、AB。大写代表偶数，小写代表奇数。当工作还没开始的时候，分析器已经读入的字符串是空串，那么理所当然的起始状态应当是AB。当分析器读完所有字符的时候，我们期望读入的字符串的a和b的数量都是偶数，那么结束的状态也应该是AB。于是我们给出这样的一个状态图：

图3.1

检查一个字符串是否由偶数个a和偶数个b组成的状态图

在这个状态图里，有一个短小的箭头指向了AB，代表AB这个状态是初始状态。AB状态有粗的边缘，代表AB这个状态是结束的可接受状态。一个状态图的结束状态可以是一个或者多个。在这个例子里，起始状态和结束状态刚好是同一个状态。标有字符”a”的箭头从AB指向aB，代表如果分析器处于状态AB并且读入的字符是a的话，就转移到状态aB上。

我们把这个状态图应用在两个字符串上，分别是”abaabbba”和”aababbaba”。其中，第一个字符串是可以接受的，第二个字符串是不可接受的(因为有5个a和4个b)。

分析第一个字符串的时候，状态机所经过的状态是：

AB[a]aB[b]ab[a]Ab[a]ab[b]aB[b]ab[b]aB[a]AB

分析第二个字符串的时候，状态机所经过的状态是：

AB[a]aB[a]AB[b]Ab[a]ab[b]aB[b]ab[a]Ab[b]AB[a]aB

第一个字符串”abaabbba”让状态机在状态AB上停了下来，于是这个字符串是可以接受的。第二个字符串”aababbaba”让状态机在状态aB上停了下来，于是这个字符串是不可以接受的。

在机器内部表示这个状态图的话，我们可以使用一种比较简单的方法。这种方法仅仅把状态与状态之间的箭头、起始状态和结束状态集合记录下来。对应于这个状态图的话，我们就可以把这个状态图表示成以下形式：

起始状态：AB

结束状态集合：AB

(AB,a,aB)

(AB,b,Ab)

(aB,AB)

(aB,ab)

(Ab,AB)

(ab,Ab)

(ab,aB)

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!