编译原理第三章词法分析总结
一.
1.词法分析任务：从左至右逐个字符的对源程序进行扫描，产生一个个的单词符号，
把作为字符串的源程序改造成为由单词符号串组成的程序。
2.词法分析器的功能和输出形式 源程序——》词法分析器——》单词符号
1.单词符号 2.单词种类
3.单词的表示形式 用二元式来表示 <单词种别，单词符号的属性值>
单词符号的属性：指单词符号的特性或特征。
单词符号的属性值：反映单词特性或特征的值。
4. 状态转换图法
(1)状态转换图：一张有限方向图
(1)状态转换图：一张有限方向图
(2)状态转换图的功能
识别（接受）一定的符号串（单词）
识别（接受）一定的符号串（单词）
二.正规式与正规集
超前搜索：在单词识别的过程中，通过向前多读几个符号的形式，准确的进行单词的识别，一旦确定识别到的单词之后，需要进行扫描指针的回退，保证单词识别工作的顺利进行。
状态转换图：一张有限方向图
正规集：具有相同特征的字放在一起组成的一个集合
正规式：表示正规集的一种形式化的方法
确定的有限自动机：
一个确定有限自动机（DFA）M是一个五元式：
M =(S, ∑, f, s0, F)，其中
1)S是一个有限的状态集合，它的每个元素我们称为一个状态。
2)∑是一个有穷的输入符号的字母表，它的每个元素我们称为一个输入字符。
3)f是从 S×∑ →S的单值部分映射。
4)s0是S的一个元素，为初始状态，它是唯一的。
5)状态集合F是终止状态的集合，它是S的子集(可空)。
非确定的有限自动机：
一个非确定有限自动机（NFA）M是一个五元式
M =(S, ∑, f, S0, F)，其中
1)S是一个有限的状态集合，它的每个元素我们称为一个状态
2)∑是一个有限的输入符号的字母表，它的每个元素我们称为一个输入字符
3)f是从S×∑*→2S 的部分映射，其中，2S表示S的幂集合（所有S的子集组成的集合）
（f是非单值的àM是非确定）
（f是非单值的àM是非确定）
4)状态集合S0是初始状态集合，它是S的子集
5)状态集合F是终止状态的集合，它是S的子集
三.课后题12（b）
四.总结
要学习第三章先要知道正规式、正规集，等价、可区别子集等概念才能完成状态图表的转换以及确定化和化简等，进而构造DFA。前两节知识偏向理论，需要了解着进行记忆，第三节正规式和有限自动机偏向逻辑性，需要学会解题。做了几个题后感觉大部分还可以，部分题目难度较大，需要加强锻炼。总体来说学完第三章对编译原理这门学科有了进一步的了解，编译原理这门课是十分注重基础的，只有基础学好了，才能够更加简单的理解后面要学的。