UML软件工程组织
词法分析自动生成器CScanGenner的设计与实现
作者: 谢煜波

现代编译器设计的一个趋势是尽量使用各种自动生成工具来实现编译器的各个部份，其中词法分析器通常是编译器的第一个部份，并且词法分析也广泛应用与各种程序中。现在常用的词法分析器程序有两种：ScanGen以及Lex。

ScanGen是一种表驱动形式的词法分析器，它最后产生的结果不是一个实实在大的词法分析器程序，而是一张转换表，通过这种转换表去驱动真正的词法分析器的运行。举个例子，我们先来想一下我们自己是怎样识别一个单词串的，比如说识别一个C语言的变量名吧：

1. 我们首先看第一个符号是不是下划线或者字母，如果是的话我们就把这个字符加入输出缓冲区，并进入下一步。

2. 继续查看紧跟着的这个符号是不是下划线、字母或数字，如果是我们就把这个字符加入输出缓冲区，并重复这一步，如果是空格我们就进入第三步。

3. 表明变量名定义完成，把输出缓冲区中的内容返回，这就是一个被识别出来的变量名。

上面这个步骤可以用如下的一幅图来表示：

 

上面这张图，我们就称之为状态转换图，用语言可以如下描述：

  • 在状态是1的情况下如果当前输入字符是下划线或字母就转到下一状态2。
  • 在状态是2的情况下如果当前输入字符是下划线、字母、数字就转到下一状态2。
  • 在状态是2的情况下如果当前输入字符是空格则转到下一状态3。
  • 在状态是3的情况下，把输出缓冲区的内容返回，表明一个单词串被识别出来。

从上面的文字描述中我们可以看出，其实决定词法分析器怎么运作的有两个关键因素，一个因素是当前状态，另一个因素是当前的输入字符。现在，我们把当前状态做为行索引，当前字符做为列索引，就得到一张如下的表：

上面这张表就被视为词法分析器的驱动表，这样，我们的词法分析器就有如下一样的很简单的结构：

DRIVER_TABLE M[][];

string buffer;

char ch;

STATE s = 1; // 初始状态为1

while(input.get(ch))

{

s = M[s][ch]; // 进入下一状态

if(s == 2)

{

buffer += buffer;

}

else if(s == 3)

{

return buffer;

}

else

{

printf( "ERROR!" );

}

}

从上面可见，由于有那张词法分析器的驱动表的存在，使得我们的词法分析程序变得非常简单。由于ScanGen生成的结果就是那张驱动表，因此，这还带来另外一个好处，也就是词法分析器的主体程序可以用任何语言书写，而不像Lex，Lex最后生成的结果是实实在在的词法分析器的C/C++程序，因而你不用其它语言来使用Lex。当然ScanGen也有一个弱点，就是转换表所含的信息相对较少，因此，这限制了词法分析器的随意度，它不像Lex那样灵活。

ScanGen最早是由微斯康星大学的一个教授写的，版权属于微斯康星大学，用的语言是Pascal，它可以把用户书写的词法说明文件（这在后面会详细论述）转换成一张驱动表。CScanGenner可以算是ScanGen的一个C++版本，它用C++语言书写的，并且取消了原ScanGen对词法说明文件的一些限制（比如说最大规模，单词串最大长度等），另外，在词法说明文件的描述上支持C风格而不是原来的Pascal风格（最大的一点变化就是大小写相关），另外，CScanGenner是开源软件，你可以在MIT许可协议[1]下随意使用。

本文不是CScanGenner的说明文档，只是描述一下他在实现上的原理及一些实现中的细节问题，关于CScanGenner的详细说明，你可以访问纯C论坛：http://purec.binghua.com或者http://iamxiaohan.nease.net取得。

单词串其实都是通过一种称之为正则表达式的东东定义的，或说可以用正则表达式来描述，比如上面那个例子就可以用如下的一个正则表达式来对其进行描述：

ID := (下划线|字母).(下划线|字母|数字)*;

上面这个就是一个正则表达式，“|”表示“或”关系，“.”表示“连接”关系，“*”表示出现零次或多次，上面的意思就是：下划线或者字母后面，出现零次或多次下划线或者字母或者数字，这个符号串被定义成一个ID（也就是我们常说的变量名）。当然，正则表达式还有“+”：表示出现一次或多次；“？”表示出现零次或一次……等等运算符，有兴趣的可以在网上搜索一下，这里就不详细描述了。

还记得那前面那幅状态转换图么？它同上面的正则表达式其实都是描述的同样一个东东，这就使我们不得不怀疑它们之间是否存在一种转换关系？实际上，形式语言的理论告诉我们：正则表达式是可以转换成为一张转换图的（有限状态机）。我们现在就来看看一这种转换。

