词法分析是编译的第一个阶段，在单词的级别上分析和翻译源程序。

理论基础

有限自动机理论
有限自动机理论与正规文法、正规式之间在描述语言方面有一对一的关系。

学习目标

掌握有限自动机与正规文法、正规式之间的转换。
能够构造词法分析程序。

正规文法、正规集、正规式

正规文法

正规文法是compiler-2中提到的3型文法

正规文法是描述正规集的文法，可用于描述程序设计语言的语法部分。
例如:标识符这种单词可以用下面的规则描述。
- <标识符>→<字母>|标识符>(<字母>|<数字>）
- <字母>表示在意英文字母
- <数字>表示任意数字

正规集

由正规文法产生的语言

正规集是集合，可有穷也可无穷。可通过正规式来形式化表示。

正规式

规则：

设A是非空的有限字母表，A={a,/ i=1,2,… …n},则空串、空集，字母表中任一字母【a~i~ (i=1,2,… …n)】都是正规式。
心
若α、β是正规式，则α|β、α*β 、α*、β*也是正规式。【α的正闭包一定是正规式】
正规式只能通过有限次使用1，2规则获得

注:

1）

“|”读作为“或”，也可写作为“+或"，”
“*”读作连接

仅由字母表A={a~i~|i=1,2,…n}上的正规式α所组成的语言称作正规集，记作L(α),L表示一种语言

3）

利用正规集相同，可用来证明相应正规式等价。如果两个正规集相同，则对应的正规式等价

三个概念间关系

一个正规语言可以用正规文法定义，也可以用正规式定义
【对任意一个正规文法，存在一个定义同一个语言的正规式】
【对任意一个正规式，存在一个生成同一语言的正规文法】
有些正规语言很容易用文法定义，有些则用正规式定义更容易;
正规文法和正规式之间是可以转换的，结构上具有等价性
由正规文法或正规式定义的正规语言的集合构成正规集。

举例：

证明b(ab)*=(ba)*b

原则：根据正规式，写出正规集，如果正规集相同，则正规式等价

L(b(ab)*)={b,bab,babab,…}

L((ba)*b)={b,bab,babab,… }

又∵正规集的前n项相同

可知它们的正规集是相等的，所以正规式b(ab)*=(ba)*b

定理1

若α， β， γ都是正规式，有以下定理1

定理2

将α->β|αγ，不断展开，变成α->{βγγγγγγγγ……}，也就是α->{βγ*}

正规文法转换成正规式

原则

由正规文法G的各个产生式写出对应的正规方程式，得到联立方程组
把方程组中的非终结符当作变元。
求此正规式方程组的解（解由终结符构成），得到关于开始符号S的解:S=w , w ∈VT*，w就是所求正规式。

举例

解：

1、由产生式写出对应的联立方程组

2、根据上面的定理2，对（1）式进行变形

同理，对（2），（3）进行转换

转换后，发现**（4）、（5）中仍然包含非终结符**，（6）已经是正规式

3、将（6）带入到（4），（5）中，得到不含非终结符的式子，即为正规式

4、所以：正规式S=a^+^ b^+^ c^+^

正规式转换成正规文法

由正规式转换成正规文法，需要借助“有限自动机”这个工具，所以先讲有限自动机

有限自动机

有限自动机是一种识别装置，它能准确地识别正规集。它为词法分析程序的构造提供了方法和工具。

有限自动机是具有离散输入输出系统的数学模型。它具有有限数目的内部状态（初始、中间、终止），系统根据当前所处的状态和面临的输入字符决定系统的后继行为。其当前状态概括了过去输入处理的信息。

过程

读头在a，状态为初始状态
读头不断改变，状态为中间状态
- 如果状态为中间状态，但读头的某个字符，是绝对不会遇到的符号，出错
读头到最后一个符号，并且状态为终态，正确
如果读头到最后一个符号，但状态不是终止状态，出错

举例

如标识符的自动机

由上图可见，最终能进入2号状态，2号状态是个终态，xtemp是正确的标识符。

如果输入2xtemp，在1号状态无法进入2号状态，会留在1号状态，1号状态不是终态，则错误

确定的自动机

DFA(Deterministic FA)

由一个状态和一个输入得到一个结果，如上面的标识符自动机

定义

s0 唯一的初态
Z 终止状态集，Z是S的子集，可以是空集（出错状态不在终止状态集中）

关键在于：f(s,a)=s’，由一个状态和一个输入，得到一个结果。是单值映射

举例

状态转换矩阵

状态转换图

在整个状态转换图中只有一个初始状态结点，用**“→”射入的结点表示初始**状态。
可有若干终止状态(也可能没有)，用双圆圈表示。
若初始状态结点同时又是终止状态结点，则表示空串可为相应DFA识别。

构造DFA

比如：

1号状态：以a/b开头
2号状态：以c开头，但没有a
3号状态：以c开头，但只有一个a

写成对应的函数关系

对应矩阵：

	a	b	c
0	1	1	2
1	1	1	1
2	3	2	2
3	\	3	3

能被有限自动机（DFA）M（M只是个名字）所识别的字符串的集合，称为DFA M能识别的语言，记为L(M)

如，标识符自动机M，能识别出所有的标识符

不能被DFA接受的字符串的两种情况

读完输入串，状态不停在终止状态，即:(s0, a)|-(s’, 空串)，且s’不属于Z
在读过程中出现不存在的映射，使自动机无法继续动作（如，标识符自动机中，输入2xtemp，第一个数字2就不能被映射）

不确定的有限自动机

NFA(Non-deterministic FA)

DFA只是NFA的特例,NFA也是个五元式

S0:非空的初态集（至少有一个元素），S0是S的真子集。不像DFA，只能有一个初始态
Z:终止状态集，Z是S的子集，可以是空集
f:一个状态+一个符号 = 一些状态，可以到达2^S个状态

注

1)非确定主要是指后继状态可有多个。
2)DFA是NFA的特例

