族谱网 头条 人物百科

正则表达式

2020-10-16
出处:族谱网
作者:阿族小谱
浏览:580
转发:0
评论:0
译名问题RegularExpression的“Regular”一般被译为“正则”、“正规”、“常规”。此处的“Regular”即是“规则”、“规律”的意思,RegularExpression即“描述某种规则的表达式”之意。历史最初的正则表达式出现于理论计算机科学的自动控制理论和形式化语言理论中。在这些领域中有对计算(自动控制)的模型和对形式化语言描述与分类的研究。1940年,沃伦·麦卡洛克与WalterPitts(英语:WalterPitts)将神经系统中的神经元描述成小而简单的自动控制元。1950年代,数学家斯蒂芬·科尔·克莱尼利用称之为“正则集合”的数学符号来描述此模型。肯·汤普逊将此符号系统引入编辑器QED(英语:QED(texteditor)),随后是Unix上的编辑器ed(英语:ed(texteditor)),并最终引入grep。自此以后,正则表达式被广泛地应用于各种Unix或类...

译名问题

Regular Expression的“Regular”一般被译为“正则”、“正规”、“常规”。此处的“Regular”即是“规则”、“规律”的意思,Regular Expression即“描述某种规则的表达式”之意。

历史

最初的正则表达式出现于理论计算机科学的自动控制理论和形式化语言理论中。在这些领域中有对计算(自动控制)的模型和对形式化语言描述与分类的研究。

1940年,沃伦·麦卡洛克与Walter Pitts(英语:Walter Pitts)将神经系统中的神经元描述成小而简单的自动控制元。

1950年代,数学家斯蒂芬·科尔·克莱尼利用称之为“正则集合”的数学符号来描述此模型。肯·汤普逊将此符号系统引入编辑器QED(英语:QED (text editor)),随后是Unix上的编辑器ed (英语:ed(text editor) ),并最终引入grep。自此以后,正则表达式被广泛地应用于各种Unix或类Unix系统的工具中。

