编译原理 词法分析

原文地址：编译原理 词法分析

编译原理

词法分析

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

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