查看“︁正则表达式”︁的源代码

[[分类:形式语言]]
[[分类:形式语言实例]]
{{InfoBox
|name=正则表达式
|eng_name=regular expression
|aliases=regexp,regex,re
}}
'''正则表达式'''('''regular expression''', 缩写为 '''regex''' 或 '''regexp''' 或 '''re''')，有时也简称'''正则'''，是一种为了进行文本[[模式匹配]]所设计的用于表达模式的[[形式语言]]。其通常作为一种形式[[元语言]]使用，所能描述的语言范围为[[正则语言]]，且本身也是一种正则语言。

正则表达式在各种库及文本搜索中都有着广泛的应用，这些不同的[[实现]]称为不同的'''正则表达式引擎'''('''regex engine''')或'''正则引擎'''。各种正则引擎对于基本的正则表达式语法都有支持，只是其中对于相对不常用的语法存在一些差异，有时也称为正则表达式的'''方言'''('''dialect''')。

正则表达式通常用于模式匹配，因此也可以被称为一个'''模式'''('''pattern''')。除完整字符串符合模式外，也存在搜索其中符合模式子串的操作。这时也说一个正则表达式'''匹配'''('''match''')一个字符串或其子串，或一个字符串或其子串'''匹配'''('''match''')一个正则表达式。严格按照形式语言的术语，可以表述为这个正则表达式'''表示'''了一种形式语言，这个字符串属于这个正则表达式所表示的形式语言。

== 形式语言定义/语义对应 ==

=== 正则表达式作为形式语言的字母表 ===

正则表达式由字面字符和运算符构成。字面字符是所要描述语言中的字符，用于匹配对应字符本身；运算符是正则表达式这一元语言中表达运算的符号，对应不同的语义。符号较多，以下规则部分一起列举。

=== 正则表达式规则 ===

* 归纳基础
** 正则表达式是字符串，但是如果需要表示[[空语言]] <math>\varnothing</math> ，理论上使用空集作为正则表达式。由于实际使用中不需要直接匹配空语言，这一条是理论上的。
** 空字符串 <math>\varepsilon</math> 是一个正则表达式，表示仅含空字符串的语言 <math>L(\varepsilon) = \{\varepsilon\}</math> 。
** 一个被描述语言符号构成的字符串，如 <code>a</code> ，是一个正则表达式，表示语言 <math>L(a) = \{a\}</math> 。也就是说，正则表达式 <math>a</math> 刚好与形式语言中的字符串 <math>a</math> 匹配。
* 归纳步骤
** 在正则表达式两侧加括号，仍然是一个正则表达式，且不改变其表示的语言，即 <math>L((r))=L(r)</math> 。
** 竖线 <code>|</code> 表示选择运算符，连接两个正则表达式得到新的正则表达式。表示匹配其中任何一个正则表达式都视为匹配这个正则表达式。也就是说 <math>(r)|(s)</math> 表示左右两侧的正则表达式表示语言的[[并集]]，即 <math>L(r|s)=L(r)\cup L(s)</math> 。如 <code>a|b</code> 表示语言 <math>\{a,b\}</math> 。
** 连接运算符，直接连接两个正则表达式得到新的正则表达式，表示一词匹配两个正则表达式。也就是说 <math>(r)(s)</math> 表示两个正则表达式所表达语言的[[连接]] <math>L((r)(s)) = L(r)L(s)</math> 。如 <code>ab</code> 表示语言 <math>\{a\}\{b\} = \{ab\}</math> 。
** Kleene 闭包运算符 <code>*</code> ，用在一个正则表达式后得到新的正则表达式，表示重复匹配 0 到多次这一正则表达式。也就是说 <math>(r)*</math> 表示这个正则表达式所表达语言的 [[Kleene 闭包|Kleene 闭包]]，即 <math>L((r)*) = L(r)^*</math> 。如 <code>a*</code> 表示语言 <math>\{\varepsilon,a,aa,aaa,\cdots\}</math> 。
** 按照优先级 <code>*</code> 、连接、选择优先级递减，且左结合的方式，允许省略括号。

=== 通用方言规则 ===

以上规则建立了理论上的正则表达式，但是实际上因为有些常见表达方式缺少简单的表达方式，一般会被引入以下运算符。
另外这一章节中写的语法是跨多种方言的组合，因此相对复杂。

