我有兴趣学习如何编写像 flex 这样的词法分析器生成器。我一直在阅读“编译器:原理、技术和工具”(“龙书”)，并且对 flex 的工作原理有了基本的了解。
我最初的方法是这样的:用户将提供一个正则表达式的哈希映射，将正则表达式映射到 token 枚举。该程序将按照给定的顺序一个一个地循环遍历正则表达式，看看它们是否与字符串的开头匹配(我可以在每个正则表达式的开头添加一个 ^ 来实现这一点)。如果他们这样做，我可以将该正则表达式的 token 添加到程序的 token 列表中。
我的第一个问题是，这是最有效的方法吗？目前我必须遍历每个正则表达式，但理论上我可以从所有正则表达式组合构建一个 DFA，并更有效地逐步完成。但是，创建此 DFA 会产生一些开销。
我的第二个问题是，我将如何实现最长匹配的字符串决胜局，就像 flex 那样？即，我想匹配 ifa 作为标识符，而不是关键字 if 后跟字母 a 。我看不到使用正则表达式执行此操作的任何有效方法。我想我必须遍历所有的正则表达式，尝试匹配它们，如果我有多个匹配项，则取最长的结果。但是，如果我将正则表达式转换为 DFA(即我自己的 DFA 数据结构)，那么我可以继续遍历字符，直到 DFA 上不再有可能的过渡边。那时，我可以将最后一次通过接受状态作为 token 的实际匹配，因为那应该是最长的匹配。
我的两个问题都指向编写我自己的从正则表达式到 DFA 的翻译器。这是必需的，还是我仍然可以使用普通的正则表达式(由标准库实现)有效地执行此操作并仍然获得最长的匹配？
编辑:我保留了我正在使用的正则表达式引擎，因为我想要一个通用的答案，但我使用的是 Rust 的正则表达式库:http://static.rust-lang.org/doc/master/regex/index.html
最佳答案
时间上，将所有正则表达式编译成一个自动机，并行匹配所有模式会更有效率。但是，它可能会显着增加空间使用量(DFA 可以具有相对于模式大小成指数级的多个状态)，因此值得调查这是否会造成伤害。
通常，您实现 maximal-munch(匹配最长的字符串)的方式是正常运行匹配的自动机。跟踪您找到的最后一个匹配项的索引。当自动机进入死状态并停止时，您可以输出从标记开头到匹配点的子串，然后在匹配完成后立即跳回到输入序列中的点。这可以非常有效地完成，而且根本不会减速。
如果有帮助，here are some lecture slides from a compilers course I taught 探索扫描技术。
希望这可以帮助!
关于regex - 如何在词法分析器生成器中有效地实现最长匹配？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23977046/