编译原理第三章-词法分析
词法分析相关概念：
1.词法分析器： 一组把输入的源程序转换成单词符号的程序，而语法分析器的构造方法包括两方面，一方面是根据词法直接编程序即有限自动 机的手工方法，另一方面是利用一些工具的自动方法。
2.词法分析的任务：从左至右逐个字符的对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为由单词符号串组成的程序。那么以词法分析为功能，词法分析器是将一个字母作为分析目标，根据该字母的下一个字母来判断是否应该判定该字母所属类型。它的输入是源程序，输出是单词符号。
3.状态转换图：
转换图是一张有限方向图，能够识别（接受）一定的符号串（单词）。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。一张状态转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。终结态上打个星号*意味着多读进了一个不属于标识符部分的字符，应把它退还给输入串。
4.正规表达式
正规集：具有相同特征的字放在一起组成一的集合（该类单词的全集）。
正规式：表示正规集的一种形式化的方法（描述单词结构的一种形式）。
正规式的性质：
设U，V，W是上的∑正规式，则
(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
(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
5.确定有限自动机：一个确定有限自动机（DFA）M是一个五元式：M = (S, ∑, f, s0, F)，其中：
（1）S是一个有限的状态集合，它的每个元素我们称为一个状态
（2）∑是一个有穷的输入符号的字母表，它的每个元素我们称为一个输入字符
（3）f是从 S×∑ →S的单值部分映射
（4）s0是S的一个元素，为初始状态，它是唯一的
（5）状态集合F是终止状态的集合，它是S的子集(可空)
（2）∑是一个有穷的输入符号的字母表，它的每个元素我们称为一个输入字符
（3）f是从 S×∑ →S的单值部分映射
（4）s0是S的一个元素，为初始状态，它是唯一的
（5）状态集合F是终止状态的集合，它是S的子集(可空)
6.非确定的有限自动机：一个非确定有限自动机（NFA）M是一个五元式M = (S, ∑, f, S0, F)，其中
（1）S是一个有限的状态集合，它的每个元素我们称为一个状态。
（2）∑是一个有限的输入符号的字母表，它的每个元素我们称为一个输入字符。
（3）f是从S×∑*→2S 的部分映射，其中，2S表示S的幂集合（所有S的子集组成的集合）（f是非单值的M是非确定）。
（4）状态集合S0是初始状态集合，它是S的子集。
（2）∑是一个有限的输入符号的字母表，它的每个元素我们称为一个输入字符。
（3）f是从S×∑*→2S 的部分映射，其中，2S表示S的幂集合（所有S的子集组成的集合）（f是非单值的M是非确定）。
（4）状态集合S0是初始状态集合，它是S的子集。
（5）状态集合F是终止状态的集合，它是S的子集。
7.正规式与有限自动机的等价性：
a. 对于任何∑上NFA M都可构造一个∑上的正规式V，使得 L(V) = L(M)。 其中，L(M)是∑上NFA M所能识别的字的全体L(V)是∑上的正规集
b.对于∑上的每一个正规式V，存在一个∑上的DFA M，使得L(M) = L(V) 。
①假定I是M’的状态集的子集，定义I的ε闭包ε_CLOSURE(I)为：
(a)若q∈I，则q∈ε_CLOSURE(I)
(b)若q∈I，那么从q出发经任意条ε弧而能到达的任何状态q’都属于ε_CLOSURE(I) ；
(b)若q∈I，那么从q出发经任意条ε弧而能到达的任何状态q’都属于ε_CLOSURE(I) ；
②假定I是M’的状态集的子集，a ∈ ∑，定义 Ia =ε_CLOSURE(J) 其中，J是所有那些可从I中的某一状态结点出发经过一条a弧而到达的状态结点的全体。
8.确定有限自动机的化简：寻找一个状态比DFA M少的DFA M’，使得L(M’) = L(M)。
步骤：
(1) 检查状态转换函数是否为全函数。
(2) 用化简算法进行化简。
(2) 用化简算法进行化简。
(3) 去掉死状态。
课后习题选做：
第七题第一小题：