总体介绍
词法分析（Lexical Analysis）词法分析器的主要任务是识别源代码中的各种词法 单元，词法单元是源程序代码中的最小语法单位，如关键字、标识符、常量、运 算符等，并将它们转换为标记(token)
正则表达式
什么是正则表达式
正则表达式由普通字符（如字母、数字）和特殊字符（如元字符）组成，可以用来进行字符串匹配、查找、替换等操作。
在编译器中， 正则表达式通常用于词法分析阶段，用于定义词法单元（tokens）的模式
正则表达式的数学定义
举例
定义扩展
有限状态自动机(FA)
什么是有限状态自动机
- 有限自动机是依据某些输入而改变状态的机器或程序。可以用状态转换图来描述
- 有限自动机是有向图这种通用结构的一个实例，在动态数据结构和高级搜索方面有许多应用
状态转换图
- 是一个有向图，结点表示状态，用圆圈表示
- 用双圆圈表示识别结束
- 用带 * 的双圆圈表示识别结束，并且需要回退1个字符
- 结点之间可以用有向边连接
- 有向边上标记影响状态改变的可能输入的字符
举例
不确定的有限自动机(NFA)
数学定义
注意：接收状态集合F是指双圆圈（上图是2）
NFA的转换表
例子
确定的有限自动机(DFA)
数学定义
注意：NFA与DFA的初始状态S0都是唯一的
NFA到DFA的等价变换
子集法
定义
举例
注意：ε-closure{a}包含a本身
构造NFA状态K的子集的算法
例子
DFA 最小化
定义
- 确定有限自动机（DFA）最小化是指将一个给定的DFA转换为等价的具有最少状态数的DFA的过程。
- 最小化DFA的主要目的是简化自动机的结构，减少状态数，提高匹配效率
Hopcroft 算法
定义
- 基于等价状态划分法
- 对于每一对不同的状态 (p,q)，如果 (p,q) 在任意输入符号下转移到相同的状态属于相同等价类，则将 (p,q) 划分到相同类中；如果 (p,q) 在任意输入符号下转移到的状态分别属于不同的等价类，则将 (p,q) 划分到不同的等价类中
详细描述
例子
正则表达式与有限状态自动机
关系
- 正则表达式简洁抽象
- 有限状态自动机直观形象
正则表达式到NFA转换
Thompson 构造算法
定义
例子
词法分析器的实现方法
手写词法分析器
通过有限自动机的状态转换表手写（难度大、精干运行效率高）
eg：GCC,LLMV
词法分析器生成工具
通过编写词法规则描述文件，使用工具自动生成词法分析器的代码
常见的词法分析器生成工具有：
- Lex / Flex：用于生成C语言的词法分析器
- JLex / JFlex：用于生成Java语言的词法分析器
- ANTLR：支持多种编程语言的词法分析器生成
构建词法分析器的一般步骤
- 用正规式对程序设计语言单词模式进行描述
- 使用Thompson构造法，根据正则表达式构建对应的NFA。包括构建基本的NFA，连接操作、或操作和闭包操作等；如果有多个正则表达式，则用规则3将不同的NFA合并连接为一个NFA
- 使用子集构造法（subset construction）将NFA 转换为 DFA
- 简化DFA，使其状态数最少
- 从化简后的DFA构造词法分析程序