03 词法分析 | 《编译原理》笔记

本系列是编译原理 (哈工大陈鄞、郭勇)视频课的课堂笔记，主要是课堂 PPT 和部分讲授内容的文字版，仅供参考。

正则表达式

正则定义

有穷自动机

有穷自动机（finite automata, FA）具有一系列离散的输入输出信息和有穷数目的内部状态。

系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变。

最长子串匹配原则：当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配，即在到达某个终态之后，只要输入带上还有符号，FA 就继续前进，以便寻找尽可能长的匹配。

有穷自动机的分类

• 确定的 FA（deterministic finite automatu, DFA）
• 非确定的 FA（nondeterministic finite automata, NFA）

从表现形式上，NFA 比 DFA 更直观；从计算机实现上，DFA 比 NFA 更容易实现。

从正则表达式到 DFA

从正则表达式先构造 NFA，再通过 NFA 构造 DFA 比较简单。

识别单词的 DFA

错误恢复：从错误中恢复过来，以检测源代码中更多的错误。