第三章 词法分析

一、知识点

    第三章学习了词法分析，词法分析的任务是从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。因此，词法分析是编译的基础。执行词法分析的程序成为词法分析器，词法分析器的功能是输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号。程序语言的单词符号一般可分为关键字、标识符、常数、运算符、界符。词法分析器输出的单词符号常常用二元式来表示：<单词种别，单词符号的属性值>。词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称输入缓冲区。

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

    状态转换图是一张有限方向图，再状态转换图中，结点代表状态，用圆圈表示，状态之间用箭弧连结，箭弧上的标记代表在射出结点状态下可能出现的输入字符或字符类，一个完整的状态转换图有n个状态，其中有一个初态，至少要有一个终态(用双圆圈表示)。

    词法分析器的构造的基本思路：程序语言的描述->词法规则->正规表达式->有限自动机->词法分析程序.正规集是把具有相同特征的字放在一起组成一个集合，然后使用一种形式化的方法来表示正规集，即所谓的正规式。正规式是描述单词结构的一种形式，正规集是该类单词的全集。

       正规式的性质：  (1) U | V = V | U 或的交换律
              (2) U | ( V|W ) = ( U|V ) | W      或的结合律
              (3) U ( VW ) = ( UV ) W 连接积的结合律
              (4) U ( V | W ) = ( UV ) | ( UW ) 分配律
                 ( V | W ) U = VU | WU

              (5) εU = Uε = U

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

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

    定理1：对于任何∑上NFA M都可构造一个∑上的正规式V，使得L(V)=L(M)其中，L(M)是∑上NFA M所能识别的字的全体L(V)是∑上的正规集。

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

     DFA化简算法：

    (1) 基本思想

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

    (2) 化简算法
    ①对M的状态集S进行划分：
把S的终态和非终态分开，分成终态集合非终态集，形成基本分划П，显然这两个子集是可区别的。

    ②假定到某个时候П含有m个子集，记П={I(1),I(2),… I(m)}并且，属于不同子集的状态是可区别的。检查П中的每个I(i)看能否进一步划分：对于某个I(i)另I(i)={q1 ,q2 ,…,qk}若存在一个输入字符a使得I(i)a不全包含在现行П的某个子集I(j)中，就将I(i)一分为二。

    二、课后习题

    

    三、感悟

    第三章我们学习了词法分析，不光学习了手工构造方法，还学习了自动构造方法，重点是正规式与有限自动机，和他们之间的相互转化。感觉做题有些困难。