正则表达式其实有三种最基本的关系：

  • 一是连接关系：

C = A.B

它可以用如下的方式转换：

这就是正则表达式C所对应的状态图，红色线表示输入可以是epsilon，即可以为空，什么都不做就能非常自由的从一个状态由红线进入到下一个状态。

  • 二是“或”关系：

C = A|B

它可以用如下的方式转换：


三是“*”关系：

C = A*

它可以用如下的方式转换：

另外的关系都可以由这三种关系合成，比如“+”关系：

A+ = A.A*

上面种种表明，我们能找到一种方法，把一个描述词法的正则表达式转换成一张状态表（有限自动机），而状态表可以很简单的转换为我们的二维表（如前所示），这样我们的驱动表就可以产生出来了。不过上面的状态表有这样一个问题：假如存在如下的一张状态表：

上面这个自动机其实等价于：ab|a，但现在问题来了，在状态1下，输入a本来应当是到状态2，但是由于状态1有一根红线到状态3，即在状态1下，可以不输入任何字符自由的到状态3，故而，可以是状态1先到状态3然后在根据输入的a到状态4，也就是说在状态1下，面对输入a，可以到状态2也可以到状态4，如下图一般：

如果是这样的话，那么在状态表中，就会出现一个表格中填入了两个动作，一个动作是到状态2，另一个动作是到状态4，这对于词法扫描程序来说是一个无法处理的事情，因为它不知道是应当按照动作一，还是应按照动作二进行。

上面的状态图反应的一种状态机称之为不确定有限状态机（NDFA），而词法扫描程序处理的必须是确定有限状态机（DFA），因此，必须采用一种算法把一个NDFA转换成一个DFA，有一种算法非常常用，这就是所谓的子集化算法。

首先，我们从状态1开始，对状态1求它的epsilon闭集，即求得所有可以由状态1通过红线（即无需输入字符，或说输入字符为空（epsilon））所能达到的状态的集合。在上例中就是：状态1，状态3。这是需要注意的是，在求的时候应当是一个递归的算法，即状态1能通过epsilon到状态3，那么应当把状态3加入到这个集合中来，随后还要求状态3可以通过epsilon所达到的状态n，这个n也应当加入集合中，因为状态1可以不需要输入字符就能达到状态3，而状态3不需要输入字符就能达到状态n，相当于状态1可以不需要输入字符就能达到状态n，故而，状态n也就加入集合之中。现在我们可以开始构造一个新的状态图：

生成了一个新状态A，它含有原状态1，3。

下面我们考查这个新状态A中的原状态，状态1输入是a时，会转到状态2，原状态3输入是a时会转到状态4，于是我们可以构造一个新的状态B，让它含有状态2及状态4，如下所示：

这时我们就得到了一个确定的东东，即在状态A下输入a时，只能到状态B，这就是一个确定的DFA。在实际的求解过程中，我们还应对B的每个元素就它的epsilon闭集，即，如果2或者4能通过不输入任何字符到达状态m，那么m也应被加入到状态B中。

继续我们的算法，当B中的状态2遇到输入b后，会转到状态4，因此，我们还需构造一个新的状态C，让它含有状态4：

由于原来的NDFA中，状态4是终态，也就是说：在NDFA中，如果状态4出现，即表明当前的输入串（被放在输出缓冲区中的东东）应当被接收（将输出缓冲区中的东东返回）。现在在DFA中，对于状态B来说，它含有NDFA中的终态4，但是也含有非终态2，那么这个输出缓冲区中的东东应不应当返回呢？这就需要由后面的输入决定了，如果后面的输入是b，说明它不应当返回，它还应转到状态C去，因为这其实是到达了原NDFA中的，现在DFA中的状态B中的状态2，如果后面的输入是其它字符，则说明它应当返回了，这其实是到达了原NDFA中的，现在DFA中的状态B中的状态4，真正的终态。这里还可以发现一个很有兴的现象：正则表达式其实是一种最大正向匹配算法，它总是尽力的尝试去匹配更多的输入。

上面描述的其实是形式语言的一些原理性的东东，在任一本形式语言的书或者某些编译原理的书中都会有较为详细的论述，这里只是简单的介绍了一下，用以说明CScanGenner所采用的算法原理，如果对这部份内容想详细了解的朋友，可以参阅相关资料。

