当前位置:首页 > 芯闻号 > 充电吧
[导读]1.历史:引用正则表达式萌芽于1940年代的神经生理学研究,由著名数学家Stephen Kleene第一个正式描述。具体地说,Kleene归纳了前述的神经生理学研究,在一篇题为《正则集代数》的论文中定

1.历史:

引用
正则表达式萌芽于1940年代的神经生理学研究,由著名数学家Stephen Kleene第一个正式描述。具体地说,Kleene归纳了前述的神经生理学研究,在一篇题为《正则集代数》的论文中定义了“正则集”,并在其上定义了一个代数系统,并且引入了一种记号系统来描述正则集,这种记号系统被他称为“正则表达式”。在理论数学的圈子里被研究了几十年之后,1968年,后来发明了UNIX系统的Ken Thompson第一个把正则表达式用于计算机领域,开发了qed和grep两个实用文本处理工具,取得了巨大成功。在此后十几年里,一大批一流计算机科学家和黑客对正则表达式进行了密集的研究和实践。在1980年代早期,UNIX运动的两个中心贝尔实验室和加州大学伯克利分校分别围绕grep工具对正则表达式引擎进行了研究和实现。与之同时,编译器“龙书”的作者Alfred Aho开发了Egrep工具,大大扩展和增强了正则表达式的功能。此后,他又与《C程序设计语言》的作者Brian Kernighan等三人一起发明了流行的awk文本编辑语言。到了1986年,正则表达式迎来了一次飞跃。先是C语言顶级黑客Henry Spencer以源代码形式发布了一个用C语言写成的正则表达式程序库(当时还不叫open source),从而把正则表达式的奥妙带入寻常百姓家,然后是技术怪杰Larry Wall横空出世,发布了Perl语言的第一个版本。自那以后,Perl一直是正则表达式的旗手,可以说,今天正则表达式的标准和地位是由Perl塑造的。Perl 5.x发布以后,正则表达式进入了稳定成熟期,其强大能力已经征服了几乎所有主流语言平台,成为每个专业开发者都必须掌握的基本工具。



2.DFA和NFA

引用理解DFA和NFA
正则表达式引擎分成两类,一类称为DFA(确定性有穷自动机),另一类称为NFA(非确定性有穷自动机)。两类引擎要顺利工作,都必须有一个正则式和一个文本串,一个捏在手里,一个吃下去。DFA捏着文本串去比较正则式,看到一个子正则式,就把可能的匹配串全标注出来,然后再看正则式的下一个部分,根据新的匹配结果更新标注。而NFA是捏着正则式去比文本,吃掉一个字符,就把它跟正则式比较,匹配就记下来:“某年某月某日在某处匹配上了!”,然后接着往下干。一旦不匹配,就把刚吃的这个字符吐出来,一个个的吐,直到回到上一次匹配的地方。
DFA与NFA机制上的不同带来5个影响:
1. DFA对于文本串里的每一个字符只需扫描一次,比较快,但特性较少;NFA要翻来覆去吃字符、吐字符,速度慢,但是特性丰富,所以反而应用广泛,当今主要的正则表达式引擎,如Perl、Ruby、Python的re模块、Java和.NET的regex库,都是NFA的。
2. 只有NFA才支持lazy和backreference等特性;
3. NFA急于邀功请赏,所以最左子正则式优先匹配成功,因此偶尔会错过最佳匹配结果;DFA则是“最长的左子正则式优先匹配成功”。
4. NFA缺省采用greedy量词(见item 4);
5. NFA可能会陷入递归调用的陷阱而表现得性能极差。

我这里举一个例子来说明第3个影响。

例如用正则式/perl|perlman/来匹配文本 ‘perlman book’。如果是NFA,则以正则式为导向,手里捏着正则式,眼睛看着文本,一个字符一个字符的吃,吃完 ‘perl’ 以后,跟第一个子正则式/perl/已经匹配上了,于是记录在案,往下再看,吃进一个 ‘m’,这下糟了,跟子式/perl/不匹配了,于是把m吐出来,向上汇报说成功匹配 ‘perl’,不再关心其他,也不尝试后面那个子正则式/perlman/,自然也就看不到那个更好的答案了。

如果是DFA,它是以文本为导向,手里捏着文本,眼睛看着正则式,一口一口的吃。吃到/p/,就在手里的 ‘p’ 上打一个钩,记上一笔,说这个字符已经匹配上了,然后往下吃。当看到 /perl/ 之后,DFA不会停,会尝试再吃一口。这时候,第一个子正则式已经山穷水尽了,没得吃了,于是就甩掉它,去吃第二个子正则式的/m/。这一吃好了,因为又匹配上了,于是接着往下吃。直到把正则式吃完,心满意足往上报告说成功匹配了 ‘perlman’。

由此可知,要让NFA正确工作,应该使用 /perlman|perl/ 模式。

通过以上例子,可以理解为什么NFA是最左子式匹配,而DFA是最长左子式匹配。实际上,如果仔细分析,关于NFA和DFA的不同之处,都可以找出道理。而明白这些道理,对于有效应用正则表达式是非常有意义的。


