编译原理第三章词法分析总结

   这一章我们将从词法分析器、正规表达式与有限自动机以及语法分析器的自动产生三方面了解词法分析，但我理解的这张的重点是正规表达式与有限自动机。

   首先我们来了解一下词法分析器是什么：它是一组把输入的源程序转换成单词符号的程序，而语法分析器的构造方法包括两方面，一方面是根据词法直接编程序即有限自动机的手工方法，另一方面是利用一些工具的自动方法。而这章的重点就是手工方法。

      要想合理的设计出词法分析器，就需先搞清楚一些基本的东西，比如单词符号的概念、单词的种类及单词的表示形式（二元式<单词种别，单词符号的属性值>），而后是词法分析器的结构。词法分析器包括输入缓冲器，预处理子程序扫描器和扫描缓冲区等四部分，词法分析器的工作流程如下：

（1）输入源程序文本，放入输入缓冲区中，词法分析工作可在这个输入缓冲区中工作
（2）剔除无用的空白，跳格(TAB)，回车，换行等编辑性字符；若空白符号为单词符号的界符，就将若干空白和并为1个
（3）剔除注释行，比如/*…*/
（4）源程序的出错列表打印
（5）将预处理好的子程序放到扫描缓冲区中

（6）在扫描缓冲区设两个半区，可互补使用，并且设两个指针：

         起点指针：指出正在识别单词起点位置
         搜索指针：向前搜索以寻找单词终点
（7）用扫描器直接对单词进行识别

        讲到这里，我们说一下单词的识别，单词的识别包括三种方法：

（1）超前搜索：在单词识别的过程中，通过向前多读几个符号的形式，准确的进行单词的识别，一旦确定识别到的单词之后，需要进行扫描指针的回退，保证单词识别工作的顺利进行

（2）直接分析法：根据读来的第一个字符的种类分别转到各种子程序处理。这些子程序功能就是识别以相应字符开头的各种单词。

                                  直接分析流程图

（3）状态转换图法

     状态转换图是一张能识别一定符号串的有限方向图。一张状态转换图包括三个因素：

 ①结点：代表状态，用圆圈表示
 ②箭弧：状态之间用箭弧连接
 ③箭弧上的标记：代表在射出节点下可能出现的字符或字符串

一个完整的状态转换图有n个状态，其中有一个初态，至少要有一个终态(用双圆圈表示)
   

   词法分析器需要识别语言中具有不同特征的字，便会用到正规式与正规集--把具有相同特征的字放在一起组成一个集合，即所谓的正规集（一类单词的全集）， 然后使用一种形式化的方法来表示正规集，即所谓的正规式（用来描述单词结构的一种形式）。正规事与正规集的概念就不在此赘述了。正规式具有或的交换律、或的结合律、连接集的结合律和分配律等性质。

有了这些基础知识，接下来了解一下有限自动机。有限自动机一般用五元式表示，可分为

（1）确定有限自动机

M = (S, ∑, f, s0, F)，其中
S是一个有限的状态集合，它的每个元素我们称为一个状态
∑是一个有穷的输入符号的字母表，它的每个元素我们称为一个输入字符
f是从 S×∑ →S的单值部分映射
s0是S的一个元素，为初始状态，它是唯一的
状态集合F是终止状态的集合，它是S的子集(可空)

【需要注意的是：确定有限状态自动机不是一个机器而是用来模拟计算机识别功能的数学模型；确定性是指，f(s, a) = s’ 是单值函数。 对任何状态s∈S，和输入符号 a∈∑ ， f(s, a) 唯一的确定下一个状态；有限性是指，S是一个有限的状态集合，并且∑是一个有限的输入符号的字母表】

（2）非确定有限自动机

M = (S, ∑, f, S0, F)，其中
S是一个有限的状态集合，它的每个元素我们称为一个状态
∑是一个有限的输入符号的字母表，它的每个元素我们称为一个输入字符
f是从S×∑*→2S 的部分映射，其中，2S表示S的幂集合（所有S的子集组成的集合）（f是非单值的M是非确定）
状态集合S0是初始状态集合，它是S的子集
状态集合F是终止状态的集合，它是S的子集  

  

    接下来用一个表格来区分DFA M和NFA M

	DFA M	NFA M
