词法分析程序的功能
- 识别组成单词，进行词法检查
- 数字 → 二进制
- 删注释和空格
单词分类
- 保留字
- 标识符（变量名什么的）
- 常数（字符串字面量，布尔常数…）
- 分隔符（+ - * / …）
乔姆斯基文法体系
- 0型 短语结构文法（符号串推符号串） 图灵机
- 1型 上下文敏感 线性界限自动机
- 2型 上下文无关 下推自动机
- 3型 正则 有穷自动机
状态图画法
词法分析方法——有穷状态自动机
只根据当前状态和后续输入，决定下一个状态转移
同时满足多个状态机时：选择最长匹配或显示指定优先级（如保留字优先）
文法与状态图转换
对于左线性文法：
GetSymbol词法分析程序
自动机分类
确定型(DFA)：对于一个输入，状态转移唯一，此情况下的自动机的时间复杂度为O(N)
非确定型(NFA)反之，状态可能有多个
在NFA中引入空字符：S输入之后通过引入空字符可以分流到几个DFA中，简化之后的状态管理，适用于多个DFA组合使用的情况
正则表达式
定义略
正则转εNFA
NFA确定化
状态的子集合I的ε-closure
- s∈I → s∈ε-closure
- 从任意s∈ε-closure出发经过有限条ε弧能到达的所有s∈ε-closure
定义Ia: 从I中所有状态经过一条a弧能到达的状态的集合J 的 ε-closure
构造状态转换矩阵：
初态为start状态的ε-closure，设其为I
接着对所有Vt t求It
对每个未出现的It重复上述操作（就是求个转移状态闭包）
DFA极小化