写道正则表达式的形式定义故意非常精简,避免定义多余的量词 ? 和 +,它们可以被表达为: a+ = aa* 和 a? = (a|ε)。有时增加补算子 ~ ;~R 指示在 Σ* 上的不在 R 中的所有字符串的集合。补算子是多余的,因为它使用其他算子来表达(尽管计算这种表示的过程是复杂的,而结果可能指数性的增大)。
这种意义上的正则表达式可以表达正则语言,精确的是可被有限状态自动机接受的语言类。但是在简洁性上有重要区别。某类正则语言只能用大小指数增长的自动机来描述,而要求的正则表达式的长度只线性的增长。正则表达式对应于乔姆斯基层级的类型-3文法。在另一方面,在正则表达式和不导致这种大小上的爆炸的非确定有限状态自动机(NFA)之间有简单的映射;为此 NFA 经常被用作正则表达式的替代表示。
我们还要在这种形式化中研究表达力。如下面例子所展示的,不同的正则表达式可以表达同样的语言: 这种形式化中存在着冗余。
有可能对两个给定正则表达式写一个算法来判定它们所描述的语言是否本质上相等,简约每个表达式到极小确定有限自动机,确定它们是否同构(等价)。
这种冗余可以消减到什么程度? 我们可以找到仍有完全表达力的正则表达式的有趣的子集吗? Kleene 星号和并集明显是需要的,但是我们或许可以限制它们的使用。这提出了一个令人惊奇的困难问题。因为正则表达式如此简单,没有办法在语法上把它重写成某种规范形式。过去公理化的缺乏导致了星号高度问题。最近 Dexter Kozen 用克莱尼代数公理化了正则表达式。
很多现实世界的“正则表达式”引擎实现了不能用正则表达式代数表达的特征。

目前正则引擎支持的语言种类:


引擎类型程序DFAawk(大多数版本)、egrep(大多数版本)、flex、lex、MySQL、Procmail传统型 NFAGNU Emacs、Java、grep(大多数版本)、less、more、.NET语言、PCRE library、Perl、PHP(所有三套正则库)、Python、Ruby、set(大多数版本)、viPOSIX NFAmawk、Mortice Lern System's utilities、GUN Emacs(明确指定时使用)DFA/NFA混合GNU awk、 GNU grep/egrep、 Tcl 

本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

随着人工智能(AI)模型变得越来越复杂,数据量不断攀升,数据中心正在通过改变系统架构,来实现更快、更高效的处理。

关键字: AI 连接器

Mar. 28, 2024 ---- TrendForce集邦咨询表示,除了铠侠(Kioxia)和西部数据(WDC)自今年第一季起提升产能利用率外,其它供应商大致维持低投产策略。尽管第二季NAND Flash采购量较第一...

关键字: SSD NAND Flash 智能手机

3月28日,美光宣布通过西安市善导公益慈善协会向西安市助爱小餐社区残疾人就业项目捐赠110余万元人民币。这笔捐款将资助130辆爱心移动餐车,为西安市创造至少130个残疾人就业岗位,助力残疾人及其家庭提高收入。

关键字: Micron

业内消息,据阿里巴巴内部人士透露,1688 近期启动全面入淘,先期开设三家店铺,后续这些店铺将整合成一个类似天猫超市的频道,并在淘宝推出 1688 严选贴牌的源头厂货。这意味着,1688 将携带百万源头厂商直接入驻淘宝。

关键字: 阿里巴巴 1688 淘宝

本周从内部人士处获知,运动科技公司Keep计划收缩线下健身运动空间Keepland,在运营部门进行了裁员,广州的拓店计划也因为裁员宣告结束,同时,目前北京仍在营业中的Keepland也将在租约到期后不再续签,陆续关闭自营...

关键字: 裁员 Keep

近日,胡润研究院发布《2024家大业大酒·胡润全球富豪榜》。70岁的钟睒睒财富比去年缩水9%,以4500亿元连续第四次成为中国首富,位于全球第21位,同比下降6位。44岁的黄峥财富比去年增长71%,即1600亿元,是今年...

关键字: 钟睒睒 AI

近日,社交媒体巨头Meta(Facebook)创始人马克・扎克伯格将其价值3亿美金的超级游艇开到了美国,这艘游艇名为“Project 1010”,目前位于佛罗里达州劳德代尔的埃弗格莱斯港,此举恰逢其40岁生日之前,引发外...

关键字: 扎克伯格 Meta Facebook

业内消息,上周索尼集团宣布将从2024财年开始提高索尼集团及两家附属运营公司员工的工资水平。对于主管级别的正式员工,每月最多增加超5万日元(约合2387元人民币),工资上涨水平与2023年相同,新员工的起薪也将在目前的基...

关键字: 加薪 索尼

本轮融资资金将用于已规模化供货的7纳米车规级芯片“龍鹰一号”的进一步量产和供货、基于“龍鹰一号”的高端智能座舱及舱行泊一体方案的市场推广,以及全场景高阶智驾新品AD1000的测试验证和市场导入。

关键字: 芯擎科技 芯片

根据戴尔日前发布的一份文件,该公司在过去一年里裁掉了大约6000名员工,以改善财务状况。

关键字: 戴尔 AI
关闭
关闭