一个编译器的实现（02）——词法分析(1.正则转NFA)

词法分析概述

词法分析是编译的第一阶段。词法分析器的主要任务是读入源程序的输入字符、将它们组成词素，生成并输出一个词法单元序列，每个词法单元对应于一个词素。这个词法单元序列被输出到语法分析器进行语法分析。

例如，有如下程序（我们以一段简单的PL/SQL语句为例）：

IF C_N > 0 THEN
    INSERT INTO TAB(CLN1, CLN2)
    VALUES(5, 'abc');
END IF;

对它进行词法分析，其输出大概是这样的：

IF       C_N      >        0        THEN

INSERT   INTO     TAB      (        CLN1

,        CLN2     )        VALUES   (

5        ,        'abc'    )        ;

END      IF       ;

一般来说，我们在分析词素的同时还会同时记录下这些词素所在的行、列以便输出错误信息供用户查看，也会同时记录词素的类型。

识别词法的过程是用DFA实现的，DFA是类似于下图所表示的东西（其实就是一个状态转换图）：

这个DFA只能处理IF、INSERT、INTO三个词，它的运行过程大至描述如下：

1. 声名一个变量（s）用来保存当前的状态。
2. 把开始状态（开始状态就是图中的实心圆点儿）负值给s。
3. 从字符流中读一个字符（c），如果读不出字符就终止算法。
4. s的边上有字符，就代表s输入这个字符之后可以沿着这个边走到下一个状态。此时看一下s输入c可以到哪个新状态里去。如果不能到到达一个新状态，则说明这个DFA不能解析这个字符流（到此终止算法），否则s的值变成新的状态。
5. 看一下s是否为终止状态（也叫接受状态，图中用带白边的圆点儿表示），如果是终止状态，则解析到一个字符，然后回到第2步，如果不是终止状态，则回到第3步。

差不多就是这样的，实际情况比上面所说的要稍复杂一点（比如冲突解决、匹配原则），后面会详细讲。

这个DFA只能识别三个单词，实际的编译器中肯定是要能识别一个语言中所有的词素，那样一个DFA是很庞大的，如何去来概造这个完整的DFA也是后面要讲的内容。

正则表达式转NFA

正则表达式是什么？这个问题不在这里详述。上网搜一下，很快就能了解基本概念。有一本书《精通正则表达式》，这本书第一章（20多页）看完就会写基本的正则表达式了。其电子版在网上有下载。

直接做一个可以识别一个语言所有词素的DFA是非常困难的，而且即使做出来，日后的修改同样非常麻烦。而用正则表达式（正则文法）来描述词素就简单得多，同时日后这个语言要修改或增加新的词素都很简单。所以现在的词法分析器的构造方式都是先用一种基于正则文法的语言来描述所有词素，再把这一描述转换成DFA。正则文法转DFA的常规方法是需要一个中间过程的，即先把正则文法的描述转成NFA，而从NFA到DFA的转换方法是存在的。

下面关于FA和NFA的描述是抄袭AMRJ2010[1]的：

转换的核心是被称为有穷自动机(finite automata)的表示方法。这些自动机在本质上是与状态转换图类似的图，但有如下几点不同：

• 有穷自动机是识别器，它们只能对每个可能的输入串简单的回答“是”或“否”。
• 有穷自动机分为两类：
1. 不确定有穷自动机(Nondeterministic Finite Automata, NFA)对其边上的标号没有任何限制。一个符号标记离开同一状态的多条边，并且空串ε也可以做为标号。
2. 对于每个状态及自动机输入字母表中的每个符号，确定的有穷自动机(Deterministic Finite Automata, DFA)有且只有一条离开该状态、以该符号为标号的边。

确定的和不确定的有穷自动机能识别的语言的集合是相同的。事实上，这些语言的集合正好是能够用正则表达式描述的语言的集合。这个集合中的语言称为正则语言(regualr language)。

一个不确定的有穷自动机(NFA)由以下几个部分组成：

1. 一个有穷的状态集合S。
2. 一个输入符号集合Σ，即输入字母表(input alphabet)。我们假设代表空串的Ɛ不是Σ中的元素。
3. 一个转换函数(transition function)，它为每个状态和Σ∪{Ɛ}中的每个符号都给出了相应的后继状态(next state)的集合。
4. S中的一个状态s0被指定为开始状态，或者说初始状态。
5. S中的一个子集F被指定为接受状态（或者说终止状态的）集合。

一个NFA的样子，如下图（NFA图可以有多种表示，下图是其中一种）：

