（我只是在学习如何编写编译器，所以如果我提出任何不正确的声明，请纠正我）
当他们可以简单地使用正则表达式时，为什么仍然有人在代码中实现 DFA（goto 语句、表驱动的实现）？据我了解，词法分析器接收一串字符并生成一个标记列表，这些标记在语言的语法定义中是终端，使得它们可以用正则表达式来描述。循环一堆正则表达式，如果找到匹配项就跳出循环不是更容易吗？
问问题
811 次
1 回答
7
你说得对，在很多情况下，写正则表达式比写 DFA 更容易。然而，一个值得思考的好问题是
这些正则表达式匹配器如何工作？
大多数非常快速的正则表达式匹配器实现都是通过在内部编译成某种类型的自动机（NFA 或最小状态 DFA）来工作的。如果您想构建一个扫描器，该扫描器通过使用正则表达式来描述要匹配的令牌然后循环遍历所有令牌，您绝对可以这样做，但在内部它们可能会编译为 DFA。
很少有人真正编写 DFA 来进行扫描或解析，因为它太复杂了。这就是为什么有类似lexor的工具flex，它可以让您指定要匹配的正则表达式，然后在幕后自动编译为 DFA。这样，您就可以两全其美——您可以使用更好的正则表达式框架来描述要匹配的内容，但您可以在幕后获得 DFA 的速度和效率。
关于构建巨型 DFA 的一个更重要的细节是，可以构建一个尝试并行匹配多个不同正则表达式的单个 DFA。这提高了效率，因为可以在字符串上运行匹配的 DFA，同时搜索所有可能的正则表达式匹配。
希望这可以帮助！
于 2013-01-19T23:14:25.510 回答