举例

0* 1^+^ 0* 1* 0*

上图的自动机，识别：至少包含一个1的二进制串

解释

如果初始是0，则递归q0；如果初始是1，则可以进入终态q1
进入q1后，读头可以是0/1，如果是1，

两个自动机等价

任何两个有限自动机M和M’，若它们识别的语言相同(L(M)=L(M’))，则称M和M’等价。
注:存在判定任何两个有限自动机等价性的算法。

NFA的转换为DFA(确定化)

使用子集法对NFA进行确定化

定理

对于每个NFA M，存在一个DFA M’，使得L(M)=L(M’)。即，设L是NFA接受的正规集，则存在一个DFA接受L。

原来的NFA中的起点打包在一起（成为一个起点），指向不同的节点

终态的确定：如果NFA的终态，也出现在转换后的终态，那将这些终态打包在一起，成为一个终态

注:

NFA确定化的实质是以原有状态集上的覆盖片(COVER)作为DFA上的一个状态(将NFA几个状态打包)，将原状态间的转换改为覆盖片间的转换，从而将不确定问题确定化。
通常，经确定化后，状态数增加，而且可能出现一些等价状态，这时需要化简。

举例

M的初态:I0={q0}。则状态集Q中就有I0状态。
由Q中的状态I0={q0}，查看NFA M的原图有:
- ({q0},0)={q0}
- ({q0},1)={q1}=I1, 因为I1不存在状态集Q中，所以把I1放入状态集Q,Q={I0,I1}
因为I0已经看过了，那由Q中的状态I1={q1}，查看NFA M的原图有:
- ({q1},0)={q0,q1}=I2, 因为I2不存在状态集Q中，所以把I2放入状态集Q,Q={I0,I1.I2}
- ({q1},1)={q0}=I0
因为I0,I1已经看过了，那由Q中的状态I2={q0,q1}，查看NFA M的原图有:
- I2里面的q0：({q0},0)={q0}; I2里面的q1：({q1},0)={q0,q1}；所以(取前面两个结果并集)({q0,q1},0)={q0,q1}=I2
- I2里面的q0：({q0},1)={q1}; I2里面的q1：({q1},1)={q0}；所以(取前面两个结果并集)({q0,q1},1)={q0,q1}=I2
- 因为I2在状态集里面，所以不用添加，Q={I0,I1.I2}
初态：I0，因为I0是NFA的初态；终态是包含q1的状态：I1={q1},I2={q0,q1}，因为q1是NFA的终态，所有包含q1的都是终态

状态转换图如下：

DFA化简（最小化）

划分法

化简(最小化)算法基本思想-划分法

