# 第三章：词法分析

词法分析器的输入是字符串，输出是 token 。

token 由 type 和 value 两个属性组成。

# 3.1 正则表达式

了解过部分正则表达式可以倍速略过。

正则表达式是描述正则语言更紧凑的方法。

任何正则文法必定存在相应的正则表达式，反之同样成立。

一些正则表达式的例子，例如如何表示数字。

离散的输入输出信息和有穷数目的内部状态。

系统根据当前所处状态和当前面临的输入信息决定系统的后继行为。

FA 接受：对于输入串从初始状态到某个终止状态的转换序列。

最长匹配：例如和分别都匹配上了，那么直接将全部匹配上。

自动机分为确定有穷自动机（DFA）和非确定有穷自动机（NFA）两种类型。

区别在于 DFA 读入一个符号后一定会转向一个确定的状态。而 NFA 读取指定字符后存在多种可能，从多种状态种选一个。甚至空字符也存在状态转换。

DFA 和 NFA 的描述语言是等价的。

表达式由五种成分组成：有穷状态集，输入字母表，转换函数，开始状态，接受状态。

$$ M = (\sum, Q, a, q_0, F) $$

表示符号集。

表示所有状态。也就是状态转换图。

（这个字符不会打，暂用 a 替代）表示状态之间的转换。其实就是一个函数，用于表示每一个状态具体是怎么转换的。

表示开始状态。表示怎么开始。

表示终止状态。表示怎么停止。

有穷自动机既可以用状态转换图表示也可以用转换表（类似于邻接矩阵）表示。

从状态 s 出发按状态 a 出发存在多条路径。

DFA 和 NFA 可以相互转换。

DFA 更容易实现，但是 NFA 更直观。

从正则表达式直接转换到 DFA 是比较难的，可以通过转换成 NFA 再转换成 DFA 实现二者的转换。

有穷状态自动机 DFA 和正则文法是等价的。

DFA 的每个状态是由 NFA 的状态构成的集合，DFA 是 NFA 状态集合的子集。