这个NFA与前面的DFA表示同样的逻辑，也是只能识别IF、INTO、INSERT三个单词，那么如果用这个NFA去解析字符流是如何运行的呢？

其运行过程与DFA有只有两点不同：

1. NFA中存在Ɛ，这个在DFA中没有。这个边在运行时不需要从字符流中读字符，是无条件走的。
2. NFA中的状态可能存在多个边接受相同的输入，这时的运行流程可以认为是从这个状态开始分成多条路，每条路分别走，互相不影响。到最后，可能有的路走不通，那就不理那个走不通的，有几条走通了，那就在所有走通的路中看一下哪条路最长（识别的词素字符数最多），就选择这条路，如果有多条路是一样长的，那就做某种约定，例如：哪条路在上面就选择哪条。

除这两点之外，其它的都与DFA是一样的。

正则表达式如何转换为NFA呢？有几个公式(MLS2007[1])：

公式1：如果一个正则表达式只有一个字符'a'，那么NFA如下图：

即：从开始状态，输入一个字符a，就到达了接受状态。

公式2：如果一个正则表达式是两个表达式连成的，如ab，那么NFA如下图：

即：从开始状态，输入a，到达状态1，再输入b到达接受状态。这个公式相当于把两个“公式1”前后连接而成的。

公式3：如果一个正则表达式是这样的：a|b，即二选一的情况，那么NFA如下图：

图中我有几条边是没有画输入的，那么就是Ɛ，即：空输入或无输入，以后为了画图方便，Ɛ输入就不画在图中了。

这个图描述的就是：从开始状态，可以向上走1，也可以向下走3，如果走1，那输入a就走到2，如果走3，那么输入b就走到4，2和4都有一个空输出到接受状态。

这个图相当于把两个“公式1”的并排放到一起，前面接一个状态做为开始，后面接一个状态做为结束。

公式4：如果一个正则表达式是Kleen必包：a*，那么其对应的NFA如图：

这个图稍微解释一下：从开始有两条空输入边，一条直接到接受状态，这表示一个a都不接受，另一个空输入边到1，1只有一个出口就是输入一个a到2，2状态可以直接到达接受状态，也可以回到1，这样就可以达到接受任意多个a的情况。

有了上面四个公式，就可以达到匹配任何字符的目的了（还不能匹配位置，不过对于编译器的词法分析是不需要匹配位置的），举个例子a*|bc就可以用“公式4”把a*的图画出来，用“公式2”把bc的图画出来，再用“公式3”把前两个图连接上就行了，如图：

上面四个公式上最基本的公式。大多数正则表达式也会识别其它的结构，如：a?、a+，其实这也可以用以上公式来做：a?可以等价于a|Ɛ（其实这个只要把a表示的NFA从开始状态拉一个空输入的边到接受状态就可以了，不需要使用“公式2”的，“公式2”主要是使用于两个正则表达式之前的或关系，如果两个表达式有一个为空，可以简便一点处理），a+等价于aa*，这样我们还是可以用基本公式来处理。

基本公式有了之后，还需要处理一些括号，下面分别讲一下：

方括号[]：代表字符组，就是指方括号中的字符任选其一的意思。例如：[abc]就是指匹配a或匹配b或匹配c，即与a|b|c等价。特殊情况是当方括号内的第一个字符是^时，表示排除形字符组，就是指广括号中，除了第一个^之外的其它字符都不匹配，例如[^abc]就是指不能匹配a，也不能匹配b，也不能匹配c。另外，在字符组中可以使用连字符(-)，例如[a-d]和[abcd]是等价的。

方括号转NFA的一个比较简单的做法是把整个字符组做为一条边的输入，这样做的话，那么表示NFA的某状态的输入就不是单个字符，而是一个字符串，只要当前字符是（或者不是，当是排除形字符组时）这个字符串中的字符即可。这样的处理方式就可以套用前面的“公式1”了。

对于连字符(-)的处理一般有两种方法。如果语言的字母表比较小（比如ASCII），那么只要把连字符展开就可以了，例如：[a-z]就直接用[abcdefghijklmnopqrstuvwxyz]来替换。如果语言的字母表很大（比如Unicode），那么就不展开，如果这样展开，那这一个字符串就要占用非常大的内存，这时的做法是把连字符直接放到输入里，不在转换与此同时文法的时候处理，而在运行的时候用“大于等于”和“小于等于”来判断。

