读龙书学编译原理词法分析(5)...

时间：2016-05-07 00:58:30 收藏：0 阅读：105

最后是最小化算法, 它的目的其实在于通过合并的方式, 减少状态数, 然后使得最终生成的代码中用来表示状态转移的数据结构尽量小, 以此节约空间和时间. DFA中运用最广泛的算法是hopcroft算法, 接下来就是对该算法的简要介绍...

这个算法的第一步是将所有的状态(也就是代码中的nodes) 划分成两部分, 接收状态和非接收状态 (这两个类中的节点显然不可能合并)... 然后分别遍历两个部分中的所有状态, 对于每一个字符, 如果某个部分中的某个(或者某群)接受了该字符之后转移到了属于另一个部分的状态, 那么就把这个状态(或者这群)分离出来并且构成一个新的部分, 不然的重复该过程知道没有新的部分被构成出来.