词法分析

lexical analysis：将输入分解成一个个独立的符号，即tokens

词法单词

token是由字符组成的序列，例如在常见的程序设计语言都有这样的一些单词类型：

类型	例子
ID	foo n14 last
NUM	11 2 34
IF	if
COMMA	,
LPAREN	（

正则表达式

由于我们在谈论某种语言时，需要为其中的字符串赋予特别的意义，因此我们可以用正则表达式去表示。

正则表达式的表达符号：

表示	意义
a	一个表示字符串本身的原始字符
ε	空字符串
M\|N	可选，alternation，M和N之间选择
M*N	联结，concentration，M后面跟着N，也可以写成MN
M*	重复，0次或者以上
M+	重复，1次或以上
M?	选择M出现0次或者1次
[a-zA-Z]	字符集合
.	表示除了换行符外的所有字符
"xxxx"	引号内的字符串本身文字字符串本身

但是，考虑这样一个字符串if8，到底是认为其为一个标识符，还是两个tokens：if和8呢？为了消除二义性，我们可以试用一下两个规则：

Longest match：对于输入的字符串，取可以与任意正则表达式规则匹配的字符串中最长的那一个作为下一个token；
Rule priority：给正则表达式赋予某些优先权，选择优先级高的；

有限自动机

虽然用正则表达式已经可以很好地指明词法规则，但我们还需要一种能用计算机程序来实现的的形式化方法。这就是有限自动机(DFA)所做的事情。有限自动机包含了有限状态的集合和一些从一个状态到另一个状态的边。

在DFA中，不会有从同一个状态出发的两条边却包含了相同的符号。若对n个字符的字符串，进行了n次的转换之后，如果自动机到达了一个终态，则选择接收该字符串。如果没有到达终态，或者找不到与输入字符匹配的边，则拒绝接收字符串。

识别最长的匹配

为了识别一个字符串是否会被接收，词法分析器往往会选择最长的匹配，作为合法的token。因此需要两个变量来记住自动机最近一次处于final states的时机。

非确定有限自动机

与确定有限自动机不同，非确定有限自动机(NFA)需要做出选择，对从一个状态出发的多条标有相同符号的边进行选择。

将正则表达式转换为NFA

有了NFA之后，我们可以很容易地将正则表达式转化为NFA，一个正则表达式要么是一个简单的primitive，要么是由多个较小的表达式组合而成。如图：

将NFA转换为DFA

先来看NFA的模拟算法：

1
2
3

d<-closure({s1})
for i<-1 to k
	d <- DFAedge(d, ci)

首先构造s1的eplison闭包，然后从该闭包的状态集合出发，吃进符号c，到达一个新的状态集合。

看一个例子：

以字符串in为例子，先计算出eplison闭包，即求得状态集合为{1,4,9,14}；接着要根据字符i来进行状态转换，从状态1可到状态2，4可以到5，9无处可去，14可以到15，因此得到状态集合{2,5,15}，但是我们还要计算一次闭包，因此得到最终状态集合为{2,5,6,8,15}；同理，根据字符n进行转换。

这样的自动机还不是最理想的，我们还可以构造最小的自动机。我们只会在这种情况下称两个状态是等价的，如果一个开始于s1的自动机接收字符串a，当且仅当一个开始s2的自动机接收字符串a。这样我们就可以使得所有进入s2的边指向s1，并删除s2。