正则表达式到NFA转换：Thompson算法详解

"这篇资料主要介绍了如何通过Thompson算法将正则表达式转换为非确定有限自动机（NFA）。转换过程遵循语言等价原则，包括空字符、单个字符、选择、串联和闭包等操作的处理。资料中还提供了多个示例，展示具体的转换步骤，帮助理解RE到NFA的转换过程，并提到了词法分析程序的构建流程，即从正则表达式定义单词结构，到NFA，再到DFA，最后实现词法分析程序。" 在词法分析中，正则表达式（RE）和有限自动机（Finite Automata，FA）都是重要的工具。正则表达式用于描述程序设计语言的单词结构，易于理解和描述，而有限自动机则便于实际的机器实现，它们在描述能力上是等价的，都能表示正则语言，因此可以相互转换。 Thompson算法是将正则表达式转换为NFA的一种方法，转换过程中遵循语言等价原则： 1. 空字符（ε）：空字符是一个特殊的正则表达式，其对应的NFA只有一个起始状态，没有其他状态，表示接受空字符串。 2. 单个字符c：对于任意字符c，对应的NFA包含一个起始状态和一个结束状态，且有一个边从起始状态到结束状态，标记为c。 3. 选择（或操作）：如果正则表达式为A|B，那么对应的NFA有两个分支，分别对应NFA(A)和NFA(B)，它们共享一个起始状态，并各自有独立的结束状态，中间用ε迁移连接。 4. 串联（与操作）：对于正则表达式AB，NFA(A)的结束状态成为NFA(B)的起始状态，表示先匹配A，再匹配B。 5. 闭包（星号操作）：A*表示A零次或多次出现，NFA包含一个起始状态S0，一个结束状态S，以及从S0到S的ε迁移，从S到S的ε迁移，以及从S0到NFA(A)的边。 资料中通过三个示例详细解释了转换过程： - 示例1：将正则表达式(a|b)*abb(a|b)转换为NFA，涉及到选择和闭包操作，形成一个复合的NFA结构。 - 示例2：将正则表达式a((a|b)*ab*a)b转换为NFA，这个例子包含了串联、选择和闭包操作，NFA结构更加复杂。 - 示例3：将正则表达式(0|1)*00转换为NFA，这个例子展示了数字字符的处理和闭包操作。 这些转换实例有助于理解Thompson算法的实际应用。通常，词法分析程序的构造步骤是首先使用正则表达式定义单词，然后将其转换为NFA，进一步转换为确定有限自动机（DFA），DFA的简化和实现最终生成词法分析程序。