flex/lex 分析器生成器：DFA 最小化

Question

flex 或 lex 是否执行 DFA 最小化？

如果是这样，那么我有这些问题：

%{
#include <stdio.h>
%}

%%
a printf("a\n");
b printf("b\n");
%%

这对应于正则表达式 a|b 并且 DFA 构造可以导致具有 3 个状态的 DFA 解析此表达式（JSON 格式）：

{states: [0, 1, 2],
 moves: [
   {from: 0, char: 'a', to: 1},
   {from: 0, char: 'b', to: 2}
 ],
 start: 0,
 final: [1, 2]
}

虽然此 DFA 运行良好，并且对于每个接受状态它都正确调用所需的操作，但 Hopcroft 的 DFA 最小化算法会将两个接受状态合并为一个，这将导致具有两个状态的 DFA。这可能是一个问题，因为那样我们将不知道在接受状态下调用哪个动作。 flex 或 lex 如何处理这个问题？

Answer 1

Flex 没有最小化 DFA，原始 lex 也没有。我不能代表所有可能的 lex 实现。
Hopcroft 算法首先将状态分成两组：接受状态和非接受状态。这些集合显然是不同的，算法的其余部分通过细化分区来进行。由于算法的基础属性，这些分区中只有一个需要重新检查。

在词汇规范的情况下，接受状态也带有一个动作编号，因此接受状态集不能被认为是同质的。相反，初始分区必须分为 N+1 个子集，其中 N 是词法分析器操作的数量。除非只有一个动作，否则这不会是二进制细化，因此基本属性不适用，所有分区都需要重新检查。

另外，经典的Hopcroft算法假设DFA是完备的；每个状态在每个输入上都有一个转换。 (f)lex 生成的 DFA 并非如此。对可以处理此问题的算法进行了修改，或者您可以只向状态集中添加一个接收器状态（所有的输出转换都是循环的）。

flex/lex analyzer generator: DFA minimization