表示方法	1.状态转换矩阵表示法 2.状态转换图	1.状态转换矩阵表示法 2.状态转换图
注意	(1)若M的初态结点同时又是终态节点，则空字可被M识别 (2)DFA M所能识别的字的全体记为L(M) (3)如果一个DFA M的输入字母表为∑，则我们称M是∑上的一个DFA (4)若V是∑上的一个正规集，当且仅当存在一个∑上的DFA M，使得V = L(M)
区别	f是从 S×∑ →S的单值部分映射 s0是S的一个元素，为初始状态，它是唯一的	f是从S×∑*→2S 的部分映射 状态集合S0是初始状态集合，它是S的子集
特殊性	DFA是NFA的一个特例，对于每个NFA M存在一个DFA M’使得L(M) = L(M’)，也就是说M和M’是等价的

   接下来说一点比较重要的东西，那就是有限状态自动机的等价：对任何两个有限的自动机M1和M2，若有L(M1)=L(M2)，则称M1与M2等价。 若M的某些结点既是初态结点又是终态结点，或者存在一条从某初态结点到某个终态结点的ε通路，那么空字ε可为M所识别 。另一点是正规式与有限自动机的等价性。等价性定理：任何对于∑上NFA M都可构造一个∑上的正规式V，使得  L(V) = L(M) 。由于等价性原理，可以实现正规式与有限自动机的相互转换：

   【1】由一个NFA M，构造一个正规式V的方法：
(1)在M转换图上加进X结点和Y结点，从X结点用弧ε连接M的所有初态结点，M的所有终态结点用弧ε连接到Y，得到一个NFA M’，且L(M) = L(M’)
(2)使用替换规则逐步消去M’的所有结点，直到只剩下X结点和Y结点，在消去过程中，逐步使用正规式来标记箭弧

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

    【2】由一个正规式V，构造一个DFA M的方法
 （1）根据V，构造一个NFA M’，使得L(M’) = L(V)：        

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

b.使用分裂规则对V进行分裂，加进新结点，直到把图转换成每条弧上标识为∑上的一个字符或ε
 （2）将M’确定化，变为DFA M

    在此处声明两个定义： 

定义1：假定I是M’的状态集的子集，定义I的ε闭包ε_CLOSURE(I)为：
 (a)若q∈I，则q∈ε_CLOSURE(I)
 (b)若q∈I，那么从q出发经任意条ε弧而能到达的任何状态q’都属于ε_CLOSURE(I) ；

定义2：假定I是M’的状态集的子集，a ∈ ∑，定义
 Ia =ε_CLOSURE(J)
 其中，J是所有那些可从I中的某一状态结点出发经过一条a弧而到达的状态结点的全体

用子集法把M1确定化的步骤：

》构造一张表

》把得到的每个集合看成一个状态，得到一张状态转换表，该表的初态就是ε_CLOSURE(X)，它的终态是那些含有终态Y的子集，这样就得到一个DFA M 且L(M) = L(M’)

     有限自动机构造完了，但是有时候会比较复杂，这时候需要进行化简即寻找一个状态比DFA M少的DFA M’，使得
  L(M’) = L(M)。

化简DFA的一般步骤 ：
 (1) 检查状态转换函数是否为全函数。
 所谓全函数，是指每个状态对每个输入符号都有转换
 若不是全函数，可以引入一个“死状态”d，d对所有输入符号都转换到d，如果状态s对输入符号a没有转换，那么加上从s到d的a转换。

 (2) 用化简算法进行化简

 (3) 去掉死状态

 

注：

1.两个状态等价的概念
 设s和t是M两个不同的状态，从s出发能读出某个字而停于终态，那么同样，从t出发也能读出同一个字而停在终态，反之亦可

2.两个状态是可区别的
 若DFA M的两个状态s和t不等价，则称这两个状态是可区别的
 注：终态和非终态是可区别的，因为终态可以读出空字ε，而非终态不能读出空字ε