Perl的正则表达式源自于 Henry Spencer(英语:Henry Spencer)于1986年1月19日发布的regex,它已经演化成了pcre(Perl兼容正则表达式,Perl Compatible Regular Expressions(英语:PCRE),一个由Philip Hazel (英语:Philip Hazel)开发的,为很多现代工具所使用的库。

各计算机语言之间的正则表达式的集成目前开展得很差。Perl6的子项目Apocalypse的设计中已考虑到了这点。

理论

正则表达式可以用形式化语言理论的方式来表达。正则表达式由常量和算子组成,它们分别指示字符串的集合和在这些集合上的运算。给定有限字母表Σ定义了下列常量:

(“空集”) ∅ 指示集合 ∅

(“空串”)ε指示集合{ε}

(“文字字符”)在Σ中的 a 指示集合{ a }

定义了下列运算:

(“串接”) RS 指示集合{ αβ | α ∈ R ,β ∈ S }。例如:{"ab","c"}{"d","ef"} = {"abd", "abef", "cd", "cef"}。

(“选择”) R | S 指示 R 和 S 的并集。例如:{"ab", "c"}|{"ab", "d", "ef"}= {"ab", "c", "d", "ef"}

(“Kleene星号”) R * 指示包含ε并且闭合在字符串串接下的 R 的最小超集。这是可以通过 R 中的零或多个字符串的串接得到所有字符串的集合。例如,{"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", ... }。

上述常量和算子形成了克莱尼代数。

很多课本使用对选择使用符号 ∪ , + 或 ∨ 替代竖杠。

为了避免括号,假定Kleene星号有最高优先级,接着是串接,接着是并集。如果没有歧义则可以省略括号。例如, (ab)c 可以写为 abc 而 a|(b(c*)) 可以写为 a|bc* 。

例子:

a|b* 指示{ a , ε, b , bb , bbb , ...}。

(a|b)* 指示由包括空串、任意数目个 a 或 b 字符组成的所有字符串的集合。

ab*(c|ε) 指示开始于一个 a 接着零或多个 b 和最终可选的一个 c 的字符串的集合。

正则表达式的定义非常精简,避免多余的量词 ? 和 + ,它们可以被表达为: a+ = aa* 和 a? = (a|ε) 。有时增加补算子~;~ R 指示在Σ*上的不在 R 中的所有字符串的集合。补算子是多余的,因为它使用其他算子来表达(尽管计算这种表示的过程是复杂的,而结果可能以指数增大)。

这种意义上的正则表达式可以表达正则语言,精确的是可被有限状态自动机接受的语言类。但是在简洁性上有重要区别。某类正则语言只能用大小指数增长的自动机来描述,而要求的正则表达式的长度只线性的增长。

正则表达式对应于乔姆斯基层级的类型-3文法。在另一方面,在正则表达式和不导致这种大小上的爆炸的非确定有限状态自动机(NFA)之间有简单的映射;为此NFA经常被用作正则表达式的替代表示。

我们还要在这种形式化中研究表达力。如下面例子所展示的,不同的正则表达式可以表达同样的语言:这种形式化中存在着冗余。

有可能对两个给定正则表达式写一个算法来判定它们所描述的语言是否本质上相等,简约每个表达式到极小确定有限自动机,确定它们是否同构(等价)。

这种冗余可以消减到什么程度?我们可以找到仍有完全表达力的正则表达式的有趣的子集吗? Kleene星号和并集明显是需要的,但是我们或许可以限制它们的使用。这提出了一个令人惊奇的困难问题。因为正则表达式如此简单,没有办法在语法上把它重写成某种规范形式。过去公理化的缺乏导致了星号高度问题。最近Dexter Kozen用克莱尼代数公理化了正则表达式。

很多现实世界的“正则表达式”引擎实现了不能用正则表达式代数表达的特征。

基本语法

一个正则表达式通常被称为一个模式(pattern),为用来描述或者匹配一系列匹配某个句法规则的字符串。例如: Handel 、 Händel 和 Haendel 这三个字符串,都可以由“ H(a|ä|ae)ndel ”这个模式来描述。大部分正则表达式的形式都有如下的结构:

上述这些构造子都可以自由组合,因此,“ H(ae?|ä)ndel ”和“ H(a|ae|ä)ndel ”是相同的。

精确的语法可能因不同的工具或程序而异。

表达式全集

正则表达式有多种不同的风格。下表是在PCRE(英语: Perl_Compatible_Regular_Expressions)中元字符及其在正则表达式上下文中的行为的一个完整列表,适用于Perl或者Python编程语言(grep或者egrep的正则表达式文法是PCRE的子集):

优先权

示例

验证字符串是否只含数字与英文,字符串长度并在4~16个字符之间

$str="a1234";if(preg_match("/^[a-zA-Z0-9]{4,16}$/",$str)){echo"驗證成功";}else{echo"驗證失敗";}?>

以下示例是用Perl语言写的,与上面的示例功能相同

print$str="a1234"=~m:^[a-zA-Z0-9]{4,16}$:?"COMFIRM":"FAILED";

print$str="a1234"=~m"^\w[12]\d{8}$"?"COMFIRM":"INVALID";


免责声明:以上内容版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。感谢每一位辛勤著写的作者,感谢每一位的分享。

——— 没有了 ———
编辑:阿族小谱
发表评论
写好了,提交
{{item.label}}
{{commentTotal}}条评论
{{item.userName}}
发布时间:{{item.time}}
{{item.content}}
回复
举报
点击加载更多
打赏作者
“感谢您的打赏,我会更努力的创作”
— 请选择您要打赏的金额 —
{{item.label}}
{{item.label}}
打赏成功!
“感谢您的打赏,我会更努力的创作”
返回

更多文章

更多精彩文章
扫一扫添加客服微信