词法分析 - 从直接构建的 DFA 中提取标记
Lexical Analysis - Extraction tokens from DFA constructed directly
一直在看龙书，对将正则表达式直接转换为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
%%
...
我已经实现了算法，想知道如何从中提取标记。我知道当用 Thompson 的构造（龙书的变体）构造的 NFA，然后转换为 DFA 时，您可以从 NFA 中获取标记，说明 DFA 由哪些组成，但我不确定在这种情况下。
(f)lex 描述——事实上，任何词法描述——是正则表达式的集合。但是，所有实用算法都匹配单个正则表达式。这不是问题，因为我们可以简单地构造一个由所有可能标记之间的交替组成的正则表达式。因此，您示例中的前四种模式将组合成
(if|then|else|[a-zA-z][a-zA-Z0-9]*)
Dragon book 中给出的直接正则表达式->DFA 算法适用于增强的正则表达式，通过在正则表达式的末尾添加单个输入结束标记来构建。包含此增强标记位置的状态是接受状态。
这对于算法的描述很方便，但对于实际的分词器的构建不是很有帮助，因为分词器很少到达输入的末尾。它会一直持续下去，直到无法再进行任何转换，此时它会返回到最后一个接受状态。
regex->DFA 算法中的状态对应于原始正则表达式中的位置组。 （如果你写过算法你就知道位置是什么，但是为了其他人一起阅读，位置粗略地说就是刚匹配的字符文字（或通配符）在正则表达式中的偏移量。并非正则表达式中的所有偏移量都是这种意义上的位置；例如，括号和运算符不对应于任何匹配的字符。整个字符 class 文字是单个位置。但考虑位置通常更容易好像它们只是正则表达式本身的字节偏移量。）
这很有用，因为我们可以立即从正则表达式中扫描到达的状态名称中看出。由于组合正则表达式中的每个模式都有不同的位置范围，我们知道我们在哪个规则中。如果模式成功，规则编号会告诉我们选择哪个动作。如果接受状态在多个规则中，我们只选择位置最小的规则，因为这是用于在相同长度的两个最长匹配之间进行选择的 (f)lex 算法：选择扫描器定义中的第一个。
但是，正如我们之前提到的，唯一的接受状态是与增强模式末尾的输入结束标记对应的状态，并且不在任何原始模式中。因此，如果我们想要识别实际模式，我们需要使用自己的结束标记来扩充每个单独的规则，而不是让所有规则共享一个结束标记。此外，结束标记不能仅限于匹配输入末尾的（虚构的）字符，因为我们感兴趣的是最长匹配前缀而不是完整匹配。所以我们必须将结束标记视为匹配任何单个字符，包括虚构的输入结束字符。 （这使它成为比 . 更百搭的通配符，因为 . 只匹配真实的字符，而不匹配虚构的输入结束字符，而且——在真实的 (f)lex 实现中——只匹配真实的恰好不是换行符的字符。但原则上，它是一种通配符，只是它不吸收它匹配的字符。)
所以最终的结果是我们将模式集合转换为：
(if#|then#|else#|[a-zA-z][a-zA-Z0-9]*#)
其中 # 是匹配结束通配符（或者更准确地说，总是成功的零长度断言），如上所述。然后，每个包含一个（或多个）# 通配符的状态都是接受状态。它对应的位置是其名称中对应#的最小位置，应该采取的规则动作是增广模式中包含#.
的那个位置
一直在看龙书，对将正则表达式直接转换为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
%%
...
我已经实现了算法，想知道如何从中提取标记。我知道当用 Thompson 的构造（龙书的变体）构造的 NFA，然后转换为 DFA 时，您可以从 NFA 中获取标记，说明 DFA 由哪些组成，但我不确定在这种情况下。
(f)lex 描述——事实上，任何词法描述——是正则表达式的集合。但是，所有实用算法都匹配单个正则表达式。这不是问题，因为我们可以简单地构造一个由所有可能标记之间的交替组成的正则表达式。因此，您示例中的前四种模式将组合成
(if|then|else|[a-zA-z][a-zA-Z0-9]*)
Dragon book 中给出的直接正则表达式->DFA 算法适用于增强的正则表达式，通过在正则表达式的末尾添加单个输入结束标记来构建。包含此增强标记位置的状态是接受状态。
这对于算法的描述很方便，但对于实际的分词器的构建不是很有帮助，因为分词器很少到达输入的末尾。它会一直持续下去，直到无法再进行任何转换，此时它会返回到最后一个接受状态。
regex->DFA 算法中的状态对应于原始正则表达式中的位置组。 （如果你写过算法你就知道位置是什么，但是为了其他人一起阅读，位置粗略地说就是刚匹配的字符文字（或通配符）在正则表达式中的偏移量。并非正则表达式中的所有偏移量都是这种意义上的位置；例如，括号和运算符不对应于任何匹配的字符。整个字符 class 文字是单个位置。但考虑位置通常更容易好像它们只是正则表达式本身的字节偏移量。）
这很有用，因为我们可以立即从正则表达式中扫描到达的状态名称中看出。由于组合正则表达式中的每个模式都有不同的位置范围，我们知道我们在哪个规则中。如果模式成功，规则编号会告诉我们选择哪个动作。如果接受状态在多个规则中，我们只选择位置最小的规则，因为这是用于在相同长度的两个最长匹配之间进行选择的 (f)lex 算法：选择扫描器定义中的第一个。
但是，正如我们之前提到的，唯一的接受状态是与增强模式末尾的输入结束标记对应的状态，并且不在任何原始模式中。因此，如果我们想要识别实际模式，我们需要使用自己的结束标记来扩充每个单独的规则，而不是让所有规则共享一个结束标记。此外，结束标记不能仅限于匹配输入末尾的（虚构的）字符，因为我们感兴趣的是最长匹配前缀而不是完整匹配。所以我们必须将结束标记视为匹配任何单个字符，包括虚构的输入结束字符。 （这使它成为比 . 更百搭的通配符，因为 . 只匹配真实的字符，而不匹配虚构的输入结束字符，而且——在真实的 (f)lex 实现中——只匹配真实的恰好不是换行符的字符。但原则上，它是一种通配符，只是它不吸收它匹配的字符。)
所以最终的结果是我们将模式集合转换为：
(if#|then#|else#|[a-zA-z][a-zA-Z0-9]*#)
其中 # 是匹配结束通配符（或者更准确地说，总是成功的零长度断言），如上所述。然后，每个包含一个（或多个）# 通配符的状态都是接受状态。它对应的位置是其名称中对应#的最小位置，应该采取的规则动作是增广模式中包含#.