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

知识点：

        1、什么是词法分析？词法分析就是将输入的源程序从左至右进行扫描转换成单词符号并输出。单词符号是一个程序语言的基本语法符号，分为关键字、标识符、常数、运算符和界符。

        2、表示形式：<单词种别，单词符号的属性值>

            单词种别常用整数编码来表示，比如关键字、运算符、界符采用一字一种编码的方式，常数按类型分别给出编码，标识符同归一种，只给一个编码。

        3、词法分析器的结构：

            输入缓存区：词法分析的工作的工作可以直接在这里进行。

            预处理子程序：处理掉其他不必要的成分。

            扫描缓冲区：进行单词符号的识别，由起点指示器和搜索指示器组成。

        4、单词符号的识别可以采用超前搜索、直接分析、状态转换图等方法。

       在进行单词识别的过程中，检测该单词是什么类别是一项十分重要的任务，在这里就引入了超前搜索的概念。超前搜索就是在单词识别过程中，向前多度几个符号的形式，一次来准确的进行单词的的识别。一旦确定识别到的单词之后，需要进行扫描单词的回退，来保证单词识别工作的顺利进行。

        直接分析法就是先判断语句中的第一个字符，然后根据这个字符进行效应的操作。

        状态转化图是一张有限方向图，能识别（接受）一定的符号串或单词。它有结点、箭弧和箭弧上的标记组成。结点表示状态，用圆圈表示，结点之间用箭弧连接，箭弧上的标记表示在射出结点下可能出现的字符或字符串。

        5、正规表达式：

        相同特征的字放在一起组成的集合叫做正规集，用形式化的方法来表示正规集叫做正规式。即正规式是描述单词结构的一种形式。设L(U)，L(V)是正规集，则正规式可能为或(U|V)、连接(UV)、闭包-任意有限次自重复连接(v)*。若U和V的正规集相同，则认为二者等价，记做U=V。

        正规式的性质：交换律、结合律、分配律、空·U=U。

        6、形式化的状态转化图叫做有限自动机。分为确定有限自动机DFA、非确定的有限自动机NFA。

        DFA和NFA 的区别和联系：当输入任何一个可以的自复式，DFA可以得到一个固定的状态，而NFA会得到一个状态的集合，其中NFA中包含空字ε。NFA去掉空字ε可以转换成DFA，DFA是特殊的NFA。

        7、如何简化DFA：将状态转化图箭弧上得标记从单个状态合并成一个正规式。

课后题：

总结：

        词法分析是编译程序的第一步，目的是将句子中的单词、符号、数字等筛选出来以供后续的操作使用。三种识别单词的方法中，有限自动机最有意思，它和正规式等价，既可以有有限自动机推导出正规式，又可以用正规式推导出自动机。而自动机中的NFA转化DFA和DFA的化简又是这一章的重点。NFA转化DFA的关键就是由NFA推导出状态转换矩阵，再由矩阵对自动机重新编排，得到对应的DFA。而DFA的化简就是消除中间状态争取以最短的状态得到最终结果。