创建词法分析器的最有效方法是什么？
What is the most efficient way to create a lexer?
我目前正在尝试学习如何手动创建自己的词法分析器。我一直在大量使用 Flex（以及 Bison）来练习和了解它的内部工作原理，但我目前至少看到 3 种不同的解决方案来开发我自己的解决方案。
- 使用 RE 列表，遍历每一个，当一个匹配时，只需 return 关联的标记（参见 python 关于 RE 的文档）
- 从 RE 创建 DFA（例如 Flex：基于 RE，创建一个大状态机）
- 使用大量 switch case 或 if 语句创建我自己的 'state machine'（例如，我认为 Lua 就是这样做的）
我有信心尝试每一种解决方案，但是：
- 是否存在一种解决方案无法解决的情况？
- 在什么情况下您会使用一种解决方案而不是另一种？
- 正如标题所说：哪个生成的代码效率最高？
提前致谢！
当且仅当您设法编写没有任何错误的状态机和 flex 词法描述时，第二个和第三个备选方案将是等效的。 YMMV 但我的经验是编写（和阅读）flex 词法描述要容易得多。
第一个备选方案可能不等价，在一般情况下使其等价并非易事。
问题是如果多个模式与正则表达式匹配会发生什么。 （这个问题在写大量 switch 语句时也会导致细微的错误。）普遍接受的词法策略是在这种情况下使用 "maximal munch" 规则：选择导致最长匹配的模式，如果有不止一个这样的模式，选择在词法定义中最先出现的那个。
作为此规则为何重要的一个简单示例，请考虑一种具有关键字 do 和 double 的语言。观察到理想的行为是：
do { => First token is keyword do
double d; => First token is keyword double
doubt = 0.9; => First token is identifier doubt
在标准 (f)lex 文件中，这将实现为：
"do" { return T_FOR; }
"double" { return T_FOREACH; }
[[:alpha:]_][[:alnum:]_]* { yyval.str = strdup(yytext); return T_ID; }
(F)lex 如果前两个规则恰好处于不同的顺序，则将生成完全相同的扫描器，尽管第三个规则肯定必须在末尾。但是能够重新排序前两个规则更不容易出错。当然，有些人会按照关键词的字母顺序来写他们的词法规则，如上，但其他人可能会选择按句法功能组织关键词，这样 do 就和 for, while、done等，而double与int、char等。采用后一种组织方式，程序员将很难保证重叠关键字以任何特定顺序出现，因此 flex 不关心是有用的；在这种情况下（和许多其他情况一样）选择最长的匹配当然是正确的。
如果您创建一个正则表达式列表并只选择第一个匹配项，则需要确保正则表达式按匹配长度倒序排列，以便匹配最长关键字的排在最前面。 （这会将 double 放在 do 之前，因此按字母顺序排列的关键字将失败。）
更糟糕的是，可能无法立即看出哪个正则表达式具有最长的匹配项。对于关键字来说很清楚——你可以按长度对文字模式进行反向排序——但在一般情况下，最大咀嚼规则可能不是对正则表达式的部分排序：对于某些标记，一个正则表达式可能是这种情况表达式具有最长的匹配，而另一个正则表达式为不同的标记提供了更长的匹配。
作为替代方案，您可以尝试 所有 正则表达式并跟踪匹配时间最长的那个。这将正确地实现最大咀嚼（但见下文）但效率更低，因为每个模式都必须与每个标记匹配。
Python 文档中使用的实际代码，您 link 通过在各种正则表达式之间插入 | 运算符，从提供的模式实际创建单个正则表达式。 （这使得无法使用编号的捕获，但这可能不是问题。）
如果 Python 正则表达式具有 Posix 最长匹配语义，这将等同于最大匹配，但它不是：Python 交替将更喜欢第一个匹配，除非需要稍后的匹配来继续正则表达式：
>>> pat = re.compile("(wee|week)(night|knight)")
>>> pat.match("weeknight").group(1)
'wee'
>>> pat.match("weekknight").group(1)
'week'
要做到这一点，您必须多加注意以确保正则表达式的顺序正确并且不会干扰彼此的匹配。 （并非所有正则表达式库的工作方式都与 Python 相同，但很多都是这样。您需要查看文档，也许还需要做一些实验。）
简而言之，对于一种单独的语言，如果您准备好投入一些工作，您将能够手动构建有效的词法分析器 "correctly"（假设该语言坚持最大咀嚼，因为大多数标准化语言大多都是这样做的），但这绝对是一件苦差事。不只是为了你：对于任何想要理解或验证你的代码的人来说，这将是额外的工作。
因此，就编写代码（包括调试）的效率而言，我认为像 (f)lex 这样的词法生成器是明显的赢家。
有一个长期存在的模因，即手工构建（或开放编码）的词法生成器更快。如果您想对此进行试验，可以尝试使用 re2c，它会生成高度优化的开放编码词法扫描器。 （通过开放编码，我的意思是他们不使用转换 tables。）对于一组给定的词法规则，该理论可能正确也可能不正确，因为基于 table 的词法分析器（由 (f)lex) 产生的代码通常要小得多，因此可以更有效地使用处理器缓存。如果你选择 flex 的快速（但更大）table 选项，那么扫描器的内部循环非常短，只包含一个条件分支。 （但是对单个分支的分支预测不会非常有效）。相比之下，开放编码扫描器在循环中有大量代码，有很多条件分支，其中大部分都相当容易预测。 （不是执行路径长了，而是内循环不够短，无法缓存。）
无论哪种方式，我认为可以合理地说差异不会破坏银行，我的建议始终是使用词法分析器，这对其他人来说更容易阅读，特别是如果你打算问在 SO 上寻求帮助 :-)
我目前正在尝试学习如何手动创建自己的词法分析器。我一直在大量使用 Flex（以及 Bison）来练习和了解它的内部工作原理，但我目前至少看到 3 种不同的解决方案来开发我自己的解决方案。
- 使用 RE 列表，遍历每一个，当一个匹配时，只需 return 关联的标记（参见 python 关于 RE 的文档）
- 从 RE 创建 DFA（例如 Flex：基于 RE，创建一个大状态机）
- 使用大量 switch case 或 if 语句创建我自己的 'state machine'（例如，我认为 Lua 就是这样做的）
我有信心尝试每一种解决方案，但是：
- 是否存在一种解决方案无法解决的情况？
- 在什么情况下您会使用一种解决方案而不是另一种？
- 正如标题所说：哪个生成的代码效率最高？
提前致谢！
当且仅当您设法编写没有任何错误的状态机和 flex 词法描述时，第二个和第三个备选方案将是等效的。 YMMV 但我的经验是编写（和阅读）flex 词法描述要容易得多。
第一个备选方案可能不等价，在一般情况下使其等价并非易事。
问题是如果多个模式与正则表达式匹配会发生什么。 （这个问题在写大量 switch 语句时也会导致细微的错误。）普遍接受的词法策略是在这种情况下使用 "maximal munch" 规则：选择导致最长匹配的模式，如果有不止一个这样的模式，选择在词法定义中最先出现的那个。
作为此规则为何重要的一个简单示例，请考虑一种具有关键字 do 和 double 的语言。观察到理想的行为是：
do { => First token is keyword do
double d; => First token is keyword double
doubt = 0.9; => First token is identifier doubt
在标准 (f)lex 文件中，这将实现为：
"do" { return T_FOR; }
"double" { return T_FOREACH; }
[[:alpha:]_][[:alnum:]_]* { yyval.str = strdup(yytext); return T_ID; }
(F)lex 如果前两个规则恰好处于不同的顺序，则将生成完全相同的扫描器，尽管第三个规则肯定必须在末尾。但是能够重新排序前两个规则更不容易出错。当然，有些人会按照关键词的字母顺序来写他们的词法规则，如上，但其他人可能会选择按句法功能组织关键词，这样 do 就和 for, while、done等，而double与int、char等。采用后一种组织方式，程序员将很难保证重叠关键字以任何特定顺序出现，因此 flex 不关心是有用的；在这种情况下（和许多其他情况一样）选择最长的匹配当然是正确的。
如果您创建一个正则表达式列表并只选择第一个匹配项，则需要确保正则表达式按匹配长度倒序排列，以便匹配最长关键字的排在最前面。 （这会将 double 放在 do 之前，因此按字母顺序排列的关键字将失败。）
更糟糕的是，可能无法立即看出哪个正则表达式具有最长的匹配项。对于关键字来说很清楚——你可以按长度对文字模式进行反向排序——但在一般情况下，最大咀嚼规则可能不是对正则表达式的部分排序：对于某些标记，一个正则表达式可能是这种情况表达式具有最长的匹配，而另一个正则表达式为不同的标记提供了更长的匹配。
作为替代方案，您可以尝试 所有 正则表达式并跟踪匹配时间最长的那个。这将正确地实现最大咀嚼（但见下文）但效率更低，因为每个模式都必须与每个标记匹配。
Python 文档中使用的实际代码，您 link 通过在各种正则表达式之间插入 | 运算符，从提供的模式实际创建单个正则表达式。 （这使得无法使用编号的捕获，但这可能不是问题。）
如果 Python 正则表达式具有 Posix 最长匹配语义，这将等同于最大匹配，但它不是：Python 交替将更喜欢第一个匹配，除非需要稍后的匹配来继续正则表达式：
>>> pat = re.compile("(wee|week)(night|knight)")
>>> pat.match("weeknight").group(1)
'wee'
>>> pat.match("weekknight").group(1)
'week'
要做到这一点，您必须多加注意以确保正则表达式的顺序正确并且不会干扰彼此的匹配。 （并非所有正则表达式库的工作方式都与 Python 相同，但很多都是这样。您需要查看文档，也许还需要做一些实验。）
简而言之，对于一种单独的语言，如果您准备好投入一些工作，您将能够手动构建有效的词法分析器 "correctly"（假设该语言坚持最大咀嚼，因为大多数标准化语言大多都是这样做的），但这绝对是一件苦差事。不只是为了你：对于任何想要理解或验证你的代码的人来说，这将是额外的工作。
因此，就编写代码（包括调试）的效率而言，我认为像 (f)lex 这样的词法生成器是明显的赢家。
有一个长期存在的模因，即手工构建（或开放编码）的词法生成器更快。如果您想对此进行试验，可以尝试使用 re2c，它会生成高度优化的开放编码词法扫描器。 （通过开放编码，我的意思是他们不使用转换 tables。）对于一组给定的词法规则，该理论可能正确也可能不正确，因为基于 table 的词法分析器（由 (f)lex) 产生的代码通常要小得多，因此可以更有效地使用处理器缓存。如果你选择 flex 的快速（但更大）table 选项，那么扫描器的内部循环非常短，只包含一个条件分支。 （但是对单个分支的分支预测不会非常有效）。相比之下，开放编码扫描器在循环中有大量代码，有很多条件分支，其中大部分都相当容易预测。 （不是执行路径长了，而是内循环不够短，无法缓存。）
无论哪种方式，我认为可以合理地说差异不会破坏银行，我的建议始终是使用词法分析器，这对其他人来说更容易阅读，特别是如果你打算问在 SO 上寻求帮助 :-)