正则表达式

正则表达式从“怎样组成一个合法字”出发描述语言。并表示备选结构，连接表示先后相邻，星表示把同一类片段重复任意有限次。它像一套语言代数，而不是一段逐字符执行的命令；实际匹配器采用 DFA、NFA 或回溯，只是计算这个集合语义的不同实现。

递归语法也规定了证明方法。要证明所有正则表达式都具有某个性质，只需验证三个基本表达式，再证明性质在并、连接与星下保持。Thompson 构造、可空性判断和 Brzozowski 导数都沿表达式树递归，正因为它们复用了这条结构归纳原则。

星号表达无界次数，却仍只需有限描述，因为各次重复无需彼此比较，自动机沿一个环即可处理任意多次。要求两个相隔很远的无界片段精确相等、嵌套配对或复制内容时，所需记忆才会越过正则边界；单纯增加重复次数不会。

许多程序语言的 ASCII 标识符规则可写成

工程语法常缩写成 [A-Za-z_][A-Za-z0-9_]*。第一段单独列出，用来禁止数字开头；第二段取星，允许只含一个首字符。这个表达式覆盖全部合法标识符，而非只枚举几个示例名字。

表达式 $(0\mid 1{)}^{\ast }01$ 描述所有以 01 结尾的二进制字。它的星只作用于括号内的单字符选择，而末尾 01 必须出现一次。相比之下，$(ab{)}^{\ast }$ 只含 $\epsilon ,ab,abab,\dots$，不包含 aabb；括号改变的是重复单元，而非视觉分组。

几个空对象值得单独核对：${\varnothing }^{\ast }=\{\epsilon \}$，因为零次重复仍合法；${\epsilon }^{\ast }=\{\epsilon \}$，因为重复空字不会产生新字；$R\varnothing =\varnothing$，而 $R\epsilon$ 与 $R$ 语义相同。忽略这些边界会让递归构造在空分支和可选片段上出错。

经典正则表达式不能描述任意深度的平衡括号，也不能描述 $\{ww:w\in \{0,1{\}}^{\ast }\}$。某些编程语言的 regex 提供反向引用、递归子模式或任意代码断言，它们可以超出正则语言；环视若只表达正则约束则未必超出，但具体引擎的语义必须逐项分析，不能只凭“regex”这个名字套用定理。

实现复杂度也要与表达能力分开。一个语言完全正则，回溯式引擎仍可能因表达式结构走指数多条搜索路径；转换为 DFA 或采用 Thompson NFA 模拟可给出线性扫描界，但可能换来更大的状态表或不同的捕获语义。

有限状态自动机公理库有限状态自动机Finite-state automaton · Finite automaton · Finite-state machine用有限个控制状态概括已读前缀，并沿带输入标号的转移识别有限字的模型家族。与经典正则表达式在有限字语言的描述能力上等价。Kleene 定理公理库Kleene 定理Kleene's theorem经典正则表达式描述的有限字语言恰好是有限自动机能够识别的语言。分别通过 Thompson 构造和状态消除证明双向翻译；这里的 equivalent_to 关系只承诺语言类相同，不把表达式语法、机器运行或表示大小等同起来。

词法分析器通常把每类 token 写成正则表达式，合并为 ε-NFA，再确定化并按优先级处理多个接受规则。日志过滤、协议字段校验与字符串搜索也使用同一链条。若任务需要递归嵌套或跨片段相等，应尽早改用文法、栈自动机或显式解析，而不是继续堆叠难以验证的引擎扩展。