小括号()：代表在正则表达式中限定一个范围，也就是改变有限级的做用。例如：a*|bc和(a*|b)c这两个表达式，我们知道“合取”的有限级是高于“析取”的（这里用“合取”和“析取”不太标准，不过因为我想到如果用“与”和“或”仍然不太标准，所以我选择用两个稍生僻点的名词，可以多吸引一下读者的眼球，或许可以因此减少对这里的不准确的描述的误解），所以a*|bc对应的NFA图是这样的：

而(a*|b)c改变了优先级，此时要先做“析取”再做合取，其对应的NFA图是这样的：

对于小括号的处理方式是先把括号内的部分做为一个整体再处理。例如：(a*|b)c，先把a*|b做为一个整体A，那么就变成了(A)c此时小括号就没用了，可以去掉，就变成了Ac，这样就可以套用“公式2”了。之后再处理a*|b，此时没有括号，也可以套用基本公式(如果有嵌套的小括号，则前面的办法，把括号内的部分做为一个整体)。之后再把转换完a*|b的NFA放到之前A在图中的位置就可以了。

花括号{}：用来引用前面已经定义过的正则表达式（我在写代码的时候用了尖括号<>，flex用的是花括号，我打算以后重写的时候用花括号，因为花括号好看一点）。正则文法的准确定义我不在这里详述，用我的话简单说来就是一系列的正则表达式（每个表达式有一个名字和一个定义），后面的表达式不但可以包含字母表中的内容，还可以包含前面已经定义过的表达式。这里我们就用花括号来引用前面已经定义过的正则表达式的名字。

对于花括号的处理比较简单：我们只要把花括号部分用前面的定义来替换就行了。实际写代码的时候我们可能在转换NFA的时候把前面已经转换完成的NFA图拿过来用就行了，而不需要去替换其定义。

正则表达式的元字符基本都说完了，但还有一个必须说的，就是转义字符：因为元字符本身都有特殊意义，所以如果我们要匹配这字符就一定要有一种方法让他们只表示自己，而不做它用。通常我们的做法是在这个字符前面加一个反斜线，如：\(a\)，这里的小括号就不再表示表达式内的一个范围，而只是一个字符。对于转义字符的处理只是在读字符的时候做一下字符处理就行了，这不涉及到NFA图的构造，所以这里就不细说了。

到此，用任何一个正则表达式转换成NFA的方法就描述完了。

一个正则表达式只能表示语言的一种词素。要表示所有词素就要为每个词素写一个正则表达式（也可能是一套正则文法），这样就会构造出多个NFA。前面只讲了一个NFA运行的过程，并没有讲多个NFA的，下在来讲一下：

一种是每个分别运行，哪一个匹配了就算哪一个，如果有多个匹配了就看哪一个匹配的单词多。

另一种方式是把这些NFA组成一个大的NFA。这个合并的方式与“公式2”差不多，也是前面加一个状态s0，这个s0可以通过Ɛ到达其它每个NFA的开始状态，并把s0做为合并后的大NFA的开始状态，后面加一个s1，每个NFA的接受状态可以通过Ɛ到达s1。这个合并过程与“公式2”只有一点差别，就是这个合并要保留原来所有小的NFA的接受状态。这样合并之后的NFA有一个开始状态和多个不同的接受状态。这样变成一个NFA之后前面的运行过程就仍然适用了。

到此正则表达式转NFA的内容就全讲完了。虽然NFA也可以运行，并且也可以用来识别语言的词素，但其运行过程要比DFA复杂得多，而且除非我们可以并发的运行NFA的每个分支，否则NFA的执行速度绝对分比NFA的执行速度要慢。我们现在拥有的计算机一般都只是PC机，还没有那么强的并发能力，所以NFA转DFA就成了词法分析的一个必要的程。

另外，某些正则引擎用NFA来运行，这是基于引擎使用的实际情况来考虑的。因为NFA转DFA也是要时间的，并且如果引擎经常使用在高并发能力的计算机上，那么直接用NFA来运行还会快一些。而编译器通常不这么做是因为编译器在发布时只发布DFA就行了，NFA转DFA的过程最终用户并不会接触到。这也是词法分析程序与正则引擎的不同之处。

下一节来讲一下NFA转DFA的方法。

本节参考资料

1. Alfred V.Aho、Monica S.Lam、Ravi Sethi、Jeffrey D.Ullman著，赵建华、郑滔、戴新宇译，《编译原理》，机械工业出版社，2010年4月。
2. Michael L.Scoot著，裘宗燕译，《程序设计语言-实践之路》第2版，电子工业出版社，2007年6月。

我的代码

代码写得一般，有一些设计上的缺陷导致其并不是很通用。我打算整个编译器写完之后，再头写一便，修复一些设计缺陷。这里就不贴了。