编译原理正规表达式转NFA算法

### 编译原理中的正规表达式转换为NFA

在编译原理中，将正规表达式（Regular Expression, RE）转换成非确定有限自动机（Non-deterministic Finite Automaton, NFA）是一个重要的过程。此过程中采用的方法之一是通过算符优先算法来构建NFA[^1]。

#### 构建NFA的基本原则

对于给定的正规表达式，可以按照特定的原则将其逐步分解并映射到相应的子NFA上：

- **字符匹配**：如果正规表达式仅由单个字符`a`组成，则创建一个简单的两状态机器，其中有一个从初始状态指向接受状态的标记为`a`的边。

- **连接操作**：当遇到两个连续的符号或更复杂的结构时，如`ab`，那么前一部分对应的NFA的结束节点会变成下一部分起始节点的一部分；即第一个模式串对应NFA的终止状态变为第二个模式串所代表NFA的起点[^3]。

- **选择分支**：面对竖线分隔的选择项，比如`a|b`，需要引入一个新的开始点和终点，并分别向这两个选项各自的NFA提供ε-moves作为过渡路径。

- **闭包处理**：星号(`*`)表示零次或多次数重复前面的内容。为此，在相应位置设置循环回路即可满足需求——让当前部分既能继续前进也能返回重新尝试该片段。

为了实现上述逻辑，通常还需要先将输入字符串解析为逆波兰表示形式（Reverse Polish Notation），这有助于简化后续计算流程[^4]。

from collections import deque

class State:
    def __init__(self, is_accepting=False):
        self.transitions = {}
        self.is_accepting = is_accepting
        
def re_to_nfa(postfix_expr):
    stack = []
    
    for char in postfix_expr:
        if char.isalnum():  # 字母数字直接生成简单NFA
            start_state = State()
            end_state = State(is_accepting=True)
            start_state.transitions[char] = {end_state}
            nfa_pair = (start_state, end_state)
            
        elif char == '|':  # 或者关系
            right_end, right_start = stack.pop()
            left_end, left_start = stack.pop()

            new_start = State()
            new_end = State(is_accepting=True)

            new_start.transitions[''] = {left_start, right_start}  # ε-move
            
            for state in [left_end, right_end]:
                state.transitions[''].add(new_end)

            nfa_pair = (new_start, new_end)
                
        elif char == '.':  # 连接操作
            right_end, right_start = stack.pop()
            left_end, left_start = stack.pop()

            left_end.transitions[''].add(right_start)  # 将左边结尾连至右边开头
            
            nfa_pair = (left_start, right_end)
        
        elif char == '*':  # 星号闭包
            single_end, single_start = stack.pop()

            new_start = State()
            new_end = State(is_accepting=True)

            new_start.transitions[''] = {single_start, new_end}  # 可选跳过整个序列
            single_end.transitions[''].add(single_start)         # 循环回到自身头部
            single_end.transitions[''].add(new_end)              # 结束后可到达最终态

            nfa_pair = (new_start, new_end)
            
        else:
            raise ValueError(f"未知的操作符 '{char}'")

        stack.append(nfa_pair)
        
    return stack[-1][0], set([stack[-1][-1]])

这段Python代码展示了如何根据不同的运算符建立不同类型的NFA组件，并利用栈数据结构管理这些中间结果直到完成整个RE到NFA的转化。