最近在学习Flex词法分析器(flex-2.6.0版本),我使用如下简单的 .l文件来跟踪代码的执行,研究DFA转换表的构造过程
...
%%
[aeiou]+ {printf("aeiou");}
^r {printf("^r");}
%%
...
在看到ntod函数(NFA到DFA的转换)之前,各个等价类的创建过程都清楚,但是我看不明白sympartition和symfollowset函数的具体实现细节。在这之前已经得到起始状态的epsilon闭包,我知道这两个函数肯定是为了得到之后状态的epsilon闭包,但是我不清楚其中实现的意思,能否详细解释一下这两个函数呢?
上述的 .l文件创建了3个等价类: aeiou, r 和 . sympatition中的ccltbl已经是其等价类的下标了,那用mkeccl得到的duplist是用来做什么呢? duplist[sym] == NIL为什么代表有唯一的out-transition呢?
上述.l 文件的NFA的状态如下
********** beginning dump of nfa with start state 11
state # 1 257: 0, 0
state # 2 257: 0, 0
state # 3 -1: 4, 0
state # 4 257: 3, 0 [1]
state # 5 257: 1, 3
state # 6 114: 7, 0
state # 7 257: 0, 0 [2]
state # 8 257: 2, 6
state # 9 -2: 10, 0
state # 10 257: 0, 0 [3]
state # 11 257: 5, 9
********** end of dump