我一直在读龙的书，对将正则表达式直接转换为DFA(没有显式NFA(的算法非常感兴趣。假设我的词法文件布局类似于 lex：
...
%%
if { return IF_TOK; }
else { return ELSE_TOK; }
then { return THEN_TOK; }
[a-zA-z][a-zA-Z0-9]* { return IDENT; }
...more tokens
%%
...
我已经实现了该算法，并想知道如何从中提取令牌。我知道，当用汤普森的构造(龙书的变体(构建的NFA然后转换为DFA时，您可以从DFA组成的NFA状态获得令牌，但我不确定在这种情况下。
(f(lex 描述 - 实际上，任何词汇描述 - 都是正则表达式的集合。但是，所有实用算法都匹配单个正则表达式。这不是问题，因为我们可以简单地构造一个由所有可能的标记之间的交替组成的单个正则表达式。因此，示例中的前四种模式将合并为
(if|then|else|[a-zA-z][a-zA-Z0-9]*)
Dragon 书中给出的直接正则表达式->DFA 算法适用于增强正则表达式，通过在正则表达式末尾添加单个输入结束标记来构造。包含此增强标记位置的状态是接受状态。
这对于算法的描述很方便，但对于实际的分词器的构造不是很有帮助，因为分词器很少到达输入的末尾。它只是继续运行，直到无法进行更多的转换，此时它会备份到最后一个接受状态。
正则表达式->DFA 算法中的状态对应于原始正则表达式中的位置集。(如果你已经编写了算法，你就知道位置是什么，但为了其他人一起阅读，位置大致是指刚刚匹配的字符文字(或通配符(正则表达式中的偏移量。在这个意义上，并非所有正则表达式中的偏移量都是位置;例如，括号和运算符不对应于任何匹配的字符。整个字符类文字是一个位置。但是，通常更容易将位置视为正则表达式本身中的字节偏移量。
这很有用，因为我们可以从正则表达式中扫描到达的状态名称中立即看到。由于组合正则表达式中的每个模式都有不同的位置范围，我们知道我们处于哪个规则中。如果模式成功，规则编号会告诉我们要选择哪个操作。如果接受状态在多个规则中，我们只选择位置最小的规则，因为这是 (f(lex 算法，用于在两个相同长度的最长匹配之间进行选择：选择扫描程序定义中的第一个。
但是，正如我们前面提到的，唯一的接受状态是对应于增强模式末尾的输入结束标记的状态，并且不在任何原始模式中。因此，如果我们想识别实际模式，我们需要用自己的结束标记来增强每个单独的规则，而不是让所有规则共享一个结束标记。此外，结束标记不能仅限于匹配输入末尾的(虚构(字符，因为我们感兴趣的是最长的匹配前缀而不是完全匹配。因此，我们必须将结束标记视为匹配任何单个字符，包括虚构的输入结束字符。(这使得它成为比.更宽泛的通配符，因为.只匹配真实的字符，而不是虚构的输入结束字符，而且 - 在真正的(f(lex实现中 - 只匹配碰巧不是换行符的真实字符。但原则上，它是一种通配符，只是它不吸收它匹配的字符。
因此，最终结果是我们将模式集合转换为：
(if#|then#|else#|[a-zA-z][a-zA-Z0-9]*#)
其中#是匹配结束通配符(或者更准确地说，总是成功的零长度断言(，如上所述。然后，包含一个或多个#通配符的每个状态都是接受状态。它对应的位置是它名称中对应于#的最小位置，而应该采取的规则操作是其增强模式包括该#的那个。