上面介绍的就是CScanGenner实现的算法基理，总结一下，说简单一点，就是由用户根据需要用正则表达式编写词法说明文件，然后，CScanGenner根据这些说明文件，把说明文件中的正则表达式先转换成一个一个的NDFA，再把这一个一个的NDFA合在一起当成一个由“或”关系组成的巨大的NDFA，随后对这个巨大的NDFA，应用前述的子集化算法转化成一个巨大的DFA，最后再把这个DFA转换成一张驱动表输出，至此，CScanGenner的工作完成，用户可以使用这张驱动表驱动自己的词法驱动程序。下面我们就来看看这其间的一些实现上的细节问题，当然，由于篇幅有限（最主要的还是认为没有必要），笔者不会完全描述所有的细节，只是对笔者觉得有意义的地方进行一些阐述。其中若有不当之处，欢迎您来信指教，笔者的电子邮箱是: xieyubo@126.com。

CScanGenner所采用的分析方法是最简单的递归下降法，它对每一个语法项的处理都有一个函数进行，关于CScanGenner的语法定义及递归处理函数请参见CScanGenner的源代码。如果你对递归下降的语法处理方法还不太熟悉，请参见本文参考文献一的前两章，它用一个很小而很简单的例子说明了什么是递归下降，怎么编写递归下降的分析程序。这里就不详细描述CScanGenner是怎么使用递归下降的，主要来看看它是怎么进行从正则表达式到NDFA再到DFA的转换的。

首先我们来看看一个只含有两个词法描述，即两个正则表达式的例子:

上面蓝色部份就是正则表达式，而深红色部份是对字符所属类别的定义。正则表达式定义了两个在C语言中常用的词法符号，一个就是单行注释，另一个就是前面已经描述过的标识符。现在我们来主要看看单行注释这个正则表达式是怎么被CScanGenner所翻译的。

CScanGenner在用递归下降法扫描这个正则表达式的时候会边扫描边构造出它的语法树。比如，先扫描了SingleLineComment，于是把这个构造为一个树根：

随后，它用一个函数对整个右边式子进行处理，而这个函数将返回一个指针，由根结点保留住这个指针，类似下面的代码：

RegularExp.pointer = HandleRightExp();

而在HandleRightExp()中，它又会用递归的方式处理它的每个小部份，比如：整个右部会被视为：Slash . Operator2，如下所示：

其中的Operator2就是“Slash . NOT(LineTerminator)*”，随后，系统又会调用函数对Operator2进行处理，如此一步一步的递归下去，最后就得到了如下一棵语法树：

这样，一根语法树就构造出来了，并且，在这棵语法树上，我们保存了这个正则表达式的所有信息，CScanGenner就是这样，把用户输入的正则表达式首先全部转换成了这样的语法树保存在了内存中。

随后，CScanGenner开始将正则表达式转换成NDFA，也即它每棵语法树都转换成一个NDFA。

对于“.”这个连接操作而言，要想生成它的NDFA（还记得前面描述的将正则表达式转换成向应的状态图的方法吗？）必须先要生成它左右两个操作数的NDFA，然后再把这两个NDFA连接起来，因此在这里CScanGenner采用的是“后根遍历”算法来遍历整个语法树，并在遍历的同时生成对应的NDFA，由于一个正则表达式就对应一个语法树，因此，当整个语法树都转换成一个NDFA的时候，这个正则表达式也就转换成了其相应的NDFA。

在前面我们已前描述了怎样把由“.”（连接）、“*”（闭集）、“|”（或）关系组合的两个NDFA合成一个NDFA，现在我们来看一看对于叶结点（如上图的“Slash”结点）怎么转换成一个NDFA。其实这非常简单，让我们用下面一幅图来说明：

上图中还有一个NOT（非）关系，它可以是如下的格式：

NOT(A, B, C, … )

对于上面这种“非”关系，在CScanGenner中是把它转换成一个大的“|”（或）关系来处理的，首先，它把所有的类别都加入一个集合中，然后，再把NOT括号中涉及到的类别从集合中删除，这样就得到了一个许可集合，然后，按照“|”（或）关系，把这个集合中所有的元素（当然，每个元素会以产生“Slash”的NDFA一样的方式先产生一个NDFA）产生的NDFA组合成一个NDFA。

现在我们来看看CScanGenner中是用怎样一种结构来表示一个NDFA的。从状态转换图上我们可以直观的看到一个NDFA由若干个状态（即图中的小圈）组成，每一个状态还有一定数量的转换边，而每一个转换边上还绑定着一个输入字符，并且，每个转换边还指出了通过它可以达到的状态。

在CScanGenner中，首先定义了一个名为：struct_transEdge的结构来表示转换表：

struct struct_transEdge

{

int classNum;

int nextState;

enum_tossSaveFlag tossSaveFlag;

};

其中classNum指明了绑定在这条转换边上的输入字符，nextState指明了这条转换边指向的状态，tossSaveFlag这个标志在后面会有详细描述，这里暂时不用理会它。

接着，CScanGenner定义了一个名为：struct_triple的结构来表示NDFA中的一个状态：

