如何将 regular expressions 应用于非文本 state machine 逻辑？

2026-11-04技术老齐

可以。将事件定义为有限字母表中的符号，提前把正则表达式编译成自动机。运行时只保存当前状态，每收到一个事件就执行一次转换，无需保存历史或把事件拼成字符串。

在微控制器上，建议先在主机端编译正则表达式，再由设备端运行完整的 DFA 转换表。如果 DFA 状态过多，再考虑位向量 NFA。状态标签和超时转换的语义需要单独定义，普通正则匹配器通常无法直接处理。

先确定匹配语义和事件字母表

自动机处理的符号可以是整数、枚举值或其他离散对象，不必是文本。例如：

A_RISE = 0
A_FALL = 1
B_RISE = 2
B_FALL = 3
TIMEOUT = 4

正则语法中的 A_RISE 可以直接代表一个事件，由解析器将名称转换为符号编号，运行时无需构造文本。

设计前需要明确：

从复位开始的全部事件序列，是否必须匹配表达式？
是否允许从任意事件位置开始一次新匹配？
接受状态表示“当前历史满足条件”，还是触发一次动作？
匹配成功后，是继续运行、自动复位，还是锁存输出？
未列出的事件应该被忽略，还是使匹配失败？

例如，A_RISE B_RISE 表示完整序列恰好由这两个事件组成；Σ* A_RISE B_RISE 表示整个历史的最后两个事件依次为它们。其中，Σ 是完整事件字母表。

这些选择会影响初始状态、转换表和输出逻辑。“当前处于接受状态”与“曾经接受过”也有区别，后者需要额外的锁存位。

语法可以保留连接、|、*、+、? 和有界重复等常见写法。任意长度的反向引用通常超出有限自动机的能力；捕获组、贪婪匹配和动作执行，也需要与单纯的接受判定分开处理。

纠正位向量 NFA 中的一个数学细节

NFA 的状态传播使用布尔半环，而不是 GF(2)。

设状态向量为 (v)，事件 (e) 对应的转换矩阵为 (M_e)，所需的 ε 闭包已合并到转换关系中，则：

[ v’_j = \bigvee_i \left(v_i \land M_e[i,j]\right) ]

AND 用于判断路径是否可行，OR 用于合并可达路径。GF(2) 的加法是 XOR，两条路径同时到达同一状态时会相互抵消，不符合 NFA 的语义。

预计算 ε 闭包可以减少运行时工作，但一般的转换矩阵未必能用几次机器字运算处理完：

状态数量增加时，位向量可能跨越多个机器字。
任意转换图的位集计算可能需要扫描多个状态或矩阵行。
预计算后的转换关系可能比原始 Thompson NFA 稠密得多。
Python 大整数运算的成本和内存行为，不能按单个固定宽度寄存器来理解。

因此，需要分别评估“每步成本不随历史长度增长”和“每步耗时恒定”。

有哪些现成工具可用？

Python：用自动机库完成编译和验证

pyformlang 提供正则表达式、ε-NFA 和 DFA 等对象。可以通过 Regex.to_epsilon_nfa()、to_deterministic() 构造自动机，再导出自己的转换表。它有自己的正则语法约定，不能假定与 Python re 或 Perl 完全兼容。

automata-lib 也适合构建和检查自动机，提供 NFA.from_regex()、DFA.from_nfa() 和 read_input_stepwise() 等接口。read_input_stepwise() 主要用于逐步观察给定输入的执行过程。要接收持续到来的硬件事件，可以提取转换表，再编写一个保存当前状态的执行器。

这类库适合在开发机上使用。能否直接运行于 MicroPython，需要检查依赖和运行环境；库本身也不保证硬 IRQ 的延迟或执行过程无内存分配。

C：考虑生成执行代码

可以优先考虑 Ragel。它能根据正则式风格的状态机描述生成 C 等语言的代码，支持动作和分段处理输入。

对于有限事件集合，可以将事件映射为整数符号，再配置合适的输入字母类型。生成的代码会在两次调用之间保留机器状态，无需维护不断增长的字符串。

Ragel 是代码生成器，适合在构建阶段使用。仍需检查生成结果：动作数量是否有上界、是否执行动态分配，以及分支和表访问是否符合目标平台的时间要求。

