原文地址：编译原理 词法分析
编译原理 词法分析 词法分析的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用于语法分析。
1.正则表达式
对给定的字符集∑={c1,c2,...,cn},归纳定义：
1.空串ε是正则表达式
2.对于任意c∈∑，c是正则表达式
3.如果M和N是正则表达式，则下列表达式也是正则表达式
(1)选择 M|N={M,N}
(2)连接 MN={mn|m∈M,n∈N}
(3)闭包 M*={ε,M,MM,MMM,...}
2.正则表达式的扩展
(1)[c1-cn]==c1|c2|c3|...|cn
(2)e+==一个或多个e
(3)e?==零个或一个e
(4)"a*"==a*自身，不是a的Kleen闭包
(5)e{i,j}==i到j个e的连接
3.状态转换图
状态转换图有一组被称为“状态”的结点或圆圈。词法分析器在扫描输入串的过程中寻找和某个模式匹配的词素，而 转换图中的每个状态代表一个可能在这个过程中出现的情况。
对于
的状态转换图为
4.有穷自动机
有穷自动机是识别器，只能对每个可能的输入串简单地回答“是”或“否”。
（1）有穷自动机分两种
1)不确定的有穷自动机（NFA）：对其边上的标号没有任何限制。一个符号标记离开同一状态的多条边， 并且空串ε也可以作为标号。 2)确定的有穷自动机（DFA）：对于每个状态及自动机输入字母表中的每个符号，有且只有一条离开该状态、以该符 号为标号的边。
（2）不确定的有穷自动机（NFA）
一个不确定的有穷自动机（NFA）由以下几个部分组成：
1)一个有穷的状态集合S。
2)一个输入符号集合∑，即输入字母表。（ε∉∑）
3)一个转换函数，它为每个状态和∑∪{ε}中的每个符号都给出了相应的后继状态的集合。
4)S中的一个状态s0被指定为开始状态，或者初始状态。
6)S的一个子集F被指定为接受状态（或终止状态）的集合。
（3）确定的有穷自动机（DFA）
确定的有穷自动机是不确定有穷自动机的一个特例。其中： 1)没有输入ε之上的转换动作。 2)对于每个状态s和每个输入符号a，有且只有一条标号为a的边离开s。
5.从正则表达式构造NFA（Thompson算法）
输入：字母表∑上的一个正则表达式r. 输出：一个接受L(r)的NFA N. 方法：首先对r进行语法分析，分解出组成它的子表达式。构造一个NFA的规则分为基本规则和归纳规则两组。 基本规则处理不包含运算符的子表达式，而归纳规则根据一个给定表达式的直接子表达式的NFA构造出这个表达式的NFA。
(1)基本规则：
1）对于表达式ε，构造下面的NFA
2)对于字母表中的子表达式a，构造下面的NFA
(2)归纳规则：假设正则表达式s和t的NFA分别为N(s)和N(t)
3）假设r=s|t，构造下面的NFA，这里i和f是新状态，分别是N(r)的开始状态和接受状态。从i到N(s)和N(t)的开始状态各 有一个ε转换，从N(s)和N(t)到接受状态f也各有一个ε转换。
4)假设r=st，构造下面的NFA，N(s)的开始状态变成了N(r)的开始状态。N(t)的接受状态成为N(r)的唯一接受状态。N(s)的 接受状态和N(t)的开始状态合并为一个状态，合并后的状态拥有原来进入和离开合并前的两个状态的全部转换。
5)假设r=s*,构造下面的NFA，i和f是两个新状态，分别是N(r)的开始状态和唯一的接受状态。要从i到达f，我们可以沿着新引入 的标号为ε的路径前进，这个路径对应于L(s)的一个串。我们也可以到达N(s)的开始状态，然后经过该NFA，再零次或多次从它的 接受状态回到它的开始状态并重复上述过程。
(3)利用Thompson算法为正则表达式r=(a|b)*abb构造一个NFA
1)首先画出语法分析树
2)对于表达式r1=a，r2=b构造NFA
3)对于表达式r3=r1|r2构造NFA
4)对于表达式r5=r3*构造NFA
5)对于表达式r6=r1r2构造NFA
6)对于表达式r7=r5r6构造NFA
7)同理最后可以得到NFA
6.由NFA构造DFA的子集构造算法（subset construction）
输入：一个NFA N. 输出：一个接受同样语言的DFA D. 方法：我们为D构造一个转换表Dtran，D的每个状态是一个NFA状态集合，我们将构造Dtran，使得D"并行地"模拟N在遇到一个 给定输入串时可能执行的所有动作。我们面对的第一个问题是正确处理N的ε转换。
下面给定了一些函数的定义，这些函数描述了一些需要在这个算法中执行的N的状态集上的基本操作，s表示N的单个状态，T代表N的一个状态集。
我们需要找出当N读入了某个输入串之后可能位于的所有状态集合。 首先，在读入第一个输入符号之前，N可以位于集合ε-closure(s0)中的任何状态上，其中s0是N的开始状态。下面进行归纳定义， 假定N在读入输入串x之后可以位于集合T中的状态上。如果下一个输入符号是a，那么N可以立即移动到move(T,a)中的任何状态。 然而，N可以在读入a后再执行几个ε转换，因此N在读入xa之后可位于ε-closure(move(T,a))中的任何状态上。
ε-closure(T)的计算：从一个状态集合开始，所有只存在标号为ε的边都加入T
对于上面由Thompson算法为正则表达式r=(a|b)*abb构造一个NFA，我们将这个NFA转换成一个DFA
首先，NFA的开始状态A是ε-closure(0)，即A={0，1，2，4，7}，NFA的输入字母表是{a,b}，则
Dtran[A,a]=ε-closure(move(A,a))=ε-closure({3,8})={1,2,3,4,6,7,8},令B=Dtran[A,a]
Dtran[A,b]=ε-closure(move(A,b))=ε-closure({5})={1,7},令C=Dtran[A,b]
Dtran[B,a]=ε-closure(move(B,8}=B
Dtran[B,b]=ε-closure(move(B,b))=ε-closure({5,9})={1,5,9},令D=Dtran[B,b]
Dtran[C,a]=ε-closure(move(C,8}=B
Dtran[C,b]=ε-closure(move(C,7}=C
Dtran[D,a]=ε-closure(move(D,8}=B
Dtran[D,b]=ε-closure(move(D,10})={1,10},令E=Dtran[D,b]
Dtran[E,a]=ε-closure(move(E,8}=B
Dtran[E,b]=ε-closure(move(E,7}=C
所有DFA的转换表Dtran
根据转换表可以得到DFA
7.最小化一个DFA的状态数量
输入：一个DFA D，其状态集合为S，输入字母表为∑，开始状态为s0，接受状态为F。 输出：一个DFA D'，它和D接受同样的语言，且状态数最少。 方法： 1)首先构造包含两个组F和S-F的初始划分II，这两个组分别是D的接受状态组和非接受状态组。 2)用下面的构造新的分划IInew
3)如果IInew=II,令IIfinal=II并接着执行步骤4)，否则，用IInew替换II并重复步骤2)。 4)在分划IIfinal的每个组中选取一个状态作为该组的代表。这些代表构成了状态最少DFA D'的状态。 D'的其他部分按如下步骤构建： (a)D'的开始状态是包含了D的开始状态的组的代表。 (b)D'的接受状态是那些包含了D的接受状态的组的代表。 (c)令s是IIfinal中某个组G的代表，并令DFA D中在输入a上离开s的转换到达状态t。令r为t所在组H的代表。 那么在D'中存在一个从s到r在输入a上的转换。
对上面的DFA最小化
首先初始划分包括两个组{A,B,C,D},{E},分别是非接受状态组和接受状态组。构造IInew时，考虑这两个组
和输入符号a和b，因为组{E}只包含一个状态，不能再被分割，所以{E}被原封不动的保留在IInew中。对于
{A,D}，是可以被分割的，因此我们必须考虑各个输入符号的作用，在输入a上，这些状态中的每一个都
转到B，因此使用以a开头的串无法区分这些状态。但对于输入b，状态A、B、C都转换到{A,D}的某个成
员上，而D转到另一组中的成员E上，因此在IInew中，{A,D}被分割成{A,C}，{D}，现在IInew中有
{A,C}，{D}，{E}。对于{A,C}，在输入b上，A和C都到达{A,C}中的元素，B却到达D上，所有IInew
有{A,C},{B},{D},对于{A,C}无法在分割。
所有最后有{A,{E}，构造如下的DFA