1.将DFAM 中的状态划分为互不相交的子集，每个子集内部的状态都等价;而在不同子集间的状态均不等价。
2.从每个子集中任选一个状态作为代表，消去其它等价状态。
3.把那些原来射入其它等价状态的弧改为射入相应的代表状态。
- 如下图的1->4,2->3；转换成（1，2）->（3，4）

状态等价与状态可区别

如果s与t识别相同的串，并得到了相同的结果，则s与t状态等价（不是相等）。否则就是状态可区别

算法

比如，对I0中，1号识别0到I02中，2号识别0到I01中，说明1和2还要继续划分。

也就是说，目前的I0如果识别0，会到达不同的状态，说明需要继续划分

注:

1)当一个自动机没有任何多余的状态，并且它的状态中没有两个是互相等价的时，我们说这个有限自动机是化简了的。

举例

做法

刚开始把0,1,2归为非终态集，3,4,5,6为终态集
看非终态集，如果识别a
- ({0,1,2},a)={1,3}不属于II0的任何一个子集，所以{0，1，2}要分开
- 得到:II1'={ {1}，{0,2},{3,4,5,6} }
再看:({0,2},a)={1}属于II1'的子集,({0,2},b)={2,5}不属于II1'的任何子集，所以{0,2}要分开
- 得到:II1''={ {1}，{0}，{2},{3,4,5,6} }

现在非终态集就划分完成

看终态集，分别识别a,b
({3.4,5.6},a)={3,6}包含于II1''的子集{3,4,5,6}中
({3.4.5.6},b)={4,5}包含于II1''的子集{3,4,5,6}
- 所以{3,4,5,6}不可再划分，所以3,4,5,6是等价的

终态集也划分完成

令状态3代表{3,4,5,6}，把原来到达状态4，5，6的弧都导入3，并删除4，5，6。得下图

结果

在3,4,5,6内部相互指向的全部由3指向自己

正规式与有限自动机关系

关系定理

由NFA M所能识别的语言L(M)可以用正规式来表示。
由NFA M，可构造一个正规式α，使得L(α)=L(M)
由正规式α，可构造一个DFA M，使得L(α)=L(M)

由DFA转换成正规式α

在M的转换图上加两个结点:x,y。从x用空串弧连接到M的所有初态结点;从M的终态结点用空串弧连接到y，这个新的NFA为M，且L(M)=L(M’)。如下图
通过引入的3条替换规则逐步消去M’中的所有结点，直到只剩下x和y为止。
这样，在x至y的弧线上的标记就是的正规式，也就是M接受的正规式。

替换规则

举例

第一步，对1节点进行转换
对2节点转换
将上述结果合并

结果如下：

现在优化3号节点，
利用规则3，去掉节点3
利用规则2，去掉节点0。外面加一个闭包，因为可以通过x->空串->空串->y

由正规式转换成DFA

1)由正规式α构造一个如下仅有两个结点x,y的状态
2)按所引入的3条规则分裂正规式。
3)重复步骤2直到每个弧上的标记是字符集上的一个字符或空串为止。
4)将所得的NFA (因为包含空串弧)进行确定化就得到DFA。下面会提到

替换规则

注意

举例

根据正规式(a|b)*(aa|bb)(a|b)*构造DFA M

分别使用规则3、规则2、规则3，得到下图
再分别使用规则2、规则1、规则2，得到下图

最后，会得到NFA，并且进而包含空串，所以需要对NFA进行确定化

对含有空串ε的NFA进行确定化

因为正规式在转换成DFA时，只能先转换成NFA，再由NFA确定化转换成DFA

举例

I0是包含初始态和只用空串到达的状态，I0={x,5,1}
再对I0，识别字母a和空串ε到达的状态，5经过a到5，1经过a到3。再求5和3的闭包，5经过空串到达1，所以I1={5,3,1}
再对I0，识别字母a到空串ε达的状态，5经过b到5,1经过b到4。再求5和4的闭包，5经过空串到达1，所以I2={5,4,1}
对I1={5,3,1},识别字母a和空串ε到达的状态，5经过a到5，3经过a到2，5经过空串ε到1，1经过a到3，2经过空串ε到6，6经过空串ε到y，所以I3={5,2,1,3,6,y}
以此类推……，得到下面的表，如果过程中，产生的Ix已经出现，就无需添加新的：比如，I1识别b时产生的和I2一致