其他环境：参考底层逐符号接口

Rust 的 regex-automata Automaton 接口展示了如何显式保存状态，并逐字节调用 next_state()。

它主要面向字节正则，并非通用事件对象引擎，其 API 分层仍可借鉴。采用文本引擎时，还要检查结束输入和匹配报告的约定，不能直接把内部状态当作硬件输出。

如何编译为可逐事件推进的对象？

可以按以下流程实现：

在主机端解析正则表达式。
构造 NFA，再确定化为 DFA。
为事件和状态分配连续整数编号。
导出完整转换表、初始状态及输出表。
在设备端实现 reset()、step(event) 和输出查询。

下面用 pyformlang 编译“最近两个事件依次为 A_RISE、B_RISE”这一条件。OTHER 表示归入同一类别的其他事件。

# 在开发机上执行
from pyformlang.regular_expression import Regex

EVENTS = ("A_RISE", "B_RISE", "OTHER")

dfa = Regex(
    "(A_RISE | B_RISE | OTHER)* A_RISE B_RISE"
).to_epsilon_nfa().to_deterministic()

states = list(dfa.states)
state_id = {state: i for i, state in enumerate(states)}

# 为缺失转换补充一个非接受的陷阱状态
dead = len(states)
rows = []

for state in states:
    row = []
    for event in EVENTS:
        targets = dfa(state, event)
        row.append(state_id[targets[0]] if targets else dead)
    rows.append(tuple(row))

rows.append((dead,) * len(EVENTS))

NEXT = tuple(rows)
ACCEPT = tuple(
    int(state in dfa.final_states) for state in states
) + (0,)
INITIAL = state_id[dfa.start_state]

设备端只需保存生成的常量，并运行执行器：

class EventMachine:
    def __init__(self, next_table, accept_table, initial):
        self.next_table = next_table
        self.accept_table = accept_table
        self.initial = initial
        self.state = initial

    def reset(self):
        self.state = self.initial

    def step(self, event):
        # event 必须是合法的连续整数编号
        self.state = self.next_table[self.state][event]
        return self.accept_table[self.state]

执行器保存一个状态编号，不需要历史缓冲区。返回值表示“截至当前事件的整个历史是否被接受”，不会自动锁存或复位。

这段 Python 代码说明了接口和语义，能否满足具体 MicroPython 板卡的硬 IRQ 要求，还需验证。如果需要严格控制分配和执行路径，可以将相同的表和执行器放入 C，并单独审查绑定层。

算法应该怎样选？

设 NFA 有 (m) 个状态，DFA 有 (Q) 个状态，事件类别数为 (k)。

方法	运行时特点	主要取舍
Thompson NFA	保存活动状态集合，逐事件传播并求 ε 闭包	构造简单；常规实现的工作量随活动状态变化
位向量 NFA	用固定大小位集表示活动状态，可安排固定扫描	适合限制资源上界；转换成本取决于图结构和位集大小
Glushkov／位置自动机	状态对应符号出现位置，没有 ε 转换	便于位置标签；转换边最坏可达平方级
子集构造 DFA	完整表下，每个事件执行一次状态转换查询	执行器简单；状态数量最坏呈指数增长
Aho-Sethi-Ullman 的 `followpos` 方法	直接构造 DFA，运行时同样可以查表	省去显式 Thompson NFA，但仍可能发生状态爆炸
Brzozowski derivatives	用导数表示消费一个符号后的剩余语言	适合构造 DFA；需处理表达式简化、去重和状态复用
Antimirov partial derivatives	用偏导数集合构造 NFA	可作为较紧凑的 NFA 路线，仍需处理集合和共享

优先试完整 DFA

完整 DFA 的执行器可以写成：

state = next[state][event];
output = outputs[state];

每个事件的处理成本不随历史长度增长。只要状态编号能用固定宽度整数表示，转换表就约需 (Qk) 个状态编号的存储空间。

判断是否可用，要看实际生成的 (Q)。正则表达式的表面长度不能直接说明自动机规模。可以在编译阶段设置状态数量和表大小上限，超限后再选择其他表示。

不要在硬 IRQ 中使用首次访问时才扩展状态的 lazy DFA，否则确定化、缓存维护或内存分配也会进入运行时。

