本文共 3823 字，大约阅读时间需要 12 分钟。

原文地址：

编译原理词法分析词法分析的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用于语法分析。

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,2,4,6,7},令C=Dtran[A,b]Dtran[B,a]=ε-closure(move(B,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=BDtran[B,b]=ε-closure(move(B,b))=ε-closure({5,9})={1,2,4,5,6,7,9},令D=Dtran[B,b]Dtran[C,a]=ε-closure(move(C,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=BDtran[C,b]=ε-closure(move(C,b))=ε-closure({5})={1,2,4,6,7}=CDtran[D,a]=ε-closure(move(D,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=BDtran[D,b]=ε-closure(move(D,b))=ε-closure({5,10})={1,2,4,5,6,7,10},令E=Dtran[D,b]Dtran[E,a]=ε-closure(move(E,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=BDtran[E,b]=ε-closure(move(E,b))=ε-closure({5})={1,2,4,6,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,B,C,D}，是可以被分割的，因此我们必须考虑各个输入符号的作用，在输入a上，这些状态中的每一个都转到B，因此使用以a开头的串无法区分这些状态。但对于输入b，状态A、B、C都转换到{A,B,C,D}的某个成员上，而D转到另一组中的成员E上，因此在IInew中，{A,B,C,D}被分割成{A,B,C}，{D}，现在IInew中有{A,B,C}，{D}，{E}。对于{A,B,C}，在输入b上，A和C都到达{A,B,C}中的元素，B却到达D上，所有IInew有{A,C},{B},{D},{E},对于{A,C}无法在分割。所有最后有{A,C},{B},{D},{E}，构造如下的DFA

转载地址：http://xbbqb.baihongyu.com/