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

     一.总结

       本章我们学习了词法分析的有关知识，编译程序是从单词的级别上来分析和翻译源程序的。词法分析的任务是从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。执行词法分析的程序称为词法分析器。

首先是对词法分析器的要求，包括功能、输出形式、作为一个独立子程序。接下来是词法分析器的设计，包括输入、预处理和单词符号的识别（超前搜索），其中，状态转换图比较重要，因为后面会用到。最后是正规表达式与有限自动机，这也是本章的重点和难点。

正规表达式与正规集相对应，具有相同特征的字组成正规集，正规式是用一种形式化的方法来表示正规集。正规集相同的两个正规式等价。等价正规式之间符合结合律、交换律、分配律等。

确定的有限自动机（DFA）与非确定的有限自动机（NFA）的区别在于映射不同，非确定的有限自动机初态是一个非空集合，而确定的有限自动机的初态是唯一的。DFA是NFA的特例，通过证明可以证，可通过子集法将NFA确定化为DFA（重点）。确定的有限自动机和非确定的有限自动机都可以用状态转换矩阵和状态转换图表示。

正规式与有限自动机的转换也是重点。首先，正规文法与有限自动机具有等价性，对于正规文法G和有限自动机M，如果L（G）=L（M），则称G与M是等价的。须掌握正规式与有限自动机的互相转换。

确定有限自动机的化简：寻找一个状态更少的DFA。注意化简的步骤和算法。

二.课后题

三.感想

        学习了词法分析，感觉自己更加理解编译原理了，好像找到方向了。词法分析的含义和作用很容易理解，但是有限自动机却很难理解，好不容易才理解了确定的有限自动机和非确定的有限自动机的区别，又感觉它们之间的转换很难理解。正规式与有限自动机的等价性容易理解，它们之间的转换又很难，弄懂这些之后，做课后题仍然很吃力。