正则表达式

正则表达式 是一种用于表示匹配简单文本模式的字符串的便捷记法。表达式 $a^*ac^*b^*$ 展示了四种正则表达式操作中的两种：连接（通过并置表示）和克林闭包（Kleene star）。其余两种操作出现在以下递归定义中。

形式化定义

1. 以下都是正则表达式：

   a) $\phi$，表示空语言/集合 $\{ \}$

   b) $\lambda$，表示仅含一个字符串的语言/集合 $\{\lambda\}$

   c) 每个字母表 $\Sigma$ 中的字符 $c$，表示语言/集合 $\{c\}$

2. 若 $r, r_1, r_2$ 是正则表达式，则下列也是正则表达式：

   a) $r_1 + r_2$ （并集）

   b) $r_1r_2$ （连接）

   c) $r^*$ （克林闭包）

   d) $(r)$ （分组）

注意：一些作者（以及大多数编程环境）使用符号 $r_1 \mid r_2$ 表示并集。

每个正则表达式都代表一个语言，即所有匹配其模式的字符串构成的集合。形式上，我们将与正则表达式 $r$ 对应的语言记作 $L(r)$，因此有 $L(\phi)=\{ \}$，$L(\lambda)=\{\lambda\}$，对字母表中的每个符号 $c$ 有 $L(c)=\{c\}$。此外还满足以下关系：

• $L(r_1+r_2)=L(r_1)\cup L(r_2)$
• $L(r_1r_2)=L(r_1)L(r_2)$
• $L(r^*)=(L(r))^*$
• $L((r))=L(r)$

上述定义是一种构造性定义。例如，在 $\Sigma =\{a,b,c\}$ 的情况下，我们可以构造正则表达式 $aa^*c^*b^*$ 如下：

• 根据规则1–c，$a$、$b$ 和 $c$ 都是正则表达式。
• 根据规则2–c，$a^*$、$b^*$ 和 $c^*$ 是正则表达式。
• 再根据规则2–b（应用三次），$aa^*c^*b^*$ 是一个正则表达式。

现在设 $\Sigma =\{a,b\}$，我们构造一个表示包含子串 $aba$ 的所有由 $a$ 和 $b$ 组成的字符串的语言的正则表达式。我们不关心 $aba$ 前后是什么内容，因此该语言的一个正则表达式为 $(a+b)^*aba(a+b)^*$。

满足定义的形式化构造过程如下：

• 根据规则1–c，$a$ 和 $b$ 是正则表达式。
• 根据规则2–b（应用两次），$aba$ 是正则表达式。
• 根据规则2–a，$a+b$ 是正则表达式。
• 根据规则2–d，$(a+b)$ 是正则表达式。
• 根据规则2–c，$(a+b)^*$ 是正则表达式。
• 最后根据规则2–b（应用两次），$(a+b)^*aba(a+b)^*$ 是正则表达式。

以下是字母表 $\Sigma=\{a,b\}$ 上的一些其他正则表达式示例。

正则表达式操作符的优先级与代数中的类似：

1. 分组具有最高优先级。
2. 其次是克林闭包（类似于幂运算）。
3. 然后是连接（类似于乘法）。
4. 最后是并集（类似于加法）。

注意上表最后一个例子中的子表达式 $ab^*a$。我们知道为了保证 $a$ 的数量为偶数，必须成对引入两个 $a$，但它们不必相邻，因此我们在两个 $a$ 之间插入 $b^*$。

记住：正则表达式是一种用于文本处理的模式语言。

虽然我们习惯于使用指数作为重复的简写形式，但在正则表达式中不允许使用变量作为指数。例如，$a^3$ 作为 $aaa$ 的简写是合法的正则表达式，因为 $aaa$ 本身就是一个正则表达式；但 $a^n$ 不是正则表达式。

记住：当 $k$ 为常量时，表达式 $a^k$ 是正则表达式；但当 $n$ 为变量时，$a^n$ 不是正则表达式！

正则表达式也遵循某些代数规则，例如分配律：$aa+ab=a(a+b)$ 以及 $b+ba=b(\lambda+a)$。此处顺序很重要，因为看似乘法的操作实际上是字符串连接，因此 $a(a+b) \neq (a+b)a$。下表总结了重写正则表达式的常见规则。

注意：正则表达式的“相等”用于表示对应语言的等价性。当我们写作 $r_1 = r_2$ 而非 $r_1\equiv r_2$ 时，其含义是 $L(r_1) = L(r_2)$。

除了上述规则外，还有一些关于正则表达式的附加规则：

$$r^*r^*=r^* \\ (r+s)^*=(r^*s^*)^*=(s^*r^*)^* \\ L(r^*)\subseteq L(s^*)\rightarrow r^*s^*=s^* \\ L(r)\subseteq L(s^*)\rightarrow (r+s)^*=s^*$$

例如，我们可以得出 $(r+\lambda)^*=r^*$，因为 $L(\lambda)=\{\lambda\} \subseteq L(r^*)$。同理，$\{aa\} \subseteq L(a^*)$，所以 $(a+aa)^*=a^*$。

再考虑表达式 $(a^*+\phi)^*+aa$。由于空集对第一项无影响，有 $(a^*+\phi)^*=(a^*)^*=a^*$，因此原表达式可简化为 $a^*+aa$。然而 $\{aa\} \subseteq L(a^*)$，故 $aa$ 是冗余的，使得原表达式等价于 $a^*$。

正则表达式在定义语言记号的模式方面非常有用。例如，一个字母标识符符合模式 $<letter><letter>^*$，其中 $<letter>$ 表示字母表中的任意单个字母。由多个符号组成的变量名用尖括号括起以便清晰区分。编辑器和类UNIX文本工具常用一种简写记法，使用方括号界定字符范围，如 $[A-Za-z][A-Za-z]^*$。

这种用方括号界定的组称为字符类，表示一组可接受字符中的任意一个。例如，[aeiou] 表示任意单个元音字符。使用连字符可以指定字符范围，因此 $[A-Za-z]$ 表示任意字母。加号（$+$）作为上标时意为“一个或多个”，因此我们可以直接写成 $[A-Za-z]^+$ 而非 $[A-Za-z][A-Za-z]^*$。C语言中的十进制整数不能以0开头，其模式为 $[1–9][0–9]^*$。这些特殊缩写并不属于我们所介绍的正则表达式的正式定义范畴，而是语言设计者和文本编辑程序为方便起见而采用的扩展功能。