Compilers_Chapter3总结

本书的第三章主要介绍了编译器中的词法分析部分。而且，主要是原理的讲解，这些东西，在任何一本计算机理论的书中都有更为详细的介绍（主要是有限状态自动机部分）。
1、Tokens。词法分析器顺序扫面输入程序，产生的结果就是一个token的序列。一般而言，这些token是一次一个地传递给语法分析器的。有些token只有一个token名，而另一些还可能有与之关联的词法值（token的属性值），这个值给出了源程序中关于这个token的额外的一些信息。
2、词。每次词法分析器向语法分析器返回token的时候，该token都对应了一个源程序中的字符序列，这个序列就叫做词。
3、缓冲。词法分析器为了加快速度，通常都会对输入文件进行缓冲，而不是一次一个字符地读取。该缓冲有一点特殊的要求，因为词法分析可能需要向前多看若干个字符（lookaheads）才能确定下一个要返回的token及其对应的词。所以，大部分词法分析器使用了一个双缓冲，这两个缓冲轮流使用，以保证在必要的时候lookahead可以回退。另外，为了加速缓冲的管理，这两个缓冲一般使用“哨兵”的方式来判断是否已到缓冲的结尾。
4、模式。每一个token都对应一个模式，该模式用于描述什么样的字符序列可以形成这个token对应的词。对应于同一个pattern的所有的字符序列的集合称为一个语言。
5、正则表达式。正则表达式是用于描述模式的一种规范形式。基础的正则表达式又相应字母表的单个字幕，代表空语言的“phi”，代表空串的“epsilon”组成，其他的正则表达式使用连接、并、kleen闭包三种运算由更小的正则表达式组成。
6、正则定义。正则定义用于描述比较复杂的一组语言。例如某个程序设计语言的所有的token。正则定义是用正则表达式定义“变量”的一系列的语句，该变量就代表了定义它的正则表达式。每一个定义都可以使用前面已经定以过的变量，但不能使用自己正在定义的变量以及后面定义的变量（这个主要是避免递归定义，这在正则表达式中是不允许的）。
7、扩充的正则表达式。在实际的应用中，工具程序识别的正则表达式通常都增加了一些扩展记号。这些记号组成的表达式都可以用定义中的三种操作实现，它们的出现只是为了更加方便。参与lex、grep、awk等。
8、状态转换图。其本质就是自动机的状态转换图，用于描述词法分析器的行为。
9、有穷状态自动机、确定型的和非确定型的。这部分的理论是词法分析的基础。但是，要小心，严格来讲其实自动机的状态转换图和用于描述词法分析器的状态转换图是略有不同的。主要就在于：自动机的所有的接受状态都表示同样的信息，而描述词法分析器的状态转化图的不同接受状态可能代表了接受不同的token。这是不同的，在DFA的最小化算法中要注意这个不同，否则会出现问题。
10、不同表示之间的互相转换。理论上，正则表达式，NFA，DFA定义了相同的语言族，并且，他们之间也互相有机械的转换算法。DFA还有进一步的最小化算法（将状态数目最小化）
11、lex。有一类软件工具称为“词法分析器生成器”，它们可以让用户使用方便的扩展的正则表达式来制定各个token的描述，然后自动的生成一个识别这些token的词法分析器。这个生成的分析器一般模拟一个确定的有限状态自动机。
个人觉得，其实词法分析的原理还是比较简单的。难的地方在于许多细节的处理，以及对算法实现的优化。比如，本章的最后由一个用于保存转换图的数据结构，似乎比较巧妙的样子，我还没有看懂。有人明白的话希望不吝赐教。