词法分析

1. 重点内容

   词法分析这一章最主要的内容是正规式和自动机，概念主要包括正规式、正规集、确定的有限自动机、非确定的有限自动机、等价，主要的可操作内容有正规式和自动机的转化、自动机的确定化、自动机的简化，这里面需要状态转化图、状态矩阵、子集闭包来做中间工作。

    首先对正规式和正规集的了解是学习自动机的基础：

1、正规集：具有相同特征的字放在一起组成一的集合（该类单词的全集）。

2、 正规式：表示正规集的一种形式化的方法（描述单词结构的一种形式）。

 

    确定的有限自动机（DFA  Deterministic Finite Automata）和非确定的有限自动机(NFA  Non-deterministic Finite Automata)在定义上有很明确的区分，NFA代表的是一个有限自动机的集合，指的是一类，而DFA可以说是NFA的一个特殊情况，是NFA这个集合中的某一个元素。

1、 DFA定义：一个确定有限自动机（DFA）M是一个五元式：

M = (S, ∑, f, s0, F)，其中

a. S是一个有限的状态集合，它的每个元素我们称为一个状态

b. ∑是一个有穷的输入符号的字母表，它的每个元素我们称为一个输入字符

c. f是从 S×∑ →S的单值部分映射

d. s0是S的一个元素，为初始状态，它是唯一的

e. 状态集合F是终止状态的集合，它是S的子集(可空)

2、 DFA M的表示方法

1)  状态转换矩阵表示法

2)  状态转换图

3、NFA定义：一个非确定有限自动机（NFA）M是一个五元式M = (S, ∑, f, S0, F)，其中

a. S是一个有限的状态集合，它的每个元素我们称为一个状态

b. ∑是一个有限的输入符号的字母表，它的每个元素我们称为一个输入字符

c. f是从S×∑*→2S 的部分映射，其中，2S表示S的幂集合（所有S的子集组成的集合）
（f是非单值的àM是非确定）

d. 状态集合S0是初始状态集合，它是S的子集

e. 状态集合F是终止状态的集合，它是S的子集

4、 有限自动关机的等价

对任何两个有限的自动机M1和M2，若有L(M1)=L(M2)，则称M1与M2等价。

注：

    (1) 若M的某些结点既是初态结点又是终态结点，或者存在一条从某初态结点到某个终态结点的ε通路，那么空字ε可为M所识别。

(2) DFA是NFA的一个特例，对于每个NFA M存在一个DFA M’使得L(M) = L(M’)，也就是说M和M’是等价的。

 

      正规式与有限自动机的等价性是正规式与有限自动机相互转化的依据，通过一定的替换规则，利用增删节点的方法实现两者之间的转换。有限自动机可以通过状态转换图和状态转换表的形式表示，通过邻接表的方式存储，这样就可以通过程序表示出一个有限自动机了。

      以下是进行正规式与有限自动机转换时依据的定理和规则：

1、 定理1：对于任何∑上NFA M都可构造一个∑上的正规式V，使得  L(V) = L(M)

其中，L(M)是∑上NFA M所能识别的字的全体L(V)是∑上的正规集

2、 由一个NFA M，构造一个正规式V的方法：

(1)在M转换图上加进X结点和Y结点，从X结点用弧ε连接M的所有初态结点，M的所有终态结点用弧ε连接到Y，得到一个NFA M’，且L(M) = L(M’)

(2)使用替换规则逐步消去M’的所有结点，直到只剩下X结点和Y结点，在消去过程中，逐步使用正规式来标记箭弧

替换规则：

                                  

1、 定理2.对于∑上的每一个正规式V，存在一个∑上的DFA M，使得L(M) = L(V) 。

2、 由一个正规式V构造一个DFA M与由一个NFA M构造一个正规式V相反。

   得到M’的状态图后，对其进行确定化，需要用到两个闭包的概念ε_CLOSURE(I)和Ia =ε_CLOSURE(J)。然后得到状态转换表，再对其进行简化。

1、 简化时用到状态等价和可区别的概念：

   状态等价：两个不同的状态读出同一个字

   可区别：不等价，则可区别

 

正规式到DFA的完整的转化过程步骤如下：

1) 在∑上构造一个NFA M’

a.   构造一个拓广的转换图；

b.   使用分裂规则对V进行分裂，加进新结点，直到把图转换成每条弧上标识为∑上的一个字符或ε

2) 用子集法把 M’确定化，需要构造一张子集闭包的表，将得到的每个集合看成一个状态，得到一张状态转换表，该表的初态就是ε_CLOSURE(X)，它的终态是那些含有终态Y的子集，这样就得到一个DFA M 且L(M) = L(M’)。用到两个闭包概念如下：

a.   定义1：假定I是M’的状态集的子集，定义I的ε闭包ε_CLOSURE(I)为：

    (a)若q∈I，则q∈ε_CLOSURE(I)

    (b)若q∈I，那么从q出发经任意条ε弧而能到达的任何状态q’都属于ε_CLOSURE(I) ；

b.   定义2：假定I是M’的状态集的子集，a ∈ ∑，定义

    Ia =ε_CLOSURE(J)

    其中，J是所有那些可从I中的某一状态结点出发经过一条a弧而到达的状态结点的全体

注释：

1、a代表字母表中的某一个字母

I是一个状态的集合，J是一个状态的集合

Ia也是一个状态的集合

2、求Ia 可以分为两步：

根据集合I，求集合J（一条a弧）

求J的ε闭包ε_CLOSURE(J)，即是Ia

3) 化简DFA  M’，即找一个状态比M’少的DFA。

(1) 基本思想

把M的状态集分割为一些不相交的子集，使得任何不同的两个子集状态都是可区别的，而同一个子集中的任何状态都是等价的，最后让每个子集选一个代表，同时消去其他等价状态。

(2) 化简算法

a.  对M的状态集S进行划分：

把S的终态和非终态分开，分成终态集合非终态集，形成基本分划П，显然这两个子集是可区别的。

b. 划分子集，直至分划中所含的子集数不再增长为止。

c. 得到一个最后分划П.对于这个П中的每个子集，选取子集中的一个状态代表其它状态。

2. 习题总结

  主要练习的正规式与有限自动机的转换，用到或、与、闭包运算的替换规则将正规式转化为状态图，利用两个闭包概念将状态图转化为状态表，将自动机确定化，利用状态等价和可区分对状态图进行简化。过程比较繁琐，纸上写容易，程序没有实现。

 

3. 课程总结

   该章定义概念比较多，一开始感觉挺零碎，但是整章学完后，感觉就正规式与自动机的转化将所有的知识点都串起来了。做了几个针对转换的题目，感觉最后的化简那一步还有点没怎么搞懂。感觉自己每次都是上课半知半解，下课得重新自己过一遍PPT才能明白整章讲了个啥，上课效率有点差劲，争取再接再厉，加油！