词法分析器---自动生成器

词法分析器的自动生成器的作用：

• 只需输入合法词的正则表达式，就可以输出一个确定有限状态自动机（DFA）,而DFA的表现形式，往往是一张分析表。
• 有了词法分析器的自动生成器，则可以避免繁琐的单词识别程序，直接对照分析表即可得出yes or no,

解释几个概念：

1. 有限状态自动机（FA）：指的存在有限个状态，并在有限个状态之间跳转的某种数学模型。（从开始状态起，接受某个字符，会跳转相应的状态）
2. 确定有限状态自动机（DFA）：依照上面的定义，不同之处在于跳转的状态是确定的
3. 非确定有限状态自动机（NFA）：跳转的状态是不确定的。

自动生成器的整体结构图：

词法分析器生成器

• 生成器的输入：正则表达式
• 生成器的输出：词法分析器（某种表结构）

有限状态自动机的表示：

• M=(Ε,S,q0,F,δ)
  • E：字母表（接受的字母）
  • S：状态集（一共存在多少种状态）
  • q0：初始的状态
  • F：终结状态集（一共有多少种可接受状态）
  • δ ：转移函数（每个状态接受什么字符跳转什么状态）

有限状态自动机的数据表示形式：

• 有向图
• 跳转表

Thompson算法：

• 算法思想：对简单的RE直接构造FA，对复杂的RE递归的构造FA
  （所以基本上，Thompson算法是递归算法）

有时间再补全

子集构造算法：

• 算法思想：利用图的遍历算法（DFS or WFS），寻找每个状态点在接受某个可接受的字符后，能达到的状态，并组成一个集合

有时间再补全

Hopcroft最小化算法

算法思想： 首先将整个DFA划分成不可接受状态，和可接受状态两个部分，再按照某种标准查看其各自内部会否还有划分的可能，如若没有，则得出了一个最小化的DFA。

有时间再补全