struct struct_triple

{

int transEdgeNum;

struct_transEdge transEdge1;

struct_transEdge transEdge2;

};

从这个结构上我们可以看见，在CScanGenner中的每个NDFA的状态最多含有两个转换边，这主要是为了方便处理，那两条转换边是不是就足够了呢？如果遇见下面的情况怎么办：

这种情况其实可以加入epsilon转换边（即前面的状态图中所使用的红色边，它表示可以不需要任何输入即能在两个状态之前自由转换）及辅助状态来保证每个状态最多有两个转换边，如上面的状态图可转换为：

一个正则表达示所对应的NDFA，其实就是一个struct_triple元素组成的数组，这样我们就把用户输入的正则表达式转换成了一个一个的NDFA，也即一个一个的由struct_triple元素组成的数组。

接下来，我们就应当把所有的这些NDFA转换成一个DFA了。系统把所有的这些NDFA（每一个正则表达式对会产生一个NDFA）看做是由或关系组成的一个巨大的NDFA，如下图所示：


然后，用本文开头所描述的子集化方法，把所有的NDFA转换成了DFA，最后，把这DFA输出为一张状态表，CScanGenner的任务也就完成了。

上面描述的东东就是整个CScanGenner的核心算法及实现方式，至于更详细的内容请参看CScanGenner的源代码，其中有很详细的注释。

下面我们来谈谈这其中可能会遇到的一些问题，及CScanGenner对之的处理方式。对于这些问题，如果您有更好的处理方式的话，请来信告诉我。

第一个问题，我们来看看如果用户有两个正则表达式可以匹配一个输入，比如对于正则表达式：a|ab*，它的状态图如下所示：

在这种情况下，如果我们仍用前面的子集化方法，那么得到的DFA的状态转换图就如下所示：

现在问题出来了，看上图的第二个状态，它含有原NDFA中的状态2、3。在原来的NDFA中，状态2、3都是终态，因此上图的第二个状态所对应的终态到底应当是原NDFA中状态2所对应的终态还是状态3所对应的终态呢？这就起了冲突，也即，如果用户的词法描述文件中有类式的情形：

TOKEN A = a;

TOKEN B = ab*;

那么，CScanGenner在最后产生出的DFA中就会发现有一个状态包含了两个NDFA中的终态，这就说明一个输入可以被两个正则表达式进行匹配，对于这种情况，CScanGenner会直接输出错误信息。

还有一个问题是由{TOSS}指示符引起的。CScanGenner继承了原ScanGen的一个特点，就是可以使用一个称之为{TOSS}的指示符，这个指示符会指示当前的输入字符不被加入到输出缓冲区中，这在某些时候是非常有用的，比如，下面一个正则表达式：

Slash = ‘\’;

Quote = ‘”’;

TOKEN A = Slash{TOSS} . Quote;

上面这个正则表达式可以匹配一个转义符与引号连用的情况（\“），在这种情况下，由于Slash后面有{TOSS}因此，Slash符号(\)就不被加入输出缓冲区中，这样最后返回给用户的TOKEN就是单纯的Quote(“)了。再比如在对字符串就是匹配时，我们可以在正则表达式中对开头与结尾的两个引号后加上{TOSS}标志，这样只有字符串的内容可以被返回给用户串，而字符串开头与结尾的引号就不会返回给用户了。

但是{TOSS}标记符的滥用也会导致一些问题，比如看下面的一个正则表达式：

a{TOSS}b|ac

它的意思是如果输入是ab的话就不返回前面的a，如果是ac的话就原样返回a（不进行TOSS操作），这个正则表达式的状态图如下所示：

现在我们用子集化的方式把它转换成DFA：

问题就出来了，对于那个a，我是应当加入{TOSS}还是不应当加入{TOSS}呢？这就起了冲突。对于出现这种情况，目前的CScanGenner的解决之道就是简单的将其做为一种错误给报告出来。

这里还需要把前面的一个遗留问题提一下，在支持{TOSS}指示符后，每个转换边又多了一个属性来保存这个转换边上是否使用了{TOSS}指示符，还记得前面描述转换边的结构体：struct_transEdge中有一个tossSaveFlag标志吗？

CScanGenner是一个开源的软件，目前它已经几个项目中实际运用了，但是他还不是一个很完善的东东，比如说它最后生成的DFA还没有优化，不是最简DFA，另外前面所谈到的问题的解决方式还比较初级。非常欢迎您能对CScanGenner进行开发与完善，也欢迎您在您的项目中自由的使用这个工具（当然，需要您遵守MIT许可协议:），你可能访问http://purec.binghua.com或者http://project.iamxiaohan.binghua.com获得关于它的全部源代码及其余资源。
　
版权所有：UML软件工程组织