DFA 太大时，再评估位向量 NFA

位向量 NFA 的活动集合需要 (O(m)) 位，只计算当前状态的存储量，不包括预计算的转换数据。

如果为每个事件、每个源状态保存一个目标位集，转换数据可能需要 (O(km^2)) 位。这部分开销需要与 (O(m)) 位的活动向量分别计算。

需要给表达式位置加标签时，也可以比较位置自动机。它没有 ε 转换，但边数可能更多，是否更快取决于最终表示。

对于 {n} 等计数重复，应按展开后的自动机规模估算资源。很短的表达式也可能描述一台很大的机器。

导数算法适合放在编译阶段

Brzozowski derivatives 可以直接解释逐事件推进的过程：消费一个事件后，表达式变成描述剩余合法序列的新表达式。

直接在 IRQ 中构造和化简表达式，容易涉及分配、哈希和可变工作量。采用这条路线时，可以提前枚举导数状态，最终导出 DFA 表。

如果只需匹配固定事件串，没有复杂的正则结构，也可以考虑 Aho-Corasick。若要求每步查询次数固定，需要检查转换表是否已经补全，避免运行时沿失败链接反复回退。

状态标签不等于捕获组

可以为一组 NFA 状态设置标签位掩码，例如：

waiting = bool(active_states & WAITING_MASK)

它表示“至少一条可行路径处于带有该标签的位置”，语义明确，也容易实现。

捕获组通常还要求确定哪条路径胜出、记录边界或保存匹配内容。NFA 中的一个位置位可能合并多个不同起点的匹配，仅靠活动位无法恢复全部捕获信息。

执行动作时还需明确规则。在尚未确定能成功的 NFA 分支上立即执行 GPIO 写入等副作用，可能产生错误行为。可以采用确定性转换、设置显式优先级，或等结果确定后统一提交动作。

如果标签是可观察输出，DFA 最小化必须保留这些输出。只按接受与否最小化，可能合并业务含义不同的状态。

延迟转换需要独立的时间模型

较容易实现的方案是由调度器把超时作为普通事件送入机器：

A_RISE → 启动定时器
A_FALL → 取消定时器
TIMEOUT_A → 推进自动机

需要明确以下行为：

同一规则能否同时存在多个待到期实例？
再次触发时，是重启定时器，还是增加一个实例？
如何识别取消之后到达的旧回调？
外部事件与超时具有相同时间戳时，先处理哪个？
定时器槽位不足时如何处理？

同一个 NFA 位置可能由不同时间启动的多条路径同时到达。将它们合并为一个活动位，会丢失各自的截止时间；普通子集构造也不会自动补回这些信息。

如果将定时器槽位限制为固定数量，就可以预分配资源，并为每个超时关联槽位或代次标识。如果需要连续时间约束和独立时钟重置，应考虑 timed automata 或具有显式定时语义的状态机。时间离散、计数范围有限时，也可以展开成普通 FSM，但状态数量会增加。

IRQ 延迟上界与计时侧信道要分别验证

完整 DFA 查表在算法层面有明确的上界，但数据相关的表地址仍可能受缓存、Flash 等待周期或总线行为影响，因此不能自动保证抵御计时侧信道的 constant-time 行为。

如果状态属于敏感信息，需要检查分支、访存地址和目标处理器指令的行为。采用固定扫描和固定宽度运算的位向量方案可能更容易审查，但仍须检查编译后的代码；普通 Python 整数操作无法提供这种保证。

工程验证至少应覆盖：

每个合法事件都有确定的转换，未定义事件有明确的处理策略。
初始化、复位、连续接受和失败后的行为符合预期。
每步使用的内存、定时器槽位和动作数量有上界。
IRQ 重入、嵌套或回调并发不会破坏当前状态。
编译后的自动机与参考解释器在代表性事件序列上结果一致。

如果不要求在 IRQ 内立即改变输出，可以让 IRQ 只向预分配的有界队列写入事件，由后台推进自动机。此时还需制定队列溢出的处理策略，并确定端到端延迟的要求。

建议先实现主机端编译器和一个小型表驱动执行器，尽早得到实际的状态数、存储量和每步执行路径，再判断是否需要更复杂的 NFA、标签或定时扩展。