复习（预习）编译原理笔记
2 词法分析器
2.1 FA & RE
编译器的词法分析器读取字符组成的输入流，产生包含单词的输出流。每个单词都标记其语法范畴，等效于英文单词的词类。因此词法分析器会应用一组描述输入程序设计语言的此法结构规则。
语法范畴
关键字
状态转移图充当了状态转换、代码的抽象。转移图可以看成是形式化的数学对象，也就是有限自动机。
有限自动机（finite automaton）
有限状态机包含一个有限状态集、一个字母表、一个转移函数、一个起始状态和一个或多个接受状态
为了能够形式化的表达转移图，使用正则表达式来描述其语言
符号表示法的形式化，一个正则由三个基本操作组成：
- 选择：
- 连接：
- 闭包：
优先级是从下往上越来越低
正则表达式和有限状态机是等价的，也就是说FA和RE是等价的，因此我们需要手段能够在FA & RE之间进行转换。
2.2 RE & FA & NFA & DFA
从正则到NFA再到DFA，
先介绍两种NFA的概念，再继续向内进行深入。
- NFA：对单个字符的输入有多种可能的状态转换，这种是非确定性有限自动机
- DFA：对单个字符的输入只有一种可能的状态转换，这种是确定性有限自动机
从RE（正则表达式）到NFA的转换，即Thompson构造法，Thompson构造法显示制造了连接、选择、闭包的NFA转换。使用Thompson构造法直接按照优先级将正则表达式转化为NFA。简单来说Thompson是最简单的构造方法。
从NFA到DFA的转换，子集构造法。子集构造法实际上是从每个配置到具体状态的转换。
简化DFA到最小DFA：Hopcroft算法
Hopcroft算法的理论基础是如果某两个复杂DFA的状态属于同一个集合，那么这两个状态对于同样的字符输入必然指向另一个集合。我们最终的目的就是按照这些集合来简化DFA
2.4 实现词法分析器
常见的词法分析器三种：
- 表驱动的词法分析器：两个表，字母表和状态转移表，按照这个来驱动并且回退
- 直接编码的词法分析器：实际上就是优化了上面两个表，字母表可以直接利用数组的性质计算出来。转移表直接用代码来表示然后互相goto
- 手工编码的词法分析器：手工编码的词法分析器减少了词法分析器和系统其余组件的接口花销，实际上手工就是为了实际接口的花销
2.5 高级主题
为了说明RE和DFA是等价的，我们需要从DFA构建正则表达式，即Kleene构造法，该构造法本质就是利用从小到大的推到
DFA最小化的另一方法，Brzozowski算法
3 语法分析器
3.1
结尾
唉，尴尬