* 数量
** Kleene 闭包运算符 <code>*</code> 同上
** 问号 <code>?</code> ，用在一个正则表达式后，表示匹配这个正则表达式或者匹配到空串上。正则表达式 <math>r?</math> 相当于 <math>r|\varepsilon</math> ，即 <math>L((r)?)=L(r)\cup \{\varepsilon\}</math> 。
** Kleene 正闭包运算符 <code>+</code> ，用在一个正则表达式后，表示重复 1 到多次匹配这个正则表达式。正则表达式 <math>r+</math> 相当于 <math>rr*</math> ，即 <math>L((r)+)=L(r)^+</math> 。如 <code>a+</code> 表示语言 <math>\{a,aa,aaa,\cdots\}</math> 。
** （仅部分方言）非贪婪匹配：只出现在寻找子串匹配的场景。由于匹配算法的关系，大部分情况下 <code>a.+b</code> 在 <code>abcbd</code> 中会匹配到 <code>abcb</code> ，也就是尽可能匹配更长的范围，称为'''贪婪'''('''greedy''')匹配。有些方言允许在其中匹配尽可能短的范围，称为'''懒惰'''('''lazy''')匹配，此时 <code>?,*,+</code> 三个符号对应地变成 <code>??,*?,+?</code> ，对应匹配到 <code>ab</code> 因为遇到一个 b 结束寻找。
** （仅部分方言）次数指定 <code>{n}</code> ，用在一个正则表达式后，表示重复恰好 n 次匹配这个正则表达式。比如正则表达式 <math>r\{3\}</math> 相当于 <math>rrr</math> ，即 <math>L((r){n})=L(r)^n</math> 。如 <code>a{3}</code> 相当于 <code>aaa</code> ，表示语言 <math>\{aaa\}</math> 。
** （仅部分方言）次数范围指定 <code>{min,max}</code> ，用在一个正则表达式后，表示重复最少 min 次最多 max 次匹配这个正则表达式。比如正则表达式 <math>r\{3,5\}</math> 相当于 <math>rrrr?r?</math> ，即 <math>L((r){m,n})=L(r)^m \cup L(r)^{m+1} \cup \cdots \cup L(r)^n</math> 。如 <code>a{3,5}</code> 相当于 <code>aaaa?a?</code> ，表示语言 <math>\{aaa,aaaa,aaaaa\}</math> 。特别地， <code>{min,}</code> 和 <code>{,max}</code> 表示不限制最多次数和不限制最少次数（即最少 0 次）。
* 分组
** <code>( )</code> 在标准意义基础上，还表示分组运算符，内部含有一个正则表达式，表示这里的正则表达式是一个分组。传统上分组有两种不同的功能：将内部正则表达式做为一个整体解析，也就是调整优先级；'''捕获'''一段被匹配字符串，并按照左括号顺序编号，有的方言允许对编号进行引用。
** （仅部分方言）重复匹配某个分组。可以匹配另一个分组，比如 <code>(ab?)c\1</code> 表示 <math>\{aca,abcab\}</math> 而不能匹配 <code>abca</code> 。其中的 <code>\1</code> 表示第一个分组。需要注意的是，有这种匹配时，刻画的内容不是正则语言或[[上下文无关语言]]，而是[[上下文有关语言]]。
** 部分方言使用 <code>(?: )</code> 表示仅起优先级功能，不起提供编号的功能。
* 字符
** 通配符 <code>.</code> 表示匹配任意一个字符，且不包括[[换行符]]。即 <math>L(.)=\sigma\setminus\{\mathtt{LF}\}</math> ，匹配任意一个字符构成的字符串，也就是字母表集合本身。
** 字符类 <code>[ ]</code> ，括号中为字母表中的多个字母，表示匹配其中任意一个字符，相当于选择运算符和括号的缩写。比如 <code>[abcd]</code> 相当于 <code>(a|b|c|d)</code> 。特别地，可以使用范围，比如 <code>[a-h]</code> 相当于 <code>[abcdefgh]</code> 或者写成 <code>(a|b|c|d|e|f|g|h)</code> ，也可以扩展出 <code>[a-h123]</code> 和 <code>[0-9a-f]</code> 这种范围与单个字母混用的。
** （仅部分方言）否定字符类 <code>[^ ]</code> （也有的方言中是 <code>[! ]</code> ），括号中为字母表中的多个字母，表示不匹配其中任意一个字符。也有类似 <code>[^a-h]</code> 的范围写法。
** （仅部分方言）预制字符类型，如一个空白字符、一个数字、一个字母、一个字母或数字，这些一般也可以放进字符类中代替一个范围进行简化表达。
** 转义字符。如果要描述的形式语言中刚好有字符和正则表达式运算符的字符重复了，在前面加上转义字符来表示这个匹配形式语言中的字符。如 <code>a\|b</code> 匹配的不是 a 或 b ，而是 <code>a|b</code> 这个长度为 3 的字符串。
* 位置断言：这类不匹配字符串，而是检查匹配过程中这个位置是否符合某个断言。一般不用来匹配字符串，而是查找子串匹配时需要指定子串位置或上下文不属于匹配内容的部分。
** 字符串首/行首 <code>^</code> 、字符串末/行末 <code>$</code> ：如果匹配到这里时不是正好遇到一行的开始或结束位置，则匹配失败。比如 <code>^123</code> 可以匹配 <code>123456</code> 的前三个字符，却不匹配 <code>0123456</code> 中的 123 。
** （仅部分方言）词边界：如果匹配到这里时不满足一侧为字母或数字，另一侧不是字母或数字，则匹配失败。
** （仅部分方言）环视(lookaround)：如果匹配到这个位置时，“向左侧或右侧看”的字符串是否匹配某个正则表达式。比如 <code>123(?=456)</code> 可以匹配 <code>123456</code> 或 <code>0123456</code> 中的子串，却不匹配 <code>012345</code> 中的，可以解释为匹配 123 且匹配后继续往右看必须是 456 。根据左侧(lookbehine)右侧(lookahead)和匹配不匹配有右侧匹配 <code>(?= )</code> ，右侧不匹配 <code>(?! )</code> ，左侧匹配 <code>(?< )</code> ，左侧不匹配 <code>(?<! )</code> 四种。

== 自动机等价 ==

正则表达式通常被转换为[[非确定有限自动机]]或[[确定有限自动机]]进行匹配。