compiler-construction - 词法分析器：通过有限自动机实现正则表达式？

Question

问候！

在阅读 Dragonbook 的第 3 章（词法分析）时，我几乎了解了所有内容（他们如何用正则表达式指定标记），直到他们开始谈论有限自动机。它似乎是描述词法分析器的重要部分。

现在我了解了有限自动机的概念，但我不了解它在词法分析器中的作用和用途？为什么不仅仅用正则表达式指定标记？

提前致谢。

Answer 1

正则表达式可以用有限自动机表示，更准确地说可以用确定性自动机表示。

当您编写正则表达式时，词法分析器会将其转换为 DFA 以在文本中查找匹配项。所以当然有限自动机在词法分析器中有它的作用。

有非常简单的算法可以将正则表达式转换为 FA，例如 Thompson 的构造算法 ( http://en.wikipedia.org/wiki/Thompson 's_construction_algorithm)，但您可以找到优化的算法。